5

Reading about Computable numbers I wondered if there is any physical experiment that returns non-computable numbers or if there is any physical theory that needs non-computable numbers. Because if that would be the case, we would have prove that the universe is not "simply" a simulation inside a Turing machine.

Bonus question: Could it be that classical mechanics is computable on a Turing machine but quantum mechanics is not?

asmaier
  • 9,794
  • 4
    http://physics.stackexchange.com/q/72396/ –  Aug 31 '15 at 20:49
  • 2
    (i) Quantum mechanics is computable on a (classical) Turing machine, it is only inefficient (with respect to time and space requirements). (ii) IMO it is irrelevant whether non-computable numbers arise in physical settings, as computable numbers are dense within the reals. – Sebastian Riese Aug 31 '15 at 22:14
  • 1
    You may find interesting a popular book by Sir Roger Penrose called "The Emperor's new mind". It discusses the issue in details and then presents the objective collapse theory (Penrose interpretation of QM) which is by definition not computable on a Turing machine (despite being deterministic). However this is just one man's opinion. The real answer to this question is yet unknown. – Prof. Legolasov Sep 01 '15 at 01:08

3 Answers3

4

Reading about Computable numbers I wondered if there is any physical experiment that returns non-computable numbers or if there is any physical theory that needs non-computable numbers. Because if that would be the case, we would have prove that the universe is not "simply" a simulation inside a Turing machine.

Measurements and experiments result in rational numbers (because we record finite precision decimal numbers as results), which are all "computable".

Physics theories use real numbers and their continuity in formulation of differential equations. However, this does not prove that the universe is not a discrete state simulation or reverse. Continuity in physics theories has little direct implication on whether that is how world really is, because with sufficiently short steps, this distinction makes no testable difference.

EDIT I should add that reproducing all properties of physical laws using a computer model is very difficult. Any discretization always introduces some behaviour that in some way does not respect physical laws. For example, discretized space, howsoever dense, cannot be exactly isotropic. Physical laws such as Maxwell's equations for EM field or Einstein equations for gravity, if we take them to be valid exactly, can't be reproduced exactly with discretized models. This does not mean universe can't be discrete, only that such discreteness should manifest in some ways that would contradict those physical laws. If that is so, those manifestations are so far too small to detect, or elude us.

Ján Lalinský
  • 37,229
  • This answer is wrong. Even if measurement results in rational numbers the fact that the classical laws of motion contain division means that you cannot simulate Newtonian physics with bounded precision. – Jason Gross May 08 '23 at 02:47

  • "you cannot simulate Newtonian physics with bounded precision" What does this mean? Using computer, we can do numerical integration with howsoever good precision.

     – Ján Lalinský May 08 '23 at 10:46
  • For any fixed output precision $\epsilon > 0$, I can construct a configuration of fewer then ten point masses, such that there is no input precision $\delta > 0$ where knowing the initial positions, masses, and velocities to with precision $\delta$ would allow computation (according to Newtonian gravity) of the positions of the particles 2 seconds later to within $\epsilon$ precision. Unlike general relativity, Newtonian gravity has exposed singularities and is discontinuous. Discontinuous real functions (like 1/r^2) are not computable in the neighborhood of their discontinuities. – Jason Gross May 09 '23 at 07:59
  • That seems to be possible only if the trajectory of the system comes to a singular point, where uniqueness of solution of the eom breaks down (initial condition no longer implies unique solution). My answer implicitly assumes ordinary regime where the initial conditions and equations have unique solution. – Ján Lalinský May 09 '23 at 11:23
  • If there is unique solution for your initial condition, it can be integrated to numerically. It may take a very long time, but that is a technical detail, dependent on how big a computer we use. – Ján Lalinský May 09 '23 at 11:25
  • It is impossible in general to compute whether or not an initial configuration of the system comes to a singular point within, say, 1 second. In this sense, at least, Newtonian gravity is uncomputable. – Jason Gross May 14 '23 at 19:19
  • That is plausible, I don't disagree. Some initial conditions lead to hard-to-integrate trajectories, but I expect those to be rare. Also, it's due to point singularities or due to collisions of three or more particles. These situations seem to be rare (maybe set of measure zero), and we can imagine a modified model with modified gravity for small distances which will make the integration problem calculable. – Ján Lalinský May 14 '23 at 21:42
  • What do you mean by "set of measure zero" in this context? The set of computable reals already has measure zero amongst the set of reals. Is there some measure you're using on the computable reals? (Does it give the rationals nonzero measure?) (If you have such a measure, it should impose a measure on the set of Turing machines that makes the subset which has undecidable halting behavior have measure zero, which seems like an interesting measure to have in hand.) – Jason Gross May 15 '23 at 23:07
  • But indeed if you have some smooth modification of gravity at small distances, this should make Newtonian gravity computable – Jason Gross May 15 '23 at 23:09
  • I mean this: I expect the set of initial conditions leading to such problem to be of zero measure in the configuration space. Also I expect it to be of zero measure in the space of all practically choosable initial conditions. I don't have a proof. – Ján Lalinský May 15 '23 at 23:47
