21
$\begingroup$

Let's say you build a computer that will calculate the state of all atoms in the Universe at certain future point in time. Because the Universe is, by definition, everything that exists (and anything that interacts with the rest), it also includes the computer that you are building. Can you calculate the state of all atoms in the Universe using your computer, including the atoms of the computer itself?

If such a computer is not possible for some other theoretical or practical reason, then what is it?

Improve this question
$\endgroup$
16
  • 2
    $\begingroup$ perhaps not answering your question, but something in spirit of your question, is Scott's musings on cosmology and complexity. scottaaronson.com/democritus/lec20.html $\endgroup$
    – gabgoh
    Nov 11, 2010 at 21:10
  • 8
    $\begingroup$ There's a couple of reasons why such a computer couldn't exist inside the physical universe: Heisenberg's uncertainty principle limits the precision of measurement, so your computer would necessarily have to use an approximation. The second problem is that simulation requires overhead. But since you're simulating the universe, you have no room for overhead. In fact, you need negative overhead! The third, and perhaps simplest complaint is that your computer is subject to diagonalization: I simply look up what it predicts I will do 10 seconds from now, and do something different. $\endgroup$
    – Mark Reitblatt
    Nov 11, 2010 at 22:55
  • 1
    $\begingroup$ It seems that it should, at the very least, violate relativity. $\endgroup$
    – Mark Reitblatt
    Nov 11, 2010 at 23:34
  • 5
    $\begingroup$ @mojuba No, free will isn't a sound objection. That's circular reasoning. You're assuming the universe is predictable by your computer, therefore I can't violate your computer's prediction. $\endgroup$
    – Mark Reitblatt
    Nov 11, 2010 at 23:35
  • 2
    $\begingroup$ @mojuba perhaps this is a good opportunity to break in the CSTheory chat, instead of playing comment tag. $\endgroup$
    – Mark Reitblatt
    Nov 11, 2010 at 23:37

5 Answers 5

Reset to default
25
$\begingroup$

No, a computer cannot perfectly simulate itself in addition to something else without violating basic information theory: there exist strings which are not compressible.

Here's the simplest possible proof: suppose the computer has a total of $N$ possible states, and suppose there is something outside of the computer in the universe, so the universe has at least $N+1$ possible distinct states. With zero overhead, each state of the computer can correspond to a state of the universe, but since the universe has more states than the computer, some states of the universe will map to the same state of the computer, in which case the simulation will not be able to distinguish between them.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Ian, can't we think of the universe itself as a machine that does the job? $\endgroup$
    – Kaveh
    Nov 12, 2010 at 11:42
  • $\begingroup$ @Kaveh : Even if so, then why should this kind of simulation be interesting ? $\endgroup$
    – Mohammad Alaggan
    Nov 12, 2010 at 17:11
  • 3
    $\begingroup$ @Kaveh we can always think of a computer or system as "simulating" itself by just being itself, but all I'm saying is that it cannot simulate itself and something else. $\endgroup$
    – Ian
    Nov 12, 2010 at 20:28
  • $\begingroup$ @M. Alaggan: Well, you can say the same thing about a simulation that is not faster than waiting up to that point and then observing the result? (look at the comments below the post by OP) $\endgroup$
    – Kaveh
    Nov 12, 2010 at 22:46
  • $\begingroup$ @Kaveh: I think that we might be trying to avoid discussing the possibility of such computer, by arguing it would be useless. I am not sure which comment you are referring me to. $\endgroup$
    – Mohammad Alaggan
    Nov 13, 2010 at 0:01
8
$\begingroup$

I am not sure if this answers your question but I hope it could be meaningful and leads to some insight.

Assume that there is a turing machine $X$ that can simulate every atom in the universe including itself, it then necessarily can simulate itself.

Now, reducing that to the halting problem is trivial:

Let $X$ take a turing machine $M$ as its input and decides whether it halts or not by simulating the universe (since $M$ is included in the universe), then do the opposite (e.g. $X$ halts if $M$ does not, and loops forever if $M$ halts). Then $X(X)$ demonstrates a contradiction.

