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.
Simon Tournier@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
@[email protected] @[email protected] @[email protected] Pardon me for jumping in uninvited, but this is an interesting topic to me and I thought I could offer some food for thought.
I'd recommend checking out this article on computable physics at nLab: https://ncatlab.org/nlab/show/computable+physics especially the discussion and references therein.
A key point is the distinction between type I and type II computability. I don't think anyone could credibly argue that the universe/physics is type I computable; that question was put to rest long ago. However, it seems to me it's still up in the air whether it is or could be type II computable. That nLab post has a reference claiming there are non-computable quantum mechanical phenomena:
Cristian Calude, Michael Dinneen, Monica Dumitrescu, Karl Svozil, Experimental Evidence of Quantum Randomness Incomputability, Phys. Rev. A 82, 022102 (2010) ( https://arxiv.org/abs/1004.1521 )
From the abstract:
In contrast with software-generated randomness (called pseudo-randomness), quantum randomness is provable incomputable, i.e.\ it is not exactly reproducible by any algorithm. We provide experimental evidence of incomputability --- an asymptotic property --- of quantum randomness by performing finite tests of randomness inspired by algorithmic information theory.
I haven't read this paper or any followups and cannot offer an informed opinion about it. Judging just from the abstract it doesn't sound like a slam dunk proof that there are non-computable phenomena, and there are authors who suggest there aren't, that the universe/physics really is type II computable. Important concepts like the Schroedinger equation have been shown to be type II computable, for instance, which is an intriguing piece of evidence.
By the way, in case you're not familiar, type I computability is what most folks think of when they think of computable: a partial function from natural numbers to natural numbers that can be implemented in a Turing machine or programming language. Type II computability is different: a function from the reals to the reals that can be so implemented. The key difference is that the input to a type II computable function can be any real number, including non-computable ones. Computable analysis concerns type II computable functions as I understand it. None of this lies in my area of expertise, just to be clear.
I'd recommend checking out this article on computable physics at nLab: https://ncatlab.org/nlab/show/computable+physics especially the discussion and references therein.
A key point is the distinction between type I and type II computability. I don't think anyone could credibly argue that the universe/physics is type I computable; that question was put to rest long ago. However, it seems to me it's still up in the air whether it is or could be type II computable. That nLab post has a reference claiming there are non-computable quantum mechanical phenomena:
Cristian Calude, Michael Dinneen, Monica Dumitrescu, Karl Svozil, Experimental Evidence of Quantum Randomness Incomputability, Phys. Rev. A 82, 022102 (2010) ( https://arxiv.org/abs/1004.1521 )
From the abstract:
In contrast with software-generated randomness (called pseudo-randomness), quantum randomness is provable incomputable, i.e.\ it is not exactly reproducible by any algorithm. We provide experimental evidence of incomputability --- an asymptotic property --- of quantum randomness by performing finite tests of randomness inspired by algorithmic information theory.
I haven't read this paper or any followups and cannot offer an informed opinion about it. Judging just from the abstract it doesn't sound like a slam dunk proof that there are non-computable phenomena, and there are authors who suggest there aren't, that the universe/physics really is type II computable. Important concepts like the Schroedinger equation have been shown to be type II computable, for instance, which is an intriguing piece of evidence.
By the way, in case you're not familiar, type I computability is what most folks think of when they think of computable: a partial function from natural numbers to natural numbers that can be implemented in a Turing machine or programming language. Type II computability is different: a function from the reals to the reals that can be so implemented. The key difference is that the input to a type II computable function can be any real number, including non-computable ones. Computable analysis concerns type II computable functions as I understand it. None of this lies in my area of expertise, just to be clear.
@abucci As I mentioned in another reply to @yoginho, the nLab page is an interesting resource but mixes two different ideas: type-I computability, which is a question of scientific modelling ("could physical laws be replaced by integer relations?"), and type-II, which is a mathematical question ("are solutions to the mainstream laws of physics computable?")
I haven't read the article on quantum computability either, so I don't even know in which category it is situated.
I didn't see that other reply; sorry for the redundancy then!
CC: @[email protected] @[email protected]
CC: @[email protected] @[email protected]
@yoginho There's at least one more ingredient: the idea of determinism.
Teixithinking one can achieve 1. that precludes 2. thus 3. & 4.
1. design & engineer AGI
2. order AGI single sentence instructions without clear outcome benefits to follow-up
3. guess how AGI will interpret instructions —plus telling to the rest of us— in some stupid closed outcomes how to guess
4. tell us this is philosophy of AI
» The history of AI has repeatedly disproved our intuitions about intelligence « @melaniemitchell
@yoginho My understanding of the history of computationalism in 1 toot: (1) People identified "mind" with reasoning. (2) Reasoning had been identified with computing. (3) Someone then fallaciously thought all activity of mind must be like calculating from causes to effects.