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 Intuitively, I am not convinced by « all the differential equations of physics can be interpreted in terms of computable numbers ». The question isn’t about continuum, unstable or chaotic systems, etc. Instead, the question’s about mathematical modeling (diff. eq.) that might output infinity.
@khinsen « We postpone the treatment of derivatives until Chapter 1. This is because the computability theory of derivatives is a bit more complicated. » Ch. 0, p.11
@khinsen « If a computable function possesses a continuous derivative, is the derivative necessarily computable? The answer turns out to be no. This raises the question: are there regularity conditions which we can impose on the initial computable function(e.g. being C^n for some fixed n,or C^∞) which insure the computability of the derivative. Here the answer’s yes. The problem’s to find the right conditions. » Ch.1,p.1
@khinsen Hum, the topic seems very complicated! :-)
Well, page p.194 mentions still open questions for linear cases (point 6) and for nonlinear problems (point 7).
« […] when T is neither self-adjoint nor compact, noncomputable eigenvalues can occur (Theorem 4.5). »
And the vast area of nonlinear problems seems barely touched.
Thanks for the reference! Very interesting… although very hard! ;-)