Essentially this means that the best $X$ can do to decide whether $X$ halts or not is just by running itself (i.e. let the universe work its way), so simulating the universe doesn't give an advantage.

The same applies when you want the state of the universe after $t$ time. Since $X$ can not decide if it will halt within $t$ time or not within $t$ time (same argument), then it will let it to the universe to do it. Trying to simulate the universe doing it, can not reduce the time you'll take to decide. And if deciding how the universe will look like in $t$ time takes more than $t$ then the simulation will diverge (as $t$ goes to infinity).

This leads to the conclusion that only useful simulator that decides how the universe will look like in $t$ time must take exactly $t$ time, i.e. by letting the universe work. This simulator is then indeed the trivial simulator.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Turing machines are not part of the physical world, they are mathematical objects and need not be physically realizable. $\endgroup$
    – Kaveh
    Nov 12, 2010 at 11:31
  • $\begingroup$ That's even better because then their realization (computers) has more limits. However if you just translate the work "Turing machine" in my post to "computer" I think it will still work. $\endgroup$
    – Mohammad Alaggan
    Nov 12, 2010 at 17:05
  • $\begingroup$ I am not sure, the inputs are more restricted, you might not be able to give the input you want. $\endgroup$
    – Kaveh
    Nov 12, 2010 at 22:37
  • $\begingroup$ @Kaveh: Can you elaborate more ? $\endgroup$
    – Mohammad Alaggan
    Nov 12, 2010 at 23:56
  • 3
    $\begingroup$ -1: This answer is just plain wrong. Even if a computer could simulate itself, it couldn't tell whether it would halt, because to do that it would have to simulate itself for an infinite amount of time. $\endgroup$
    – Peter Shor
    Mar 5, 2016 at 14:09
7
$\begingroup$

I guess we could try to see this as a modelling problem: how can we re-phrase the question so that it becomes computer science and not physics? I'll try to give a simple, concrete example of how we might try to do this, to get things started...

Let's replace the "universe" by something that is very discrete and simple (and finite!). Let's say that our universe is a finite cellular automaton. In particular, the whole world $W$ is an $n \times n$ grid.

Assume that the initial configuration of the world $W$ is arbitrary. Now the question seems to be the following: Can we choose a strict subset $C$ of $W$ ("computer"), and an initial state of $C$, that satisfies the following conditions:

  • We do not change the initial state of $W \setminus C$. (That is, we just "build our computer $C$", without tampering the world outside it.)

  • Then we can run any number of steps of the cellular automaton (the whole world $W$, including $C$ and any interactions between $W \setminus C$ and $C$).

  • We can read the current state of the world $W$ by merely inspecting $C$. (That is, $C$ must be a "simulation" of $W$. Note that we must be able to read the state of whole $W$, not only $W \setminus C$. In a sense, $C$ must be able to simulate both its outside and its inside!)

Now, is this doable? It might be tempting to use a counting argument (there are more states in $W$ than in $C$) and say that it is impossible. But this is not necessarily the case!

Let's assume that our cellular automaton is totalistic. Then what we can do is we simply let $C$ be the right half of our grid $W$, and let the initial configuration of $C$ be a mirror image of $W \setminus C$, so that everything is symmetric. That's it.

Start the automaton and see what happens. The current state of $W$ will always be equal to the state of $C$ + its mirror image. That is, merely inspecting $C$ is enough to tell what is the state of whole $W$.