1

As Sebastian Riese points out, quantum mechanics is computable. Interestingly, classical mechanics is known to be non-computable. If classical mechanics were valid on all length and time scales, then you could construct a so-called "rapidly accelerating computer", which is a computer that accelerates such that the next clock cycle takes half the time to execute as its previous clock cycle. This means that an infinite amount of computations can be done in a finite time. One can then verify the truth of theorems and also verify whether that theorem then known to be true or false is actually provably true or false.

E.g. the Riemann hypothesis can be false, in which case it is provably false (just point of that zero that is not on the critical line), or it is true in which case there may or may not exist a proof for it. A proof is just an argument of finite length that demonstrates that it is true and such a proof may not exist.

The rapidly accelerating computer can simply check out all the zeros one by one and be done with the countably infinite number of zeros in a finite time and then return the result of whether or not they are all found to be on the critical line. Also, it can generate all proofs of theorems using Hilbert's proof checkers algorithm and then check if it ever encounters a proof of a theorem demonstrating that the Riemann hypothesis is true.

But of course, we know that classical mechanics is false. But while quantum mechanics is computable, this is only when you keep track of the unitary evolution of an isolated system. If you perform measurements, then in no-collapse interpretations, one assumes that all possible measurement outcomes are realized, and it's this entire set of measurement results that is computable. What is not computable are the individual results you observe in some particular sector. So, if you repeatedly measure the z-component of a spin polarized in the x-direction, you'll get a random set of measurement result. If spin down is replaced by 0 and spin up by 1, and you put a decimal point ( or is this called "binary point"?) in front then the number between 0 and 1 you get is non-computable.

Count Iblis
  • 10,114
  • 2
    Do you have a reference that shows, that classical mechanics is non-computable? – asmaier Sep 02 '15 at 08:50
  • 1
    @asmaier, I'll look up and include the references in my answer. – Count Iblis Sep 02 '15 at 16:41
  • Classical Newtonian Mechanics is uncomputable; general relativity is computable: https://rangevoting.org/WarrenSmithPages/homepage/church.pdf . (Roughly it boils down to the fact that "divide by r^2" is uncomputable for infinitesimal r; GR has no such division while Newtonian gravity does.) Is there a reference for time evolution in the quantum n-body problem being computable? – Jason Gross May 08 '23 at 02:39
0

Classical Newtonian mechanics is uncomputable because the expression for gravitational force, $Gm_1m_2/r^2$, contains the uncomputable operation $/r^2$. If you cannot bound $r$ away from 0, then you cannot compute division.

General Relativity, by contrast, is computable, because it contains no such division.

See "Church’s thesis meets the N-body problem" by Warren D. Smith for more details.

I am not sure about quantum mechanics. I too would like to know if time evolution in the $n$-body problem is computable. (This blog post and moreover "Lazy Functional Algorithms for Exact Real Functionals" by Alex K. Simpson describe how to compute exact integration of computable real-valued functions. I'm not sure if there's a similar solution to differential equations...)

Edit: the same paper claims that Quantum Mechanics is in fact computable, and cites "Church’s thesis meets quantum mechanics" by Warren D. Smith. I haven't looked at the explanation yet though.

Jason Gross
  • 101