Is the universe isomorphic to a universal turing machine?

Question

I often think about problems that require an understanding of the very essence of computation and its inherent limitations. So, my questions are as followed:

• Is the universe isomorphic to a universal turing machine?
• Is the universe isomorphic to a universal quantum computer?
• What evidence do we have within our universe to support an answer to such a question?
• What corollaries follow from a universe that is or is not isomorphic to a universal turing machine (or universal quantum turing machine)?
• Is this question really answerable, and what is the current literature on this subject?

I'm mostly interested in the implications and corollaries that follow from a universe that is or is not isomorphic to a turing machine (or universal quantum computer) and the insights that it would provide us with, about the nature of computation.

Answer 1

I disagree with Michael.

From all we know, there is no indication that the universe could not be properly simulated in a Turing machine, even if it is infinite.

You have to accept though, that a Turing machine would only stochasically approach the outcome of the universe. Computing the future is out of the question as far as we know (because of the stochastic nature of things), yet simulating it without any way for somebody living in the simulation to know is likely.

This 'likely' hinges on the question whether the infiniteness of the universe is one of the kind of the integer numbers (then the answer is yes) or of the real numbers (then it is no), because as you might remember even though both are infinite, integers and rational numbers are countable and the Turing machine could thus make progress.

Physics seems to indicate that it might be the integer kind (particles cannot be split indefinitely as numbers, time and space have limits to their resolution) for all we care.

The costs though are tremendous, a turing machine would likely spend trillions of cycles just simulating the interaction of any two of most basic particles to a degree of stochastic realism.

My understanding of computing tells me that simulating the universe needs an efficient way of doing an NP problem and that a Turing machine is not efficient in this regard.

Answer 2

I'm afraid I don't find the question terribly interesting, and I don't think it yields any information about the nature of computing.

That being said: Tom Stoppard had a character raise this idea in his play "Arcadia" (without recourse to a Turing machine-- the character was speaking in the early 19th century):

"If you could stop every atom in its position and direction, and if your mind could comprehend all the actions thus suspended, then if you were really, really good at algebra you could write the formula for all the future; and although nobody can be so clever to do it, the formula must exist just as if one could."

And, of course, that's trivially true, if the universe is made up of (properly atomic) "atoms" which possess no changing attributes other than a position and a direction. Unfortunately, current research in physics indicates that things are a fair bit more complicated than that.

So, let's generalize: if the universe is comprised of a finite number of (otherwise) unchanging atomic elementary particles, and if a finite number of types of transformations are permitted to each particle, given the total state of all particles at one moment in time, one could theoretically derive a formula to derive the state for the next moment-- if, and only if, you believe that the transformations and operations thus described are determinate.

In other words, if there is any true randomness (and not merely pseudo-randomness) involved, you're shit-out-of-luck. And, at present, we have absolutely no way of knowing whether or not that is the case, so the whole matter is purely idle speculation (which is why I find it not to be an interesting question).

Now, what does the above tell us about Turing machines, or the nature of computation? Precisely nothing that we didn't already know. The definition of what is computable remains unaffected.

Thus, the answer to your bullet point questions are:

• We have no way of knowing.
• Not much, with the current state of physics.
• A universe that is isomorphic to a Turing machine is determinate, and finite.
• It's pure speculation, and to the best of my knowledge, is not treated in the literature in any depth, for precisely that reason.

Answer 3

• to the technical question 'is the universe -isomorphic- to a universal turing machine': for an isomorphism, there must be a mapping in both directions.
  • The universe can certainly simulate a turing machine (and a universal one) because people have created simulators...except for (as danportin commented) the requirement of an infinite tape. The latter is unknown to be possible. We can use a deterministic features of the macroscopic properties of objects in the universe (billiard balls or tinker toys) because theoretically a deterministic TM can compute the same things as a nondeterministic TM.
  • Can a conceptual UTM simulate the universe? That depends on what we take the rules of physics to be. With Newtonian mechanics, deterministic atoms and chemical properties,and an initial state of all, I think so (but it will be quite intractable). Presumably all chemical , biological and psychological behavior would follow (the rules might be hard to extract though).

Note: this isn't really an isomorphism but a bisimulation, which is really what you want (it's the equality of two kinds of mathematical processes rather than static mathematical objects).

• as to quantum machines, a lot of research (in computational complexity theory) has gone into showing that quantum machines can be simulated by classical machines (with an unknown overhead, possibly exponential, but also possibly only a constant, this is related to the P != NP problem). The inherent non-determinism of quantum mechanics might pose some difficulties with this simulation.

But non-technically, it is mostly a fascinating hypothesis to suggest that the universe is a computer. Mostly because it is just a way of thinking about physical rules. A physical law is conceptually the same as a copmutation (a computation of what it just did). Stephen Wolfram (the personality behind Mathematica and "A New Kind of Science") is a great proponent of this view (and he greatly emphasizes the 'is' part).

As to what follows from 'is' is that we should be able to do exact prediction (given enough time and space resources for the simulation) say of weather patterns. If 'is not', I still don't think it is of much difference. The limitations of time and space are roughly the same import as limitations of exactness.

Answer 4

Depends on what type of universe sought. If this universe contains undecidable propositions (like ours does), then no. That would get you in a lot of trouble very quickly. Even if one were to construct a TM, it doesn't mean the TM is going to cover the entire case. So you must rule out things such as the induction rule which is key to the TM to work if you really wanted to do this. As others have suggested, it must be finite and deterministic to ensure the decidability of the TM. Overall this question is not an important one, since it cannot be done effectively even if you were given a finite number of objects due to the Halting Problem, in relation to the existence of arbitrarily infinitely many undecidable statements. Removing these statements is impossible.

