3

According to the following question, it is likely the physical universe can be simulated on a Turing machine.

Is the universe isomorphic to a universal turing machine?

If so, does this imply phenomena that cannot be reduced to a Turing machine output have a non-physical cause?

Additionally, is observing such phenomena in principle possible?

For example, for phenomenon X we know that it was produced by physical object P. We also know the range of outputs P can compute, if it were Turing reducible, are O. Yet X is not in O. Therefore, we conclude that P has a non-physical component.

Community
  • 1
yters
  • 1,553
  • 11
  • 17

3 Answers3

4

The laws of physics, in particular quantum physics, seem to imply that it is possible to construct a universal computer that could simulate any physical system with arbitrary accuracy, this is called the Turing Principle, see

http://www.daviddeutsch.org.uk/wp-content/deutsch85.pdf

and "The Fabric of Reality" by David Deutsch. The relevant kind of computer is a quantum computer, not a classical computer.

These laws apply to all physical systems, including everything that you can observe and your own brain. So if these laws and the argument that they imply the Turing Principle are correct then it is impossible to observe anything that contradicts the Turing Principle.

There are explanations that are not entailed by the laws of physics but are nevertheless true, such as epistemological explanations. They are usually about some complex phenomenon where it is possible for complex rules to emerge that are not straightforward consequences of the laws of physics but don't contradict them. These emergent explanations can't contradict the laws of physics, because then they couldn't be instantiated in any physical object because the existence of such an object would be forbidden by the laws of physics. Even if the Turing principle is wrong these emergent explanations still could not contradict the laws of physics for that reason.

alanf
  • 7,275
  • 12
  • 18
1

If space-time is finitely quantified, then we end up in Nietche's universe which must eventually simply repeat itself. There are finitely many ultimate positions, and as soon as you get back into one you have already been in, you are looping. Any computation about a finite system can be described by the Turing machine that just considers every available position in the system and checks whether each one happens or not.

But we generally do not believe that. If space (and therefore time) is continuous or otherwise admits infinite potential variation, and if arithmetic of any sort describes how space can be divided, then given Goedel, its ultimate behavior cannot be described by Turing machines.

According to Goedel's Theorem there have to be truths that cannot be verified by first order logic in any infinite system that is consistent and handles arithmetic, no matter how complete the information available about the system. (Flipping it over, if you gave complete information about a system that handles arithmetic, it would turn out to be logically inconsistent.)

The universal Turing machine is just a very clear formulation of the exact system of first-order logic that Goedel was investigating.

In the end, there are strictly more potentially relevant facts in the universe described by any language than there are Turing machines processing that language available to model them. And that does not even consider potential truths that might remain inexpressible in the language itself.

  • This is a very interesting answer. However, one problem that occurs to me is quantum computers are not any more powerful than regular computers. So, this means the physical universe, as we currently understand it at least, is Turing computable. – yters Oct 04 '14 at 01:45
  • @yters How do you get there? Beyond the fact that is not true if space is infinitely divisible, the physical universe also appears to follow Heisenberg's Principle, which prohibits finding precise starting conditions for a model of the physical universe, or any significant part of it. How would this simulation proceed, without starting? –  Oct 04 '14 at 02:25
0

I think Alanf mostly got it, but something additional: while it is likely that anything "computable" is computable by a Turing machine, it is possible that this is not the case. As the Wikipedia article mentions, there are two classes of problems ("BQP" and "BPP" - for the technically inclined, you can look up what they are) that if one is a proper superset of the other, the Church Turing Thesis would be invalidated.

James Kingsbery
  • 5,919
  • 1
  • 18
  • 41