2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ physics.stackexchange.com/q/72396 $\endgroup$ – user81619 Aug 31 '15 at 20:49
  • 2
    $\begingroup$ (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. $\endgroup$ – Sebastian Riese Aug 31 '15 at 22:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Prof. Legolasov Sep 1 '15 at 1:08
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Do you have a reference that shows, that classical mechanics is non-computable? $\endgroup$ – asmaier Sep 2 '15 at 8:50
  • 1
    $\begingroup$ @asmaier, I'll look up and include the references in my answer. $\endgroup$ – Count Iblis Sep 2 '15 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.