So to answer your question, no you cannot if it contains propositions about itself (the consistency of it's own being, which is related to several paradoxes). Encounter a single paradox, your TM can't decide the universe. If one were to only be measuring say spaces and points of atoms, but nothing in regard to people and what people are capable of (better known as mathematical intuition), then it is only possible if the universe is CLOSED.

Answer 5

The question relative even to quantum computers depends upon the notion of isomorphism. If you expect a quantum computer to model reality within an arbitrary precision, you do not believe the Heisenberg Principle, which has a great deal of empirical support.

Running a quantum simulation could not copy the universe, because a large number of decisive events seem to be necessarily random. So the only defintion of isomorphism you could really use would be that the quantum simulation would produces something that the world 'could' be if all the randomness aligned perfectly. And I think that is kind of the definition of a simulation.

So the question needs a clearer distinction between simulation and isomorphism in order to be potentially true. But with a naive one, it is false.

Answer 6

There is some difficulty with the idea "the Universe=computer". This computer can do one step from one state to another, but why should the machine make such a step at all? Why she does not stick forever at one state? The logical schema is inherently static; it cannot say anything about the time and the change. For any particular computer the problem of change does not matter - this computer is realized somewhere as a physical entity, so nobody care of where the change comes from. In the case when the Universe is declared to work as a computer and nothing more, this problem starts to be too serious and it cannot be ignored.

Apparently, the computer model being blind towards the time implies - there is something beyond its scope; this "something" pushes the world to change in time, some phenomena start to be, and others disappear. In other words - the model is incomplete. For my opinion, this kind of universal Pythagorean project should fail (as all other kinds, probably).

Answer 7

For one, with the current state of our technology we cannot count the number of atoms (or whatever the smallest known particles are nowadays) which exist in the universe. Therefore, there are uncountably many atoms in the universe (no, that's just a pun). It does no matter whether there is a countable or uncountable amount. The universe is isomorphic to a Turing Machine.
Why? As said above by danportin, the universe can only be isomorphic to the universe if there is an infinite number of things, as the tape is infinite (he also says the amount of states of a TM must be infinite, but that is false). We do, however, need a finite amount of input. If there is an infinite number of things, that can get quite tricky, but luckily it is a given that every thing is built from atoms (or the smallest known particles, I just stick with atoms).
As there is a finite number of atoms, we can proceed. The next important matter is the finite amount of states. To achieve the isomorphism there need to be only a finite amount of reactions possible between the atoms. Impossible, one might say, but remember that the infinite tape has nothing to do with the amount of states: We can just put all the possible outcome (may or may not be an infinite amount) on the tape, and only deal with the reactions between atoms in the states.
The amount of reactions (between atoms) is finite. The amount of possible actions in reading and writing is finite (go left, right, nowhere, write a finite set of tokens). Therefore, as a finite amount times a finite amount will lead to a finite amount, we have a finite amount of states in which we define the universe.
(and remember kids, a TM is only defined by its states, not by the amount of tape it has)

For two, a quantum computer can only calculate a 2^n number of outcomes, therefore a finite number of outcomes, per tick. So, if the universe is neverending, we would need to let the quantum computer run endlessly before it can calculate the universe. Assuming we have the time for this, we can conclude there could exist a quantum computer isomorphic to the universe, but if you want an answer I suggest reading The Hitchhikers Guide to the Galaxy.

For three, I assumed the universe was built up from atoms. If this assumption is disproved somewhere the next aeons, then we need another kind of support to answer these questions.

For four: Hitchhikers Guide to the Galaxy (again!). Or at least nothing non-fictional for now.

For five: No idea, this was just a hunch.

Answer 8

The answer lies in understanding the human mind in relation to the ontological system that lies within it. We oscillate from an atomic point, in a constellation of synthetic concepts. I believe there is an ontological algorithm in the mind that we are only now evolving to see. As a man with autism, I am already in the embryonic stages of this development, although I do not feel that in my short life span, that I will fully realize my mind in its net.

If you consider any equation in mathematics, it becomes clear that they all have a single foundation in the human mind. For example: let us consider the simplest equation of all, and that is 1 + 1 = 2. This notion is only possible because the mind is operating around a constellation of systemizing concepts such as, consistency, extension, aggregation, adding, traction, extraction, and configuration, to name just a few.

If you consider these concepts as modes, you can see clearly that they are all connected in one constellation in the mind when we apply our minds to every single subject that has natural merit. These concepts are part of a single innate unit, and they are the seeing eye within our mind. If we can figure out all the axims that hold these concepts to a smooth motion, we will have defined the ontological algorithm.

The ontological algorithm is where you will find similarities to the turning machine. Yap.

Answer 9

*Is the universe isomorphic to a universal turing machine?*

Probably closer to an abstract finite state machine, but conceptually a turing machine has the power to computationally represent the universe.

Is the universe isomorphic to a universal quantum computer?

Not sure.

What evidence do we have within our universe to support an answer to such a question?

Go:dels Incompleteness Theorem claims that the universe must be computationally incomplete because it cannot contain the axioms to describe itself, the universe is information and must be contained in something and that container can't be described inside the universe. A singularity paradox.

What corollaries follow from a universe that is or is not isomorphic to a universal turing machine (or universal quantum turing machine)?

A theory of everything could be possible, or everything inside of a bounds we could logically call a universe.

Is this question really answerable, and what is the current literature on this subject?

This is a question of logic within information theory, and type hierarchy. The universe must be a type of information, therefore an automaton with rules and axioms describing itself, with paradoxes of information along the way.

Answer 10

If the universe were isomorphic to a universal turing machine so would our understanding which is part of the universe. However, Searle’s Chinese Remainder Argument suggests that this is not possible and so we can conclude that the universe is not isomorphic to a universal turing machine since there exists a part of the universe that is not.