# Is Physics Computable? [closed]

Is it possible for a Turing machine to simulate physics accurately?   For the problem of reals, I was thinking of the following:
For each real,
$2^1, 2^2, ...., 2^n, ...$ memory cells store the first real.
$3^1, 3^2, ...., 3^n, ...$ memory cells store the second real.
$...$
$...$
$...$
$m^1, m^2, ...., m^n, ...$ memory cells store the $m-1^\text{th}$ real.

So if the Turing machine had arbitrarily large speed could it render a perfect simulation of our Universe?

Bonus:
If an ordinary Turing machine cannot simulate physics, then in addition to the above, The machine as the following property.
Let $t$ represent one time step.
In first $1t$ it performs $1$ primitive operation.
In next $.5t$ it performs $2$ primitive operations.
In next $.25t$ it performs $4$ primitive operations.
$...$
In next $2^{-n}t$ it performs $2^n$ primitive operations.

Operation resets every 2t.

My question is whether it is possible in principle for an infinite state Turing machine to capture this universe. Whether it is possible for this universe to be simulated within the limits of computation. It is not necessary for the machine that simulates the Universe to be physically realisable. The machine may e.g have infinite computational speed.

Assuming certain real constants would be needed in the computation, the above was to suggest a method for a computer to manipulate real numbers without truncation.

## closed as off-topic by sammy gerbil, StephenG, Jon Custer, John Rennie, knzhouDec 2 '17 at 12:56

• This question does not appear to be about physics within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

• It's pretty obvious that if you need the full set of real numbers to do physics with perfect accuracy, a Turing machine would never finish even reading a real number, so no to your first question in that case. Whether you need the full set of real numbers to perfectly simulate physics is unknown as far as I know, though. – Chris Dec 1 '17 at 8:34
• I'm voting to close this question as off-topic because it is asking about computing with real numbers, it is not asking about physics. I do not see where physics comes into this question. – sammy gerbil Dec 1 '17 at 10:30
• @sammygerbil you're quite wrong about "nothing to do with physics", although the op's approach is a bit naive. I'm formulating a more typical approach as we speak, which should appear as an "answer" (or as a "reply", anyway) soon. – John Forkosh Dec 1 '17 at 10:33
• @sammygerbil Well, yeah, but the question starts with the words "simulate physics accurately" but then devolves to a more prosaic issue, which my comment (maybe too generously:) characterized as "naive". However, see my now-posted answer below, where I try to address "simulate physics" in a more foundational sense. And like my first comment above says, "lots has been written about this". And I can probably dig up some more arxiv references, but don't have them handy offhand. Nevertheless, I guarantee you that many exist, and that the subject is indeed foundational physics related. – John Forkosh Dec 1 '17 at 11:09
• @JohnForkosh I do not doubt that much has been published on the question in the title. My objection is that it is not clear what the OP means by it, other than the issue of computing to arbitrarily high accuracy. What is the question about physics here? The only issue which the OP identifies is not about physics. What physics issue(s) are you thinking of? – sammy gerbil Dec 1 '17 at 11:43

Any real computer must be a physical system and so must obey the laws of physics. So in any real computer, the speed at which information can be transmitted is less than or equal to the speed of light.

However, a universal computer can simulate a physical to any finite accuracy:

https://people.eecs.berkeley.edu/~christos/classics/Deutsch_quantum_theory.pdf

I can see one immediate obstruction to simulating physics is the Nielsen-Ninomiya theorem.

Discretising the Standard Model (on a lattice) in order to simulate it is not entirely possible without dropping some assumptions.

Dr David Tong makes the argument in an essay this is also why it’s not plausible for the universe to be some simulation.

The counter-argument I see is to say that the Standard Model is an effective theory and its inability to be simulated on a lattice due to the dichotomy between fermions of different chilarity is simply a consequence of that.

In other words, one could argue that perhaps a ‘final thory’ does not suffer from such a no-go theorem.

• One could in principle conceive a clever way to simulate the universe than just using a lattice. – Rexcirus Dec 3 '17 at 8:50
• A final "theory" of everything might be non-computable even if a colleciton of theories for each domain (GR + QFT) might be computable. – Croolsby Apr 3 at 2:26

In addition to my comment above referencing https://arxiv.org/abs/1312.4456 consider the following more typical approach...

Let $\left|\psi\right>=\sum_{i=1}^\infty a_i\left|e_i\right>$ where the $\left|e_i\right>$ are a set of basis vectors spanning some infinite-dimensional Hilbert space, and the $a_i\in\{0,1\}$ are $\left|\psi\right>$'s eigenvalues in that basis. Note that all the $a_i$'s are either $0$ or $1$. So that means an $\left|e_i\right>\left<e_i\right|$ measurement of $\left|\psi\right>$ always (with probability $1.0$) gives you that corresponding $0$ or $1$ outcome.

Okay, so computability-wise, you've heard of the halting problem, right? If not, see https://en.wikipedia.org/wiki/Halting_problem (and a zillion other google hits) for details. So consider an enumeration of all possiible computer programs, e.g., by their Godel numbers (see https://en.wikipedia.org/wiki/G%C3%B6del_numbering and other google hits for details).

And now, prepare (I dare you to prepare:) state $\left|\psi\right>$ such that $a_i=1$ if the program whose Godel number is $i$ halts; otherwise $a_i=0$ if that program doesn't halt. So, bingo, $\left|\psi\right>$ solves the halting problem. Since that's impossble, such a state can't be prepared, measured, computed, etc. It might "spontaneously arise" in nature, but it's inaccessible to humans by any conceivable process.

>>Note<<: I read this argument somewhere, sometime, some article, but don't recall the source or author. Somebody please post a comment with the citation if you know it.

>>Edit<<: in his comment above, @sammygerbil asks me, "What physics issue(s) are you thinking of?" Okay, so here's one concrete specific issue...

In his book, "Quantum Theory: Concepts and Methods", on page 50 Asher Peres says https://books.google.com/books?id=pQXSBwAAQBAJ&pg=PA50&lpg=PA50 "Principle of Superposition Any complex vector, except the null vector, represents a realizable pure state."

Well, sorry Asher, but the above argument demonstrates a non-realizable complex vector. So this should be a sufficiently physical issue to merit at least some discussion here.

• The OP's explicit question is whether physics can be simulated- essentially whether the time evolution of an arbitrary state is computable. It's not clear what the connection between being unable to produce a particular state and being unable to simulate time evolution is. – Chris Dec 1 '17 at 11:14
• @Chris please see comments below original post between SammyGerbil and me. Rather than have Sammy just close the op's question, my answer's more a reply to the broader question whose formulation is suggested by those comments, hopefully addressing a more on-topic and interesting physical issue. You're absolutely correct that my answer's not a spot-on answer to the op's exact question. – John Forkosh Dec 1 '17 at 11:20