Yogi JaegerThe history of computationalism in 1 tweet: (1) there was a theory of the human activity of calculating by rote. (2) Someone realized this is a physical activity. (3) Someone then fallaciously thought all physical activity [in the brain/universe] must be like calculating by rote.
This may be a bit of a hot take, I admit, but there really is nothing more to it than just that...
Roberto Toro@yoginho you wouldn't trace the roots of computationalism to logic?
@r3rt0 Nope. The idea that the universe is computable arguably originated with Newton, but computation in the modern sense definitely starts with Church/Turing. Uncountably many logically consistent systems are not Turing-computable.
@yoginho I see. But is Newtonian mechanics an example of computable theory? You can have, for example, a 3 body problem, which is fully Newtonian but not computable.
@r3rt0 Newton and his contemporaries use the verb "to compute" when talking about calculating predictions based on theory. But classical mechanics (in general) is not Turing-computable because of its continuum assumption and the non-computable reals that pop up as parameters in classical models (esp. deterministic chaos, i.e. the three-body problem).
Konrad Hinsen@yoginho My memories from a long-ago deep dive into computable analysis say the contrary: all the differential equations of physics can be interpreted in terms of computable numbers (as introduced by Turing) and computable functions. Even chaotic motion is computable (resource consumption doesn't enter into computability considerations).
@yoginho I don't know of any high-level overview, there are only detailed technical treatises. The best reference I have is "Computability in Analysis and Physics" by Marian Pour-El and Ian Richards:
@yoginho Another useful resource is
https://ncatlab.org/nlab/show/computable+physics
although it mixes different issues (the one we have been discussing is the type-II computability of the equations of physics). It has many references but unfortunately I don't have access to most of them.
@r3rt0 Given a suitable computer program (not too hard to write) and enough computational resources (a different story), you could compute the positions of the three bodies at any moment in time, to any finite precision you specify, given the positions at some initial time. In short, you could perform a simulation of the trajectories to any desired precision.
@r3rt0 For use in real life, you still have the problem of measuring or defining the initial positions to the required accuracy. The simulation would simply take whatever values you give it to be exact.
With some additional effort, you could get the algorithm to tell you the required precision for the initial positions, given your requested precision for a later time in the simulation.
Thanks, @khinsen, for the references. Very useful for my current research. Will check them out carefully.
I still don't see how the 3-body problem can really be considered computable. Initial conditions will include non-computable reals, and although they can be approximated to infinite precision that would take an infinite amount of time and resources, so not exactly computable in Turing's original sense (where computation must take a finite amount of time to terminate).
Anthony@[email protected] @[email protected] @[email protected] It's not clear to me what might be meant by saying the initial conditions aren't computable. What if all three bodies have 0 momentum, and start at positions (0,0,0), (0,1,0), and (0,0,1)? 0 and 1 are perfectly nice computable numbers, so these initial conditions are about as computable as you can get.
that would take an infinite amount of time and resources, so not exactly computable
It almost sounds like you're saying that any number that has an infinite decimal expansion is not computable, which would be a mischaracterization of the word "computable" (its technical meaning, at least). Please correct me (and ignore what follows) if I've misinterpreted.
π for example is a perfectly nice computable real number. You can write a relatively simple and short computer program that takes in a number n and tells you the first n digits of the decimal expansion of π. If you tried to run this program in a naive way and spit out all of π's decimal expansion, it'd run forever, spitting out digits and never terminating. But the program itself is perfectly finite. You can do all sorts of arithmetic, algebra, trig, and calculus with numbers represented like this as finite computer programs. Exactly like people do when they write expressions such as "π r²"--that expression doesn't take infinite resources to write down even though it involves at least one number with an infinite decimal expansion. At the very end of your sequence of calculations, if you needed to know a lot of digits of precision, you might have to wait a long time to get them. But that doesn't mean the number isn't computable: you could get as many digits of precision as you could possibly want in finite time and with finite resources.
that would take an infinite amount of time and resources, so not exactly computable
It almost sounds like you're saying that any number that has an infinite decimal expansion is not computable, which would be a mischaracterization of the word "computable" (its technical meaning, at least). Please correct me (and ignore what follows) if I've misinterpreted.
π for example is a perfectly nice computable real number. You can write a relatively simple and short computer program that takes in a number n and tells you the first n digits of the decimal expansion of π. If you tried to run this program in a naive way and spit out all of π's decimal expansion, it'd run forever, spitting out digits and never terminating. But the program itself is perfectly finite. You can do all sorts of arithmetic, algebra, trig, and calculus with numbers represented like this as finite computer programs. Exactly like people do when they write expressions such as "π r²"--that expression doesn't take infinite resources to write down even though it involves at least one number with an infinite decimal expansion. At the very end of your sequence of calculations, if you needed to know a lot of digits of precision, you might have to wait a long time to get them. But that doesn't mean the number isn't computable: you could get as many digits of precision as you could possibly want in finite time and with finite resources.
@abucci @khinsen @r3rt0 Yes, I know some reals are computable, but an uncountably infinite majority of them can only be approximated to an imperfect degree by algorithmic computation. These will matter (at infinite precision) when determining the dynamics of a chaotic system. Thus, the system is not computable.
Am I getting something wrong here?
@yoginho Yes: the infinities. In a finite universe, nothing can ever be infinite. Neither measurement precisions nor computations. If you ask for anything to be infinite, you rule out computability by definition.
So if you want to examine if the 3-body problem is computable, then you have to start from a precise formulation of the problem that doesn't require anything infinite.
@yoginho This holds for all of science, of course. Non-computable reals have no place in scientific models.
They were introduced as a convenience, before computability was understood. I'd love to see a serious effort to rebuild physics (and more) on computable analysis. Similar in spirit to rebuilding mathematics in a constructivist style. And profiting from the interesting analogies between measurement precision and accuracy of computations.
@yoginho Today, an important part of physics training is to learn how to interpret and work with the "infinitely big" and the "infinitely small". It's normal in a seminar to hear a question such as "how big is your x-going-to-inifinity in a real application?"
Professional physicists are well aware that infinities are idealizations that are useful in mathematical analysis, but need to be eliminated from any physical interpretation.
@yoginho First of all, I object to equating computable with analytic! A computable solution is one from which I can obtain numbers that can be compared with observations. An analytic solution is one that I can reason about using mathematical tools. A solution can be both analytic and computable, but also one without the other.
@yoginho Next: what is or isn't an analytic solution depends on the mathematical framework available for analysis. There has been a candidate for an analytic solution for more than a century: Sundman's expansion as a Puiseux series (details are in the Wikipedia article on the 3-body problem).
The problem is that there aren't many useful mathematical tools for working with Puiseux series, and therefore Sundman's solution has little practical relevance. So is it analytic?
@khinsen Ok. Granted. I meant an analytical solution in the traditional sense, as an explicit formula for the time evolution of a system. That wasn't clear. But your distinction here is interesting.
Bottom line is though: much of classical physics and relativity is not Turing-computable (i.e. in finite time with finite resources).
But whether this is a fundamental limit or whether we'll find workarounds is an open empirical quesition.
Is this correct?
Simon Tournier@khinsen Hum, I am not convinced that "classical" pendulum solution is computable although initial numbers are computable.
It implies "mathematical objects" as elliptic integrals that don't translate to "computable objects". The relation derived from "classical physics" between "computable numbers" isn't necessary computable.
Bah although "mathematical object" is clear for me, "computable objects" are much less clear. :-)
@khinsen Because they might diverge. I just took the first example that came in mind from "classical physics" to bound the discussion. :-)
Physics provides transformation from quantities to quantities. The initial quantities're computable numbers because we measure them. But there's no guarantee that the transformation's itself computable. The output quantities might be non-computable numbers. Ex: electricity, magnetism, etc
@khinsen Physics's about measurable quantities; inputs/outputs. Measurable means exactly the same as computable. So yes mathematical modeling that outputs non-measurable quantities're said to not be physically correct. That's a switch of the initial question. ;-)
My understanding of the question was: can we have "classical mechanics" (= mathematical modelling) that are not computable? My answer: yes. Example: resonant system
@khinsen And if we speak about physics (in general), I’m not familiar but there’s all this topic of re-normalisation.
All depends on how we bound “physics”. Philosophical question: identification between “physical object” with its “mathematical modelling”. One’s measurable while the other not necessary computable.
That's what I’ve tried to express with: « "mathematical objects" that don't translate to "computable objects" ».
@khinsen My point is about physics that outputs "infinity".
Applied to "classical physics", it means topics where resonance might appear. About "classical mechanics", we could imagine many systems.
Back to "classical pendulum", the divergence happens for an extreme case: the initial angle being vertical. And for that case, Newtonian mechanics is probably not the right physics. But still. :-)
@[email protected] @[email protected] @[email protected]
Bottom line is though: much of classical physics and relativity is not Turing-computable (i.e. in finite time with finite resources).
I'll continue to insist that this is a misleading statement. As I suggested in my previous post, the "finite time/finite resources" criterion is not what the word "computable" means. What you're talking about when you say that is a total computation, but total computable is strictly weaker than computable. Turing machines can compute functions that are not total computable; this is not a trivial distinction, but an absolutely defining one.
Classical physics could very well be computable in the sense that word is typically used. It could even be type I computable, the nice easy-to-understand version (well, easier). It might even be total computable, who knows! You make this statement with confidence, but the question isn't settled yet. There's a lot more going on here than such a simple dismissal acknowledges.
I'd also throw in that there are a number of efforts, including causal set theory, that, if successful, would unify quantum field theory and general relativity in a discrete structure (a causal set). If such efforts proved successful, and we assumed the universe were finite, it'd be a finite, discrete structure: the most eminently computable object possible.
Bottom line is though: much of classical physics and relativity is not Turing-computable (i.e. in finite time with finite resources).
I'll continue to insist that this is a misleading statement. As I suggested in my previous post, the "finite time/finite resources" criterion is not what the word "computable" means. What you're talking about when you say that is a total computation, but total computable is strictly weaker than computable. Turing machines can compute functions that are not total computable; this is not a trivial distinction, but an absolutely defining one.
Classical physics could very well be computable in the sense that word is typically used. It could even be type I computable, the nice easy-to-understand version (well, easier). It might even be total computable, who knows! You make this statement with confidence, but the question isn't settled yet. There's a lot more going on here than such a simple dismissal acknowledges.
I'd also throw in that there are a number of efforts, including causal set theory, that, if successful, would unify quantum field theory and general relativity in a discrete structure (a causal set). If such efforts proved successful, and we assumed the universe were finite, it'd be a finite, discrete structure: the most eminently computable object possible.
I've been reading some more today and I now understand the difference between what Turing meant by effective computation (type I) and what you mean here by computable (type II computability).
Turing machines can run infinite algorithms, but those were not included in type I by Turing himself who insisted they terminate.
This means that computable numbers are not really computable in this original sense, only approximable in finite time. This is different.
I find the whole discussion a bit bizarre: physicists insist that their theories are computable in practice with a concept of computability that requires infinite resources. Hmm. I think that's a bit funny.
I do get that infinite precision is mostly not required in practice (and cannot be achieved in measurement), but that still means that quantum randomness and chaos will be a problem for computational prediction.
This is all very interesting, but actually quite beside the main point that comes out of all of this: the question of computability is strictly about prediction, and nothing else.
It is *not* about understanding how the world works. It does *not* imply that all physical processes compute (beyond nervous systems & computers that evolved or that we've designed to do so).
Why would anyone assume they do though? That's where the fallacy lies.
@yoginho The attitude towards computability varies widely among physicists. The majority takes a very pragmatic attitude and doesn't talk much about it. "Computable is what I can compute with the means I have." Those who talk about such questions are a small minority.
Technical remark: type-II computability doesn't require infinite resources, but resources that grow rapidly with requested precision. I haven't seen any discussion of computational complexity in this context.
@yoginho If you look at the history of mathematical physics, the space of analytic solutions has systematically increased with progress in mathematics. Example: Bessel's differential equation got an analytic solution simply by labelling it as a Bessel function - once its properties were understood well enough to become a useful part of mathematical vocabulary.
@khinsen « Professional physicists are well aware that infinities are idealizations that are useful in mathematical analysis, but need to be eliminated from any physical interpretation. »
I think all the question’s about the relation between “physical object” and “mathematical object“. Physics is by definition measurable so computable. That doesn’t imply maths models are.
So, the question’s: are all maths models computable?
@khinsen « Professional physicists are well aware that infinities are idealizations that are useful in mathematical analysis, but need to be eliminated from any physical interpretation. »
Yes and for some fields, physicist formalized such elimination, as renormalization: a collection of technique that're used to treat infinities arising in calculated quantities.
https://en.wikipedia.org/wiki/Renormalization
@yoginho @abucci @r3rt0
@khinsen Physics manipulates finite quantities; physicists creates math models; internal steps in math models can be infinite; physicists creates other maths models to make this infinite again physically interpretable.
It's not because physical inputs and physical outputs are physically interpretable that the complete mathematical chain is computable.
Anyway, thanks for the reference and comments. Very insightful! :-)