-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
    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 01 '17 at 08:34
  • Lots has been written around this kind of conjecture. Answer is "No" (physics not computable). See, for example, "Uncomputability and Physical Law", Seth Lloyd, https://arxiv.org/abs/1312.4456 –  Dec 01 '17 at 10:25
  • 7
    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 01 '17 at 10:30
  • 3
    @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. –  Dec 01 '17 at 10:33
  • @JohnForkosh The question in the text appears to be about the accuracy of computation, eg :If a computer had an arbitrarily high speed, could it compute real numbers to an arbitrarily high precision? The OP has not made any connection between computing and physics - eg determinism, discreteness, thermodynamic constraints. ... Of course you can bring physics into the OP's broad title, as Seth Lloyd does, but that does not appear to be the issue which the OP is asking about. – sammy gerbil Dec 01 '17 at 10:56
  • 2
    @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. –  Dec 01 '17 at 11:09
  • 2
    @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 01 '17 at 11:43
  • Possible duplication of Are We Living in a Simulated Universe? or Simulate the universe? or How many bits are needed to simulate the universe? or Is simulating the entire universe possible? or Computability of physics or Computation theory and the simulation argument etc – sammy gerbil Dec 01 '17 at 11:57
  • 1
    @sammygerbil I've put an "edit" at the bottom of my answer to discuss your question, "What physics issue(s) are you thinking of?" –  Dec 01 '17 at 13:08
  • I think https://scicomp.stackexchange.com may be a better match for this question. – peterh Dec 02 '17 at 20:16

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
  • 7,424
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.

  • 3
    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 01 '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. –  Dec 01 '17 at 11:20
  • " Since that's impossble, such a state can't be prepared, measured, computed, etc."

    This conclusion is not correct. It's impossible for a Turing machine to solve the halting problem. This does not imply that it's impossible for this state to be prepared.

     – Onye Apr 08 '22 at 18:56
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,254
  • One could in principle conceive a clever way to simulate the universe than just using a lattice. – Rexcirus Dec 03 '17 at 08: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 03 '19 at 02:26