# Computation theory and the simulation argument

1. Can physical states be treated as information (strings over some alphabet)?

2. If (1) is true, isn't this a trivial conclusion that the universe can be simulated by a Turing machine or a cellular automaton or any other computational model, given that differential equations that determine the evolution of physical states (the bits in digital physics) are simulated by the transition function of the Turing machine?

-
Possible duplicates: physics.stackexchange.com/q/759/2451 and links therein. –  Qmechanic Jul 27 '13 at 4:49

Can physical states be treated as information (strings over some alphabet)?

There is a distinction between a state and a vector (see this mo question), but disregarding that, we can clearly approximate a vector to any desired precision using a finite-length string. I doubt that anyone can say whether the rounding errors involved grow uncontrollably or something, from the point of view of a person who is being simulated in the approximation itself.

There seems to be quite a large literature in academic philosophy on the "simulation argument," starting with Bostrom 2003. A certain amount of analysis has also been done by physicists. Beane 2012 says there would be observable glitches. Aaronson 2002 says that such a simulation "cannot be made compatible with both special relativity and Bell inequality violation." Bostrom has counterarguments on his web page (see #15).

If I'm living in a real universe, then I can (given some technological advances) build a quantum computer that can factor large numbers faster than any Turing machine. But of course, "faster" is a problematic term, since a simulated universe doesn't have to run in real time.

There is also the issue of the amount of memory you have available. A Turing machine is an abstraction that has an infinite amount of memory available. In reality, if we're living inside a simulation, whoever's running the simulation might be presumed to have finite computational resources, e.g., resources significantly less than the total resources that could be harnessed within what we presume to be our own observable universe. Given such resources, it seems unlikely to me that one could use a classical computer to simulate a quantum-mechanical universe of a comparable size. On the other hand, I don't see why this hyper-advanced civilization has to use classical rather than quantum-mechanical computers.

So in summary: (1) I don't think your choice of a Turing machine, with its classical nature and infinite memory, as the model of computation is necessarily appropriate. (2) Even assuming we could agree on an appropriate model of computation, I think the answer to the your question would be a matter of controversy.

Aaronson, Book Review: 'A New Kind of Science,' http://arxiv.org/abs/quant-ph/0206089

Beane, Davoudi, and Savage, Constraints on the Universe as a Numerical Simulation, http://arxiv.org/abs/1210.1847v2.pdf

Bostrom, Are You Living In a Computer Simulation? Nick Bostrom. Philosophical Quarterly, 2003, Vol. 53, No. 211, pp. 243-255, http://www.simulation-argument.com/

-

even if (1) is true you cannot conclude (2). The reason being that differential equations are only an approximation to physical laws. Even if highly unlikely, the laws of physics could be non-computable, and only computable as an approximation. (see Wolfram's book "A new kind of Science"). In conlusion, there is no evidence that the evolution of the universe can be computed by a Turing machine (my personal opinion is that it likely is)

-
Actually, (2) may not be unlikely. See: Marian B. Pour-El, J. Ian Richards, "The wave equation with computable initial data such that its unique solution is not computable" dv. Math., Vol. 39 (1981), pp. 215-239 Peter Shor posted this reference in this answer physics.stackexchange.com/a/5618/26076 –  WetSavannaAnimal aka Rod Vance Jul 27 '13 at 3:39

If you think to classical bits, the answer is no. Physical states obeys Quantum Mechanics (or Quantum Field Theory), so a "state" is nothing that a complex "vector" on some basis. Conservation of information (Unitarity) says that the "norm" of the vector is constant.

For instance, suppose a isolated state $S$, at time $0$ defined by :

$|S(0) \rangle = a|0 \rangle + d |1 \rangle |1 \rangle$,

and at time $t$ by :

$|S(t) \rangle = c|0 \rangle + d|1 \rangle + e |0 \rangle |0 \rangle + f |1 \rangle |1 \rangle$

where $a, b, c, d, e, f$ are complex quantities.

Here, the states $|0 \rangle,|1 \rangle$ are $1$-particle state, while the states $|0 \rangle |0 \rangle, |1 \rangle |1 \rangle$ are $2$-particle states. Morevoer, all these states are normed and orthogonal to each other, so they make a basis.

Conservation of information means only that the "norm" of the vector (or state) $S$ is conserved between times $0$ and $t$, that is $$|a|^2+|b|^2 = |c|^2+|d|^2+|e|^2+|f|^2$$

So, you are not working with an alphabet, but with complex quantities which can vary, but have constraints due to the conservation of information (unitarity)

-