(Of course here the computer interacts with $W$, and affects the future state of $W \setminus C$. But that's what happens in the real world, too.)

Now it might be interesting to see if there is a non-trivial answer to this question. For example, which CAs admit computers that have size smaller than half of $W$?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Don't you think the same symmetry argument makes any n-fold symmetry trivial, not just half ? Also you are assuming that the "observer" knows that $W \ C$ is a mirror (a function) of $C$, what if the function is different than the mirror function ? It is related then to the Kolomogrov comlexity of the universe and the computing power of the observer. $\endgroup$
    – Mohammad Alaggan
    Nov 12, 2010 at 17:44
  • $\begingroup$ If the initial configuration of $C$ be a mirror image of $W ∖ C$, so you have overwritten the internal state of $C$ ! so $C$ doesn't simulate itself $\endgroup$
    – Deyaa
    Nov 12, 2010 at 19:47
  • $\begingroup$ @Deyaa: And when you construct and program a physical computer, you will certainly change the state of the world inside the boundaries of the computer... $\endgroup$
    – Jukka Suomela
    Nov 12, 2010 at 19:47
  • $\begingroup$ I would argue that this is not a proper simulation since it can only simulate a small subset of the universe's states. Even if you're allowed make arbitrary changes to the "real" universe when setting the state of the computer, you shouldn't just be limited to simulating the universe's actual state. $\endgroup$
    – Ian
    Nov 12, 2010 at 20:52
  • $\begingroup$ What is a "CA"? Also I'm not certain about the totalistic nature of the universe, but quantum entanglement is an interesting property in this sense. E.g. Consider the computer is everything: it predicts the future as fast as time passes. Can it be less than everything so that we have a part of the universe out of the computer? Yes, it can be everything minus entangled particles. So there it is, the computer is already working and doing a good job. $\endgroup$
    – Trylks
    Aug 8, 2013 at 18:01
3
$\begingroup$

Here is a simple (non-formal) proof. Say is the year 2115 and I have a 100 year old computer that I'll call Mac, and a state of the art supercomputer called God. God can easily simulate and predict Mac, until I do the following:

First, I attach a webcam to Mac and point it towards God's screen. Then, I run on Mac a program that, in an infinite loop, stores every number detected in God's screen and generates and displays a number that is not in the list of stored numbers. Finally, I ask God to show me the number that Mac is going to be showing one minute from now. Whatever number God shows, Mac will produce and show a different one, so God will be unable to give a correct answer.

This is equivalent to the fact that if a supercomputer predicts me, whatever she tells me I'll do, I'll be able to do the opposite (as in Mark's comment). Also, this holds regardless of the process the supercomputer uses to predict the future (simulation, traveling to the future and coming back, asking an oracle, etc.).

Improve this answer
$\endgroup$
4
  • $\begingroup$ In other words, God affects the reality while computing the future and thus it can't compute the future. On the other hand, if we fully isolate God from this Universe, it won't be able to read the state of the Universe. I agree, it sounds like a proof. $\endgroup$
    – mojuba
    Aug 17, 2015 at 11:18
  • $\begingroup$ @mojuba Actually, if God would be fully isolated and could somehow read the state of our universe (for instance, if our universe was a simulation running in God's mind) then he could predict our future. But if he somehow informs us about our future, then that would stop being an accurate prediction since we (or a program) could just do the opposite. And for the same reason he couldn't predict his own universe, including himself. $\endgroup$
    – Juan
    Aug 21, 2015 at 2:14
  • $\begingroup$ the question with the simulated world is, whether it can be considered a fully isolated, self-contained Universe or not. The simulation machine keeps the states of all particles of the simulated world and models their interaction according to some laws of physics. If God interferes in any way, it would mean the laws will be broken somewhere (because if they are not broken, then that's not God's interference). At least that kind of interference means the simulated Universe is not isolated and so the original question does not apply to it, I think. $\endgroup$
    – mojuba
    Aug 22, 2015 at 16:08
  • $\begingroup$ I believe it is true that you can't simulate the universe in its entirety faster than the universe evolves itself. But that doesn't mean you can't simulate the universe. $\endgroup$
    – MVTC
    Aug 21, 2022 at 10:42
-1
$\begingroup$

A finite computer cannot simulate itself, in contrast to a Turing machine that has an infinite tape and can simulate any other Turing machine. It is, however, possible to simulate any computer on a similar computer, but you need a little more memory than the "simulated" one (like in a virtual machine): http://meaningofstuff.blogspot.com/2016/03/can-computer-or-human-simulate-itself.html

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.