-2

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.

Tobi Alafin
  • 121

3 Answers3

4

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 system to any finite accuracy:

https://www.cs.princeton.edu/courses/archive/fall06/cos576/papers/deutsch85.pdf

alanf
  • 11,359
  • 1
  • 16
  • 33
2

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.

2

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.

JamalS
  • 19,600