<p>No, a computer cannot perfectly simulate itself in addition to something else without violating basic <a href="http://en.wikipedia.org/wiki/Information_theory">information theory</a>: there exist strings which are not compressible.</p>

<p>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.</p>

CC BY-SA 3.0
2013-08-08T17:48:57.677Z
How do you infer that the universe has more states than the computer?
Trylks
CC BY-SA 4.0
2022-08-21T10:20:58.863Z
A computer in theory (e.g. a Turing machine) can have an unbounded number of 'states' (configurations).
MVTC
CC BY-SA 2.5
2010-11-12T11:42:07.587Z
Ian, can't we think of the universe itself as a machine that does the job?
Kaveh
CC BY-SA 2.5
2010-11-12T17:11:15.540Z
@Kaveh : Even if so, then why should this kind of simulation be interesting ?
Mohammad Alaggan
CC BY-SA 2.5
2010-11-12T20:28:48.330Z
@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**.
Ian
CC BY-SA 2.5
2010-11-12T22:46:56.753Z
@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)
Kaveh
CC BY-SA 2.5
2010-11-13T00:01:20.227Z
@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.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-13T04:14:04.283Z
@M. Alaggan: being useless (in whatever sense) is not a good argument. I am referring to this part of OP's comments: "let's say the computer predicts the moment in time at which it finishes the calculation"
Kaveh
CC BY-SA 2.5
2010-11-12T09:01:15.213Z
2010-11-12T09:01:15.213Z
Ian
<p>I am not sure if this answers your question but I hope it could be meaningful and leads to some insight.</p>

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

<p>Now, reducing that to the halting problem is trivial:</p>

<p>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. </p>

<p>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.</p>

<p>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). </p>

<p>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.</p>

CC BY-SA 3.0
2016-03-05T14:09:19.740Z
-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.
Peter Shor 
CC BY-SA 3.0
2016-03-08T03:50:24.093Z
@Shor that's what I am trying to say, in fact, in the last sentence...
Mohammad Alaggan
CC BY-SA 4.0
2022-08-21T10:33:15.090Z
The answer is wrong, and anyway Turing machines can simulate themselves. A universal Turing machine can simulate any Turing machine for example, including itself. You might think, well then one could run forever if the simulation of itself halts. But the Halting problem considers the problem of deciding if a Turing machine `T` will halt on an input  `x`. Suppose you have a machine `M(<T,x>) { loop if T(x) halts else halt }`. Suppose you want to get your contradiction, so you running `M(<M,x>)`. Your problem is that `<M,<M<x>>` is not equal to `<M,x>`.
MVTC
CC BY-SA 2.5
2010-11-12T11:31:03.447Z
Turing machines are not part of the physical world, they are mathematical objects and need not be physically realizable.
Kaveh
CC BY-SA 2.5
2010-11-12T17:05:06.507Z
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.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-12T22:37:39.870Z
I am not sure, the inputs are more restricted, you might not be able to give the input you want.
Kaveh
CC BY-SA 2.5
2010-11-12T23:56:16.363Z
@Kaveh: Can you elaborate more ?
Mohammad Alaggan
CC BY-SA 2.5
2010-11-13T04:14:53.410Z
Try to make your argument more formal and rigorous for the physical world and you will see what I am talking about.
Kaveh
CC BY-SA 2.5
2010-11-12T03:25:41.403Z
2010-11-12T03:25:41.403Z
Mohammad Alaggan
<p>I guess we could try to see this as a <strong>modelling problem</strong>: 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...</p>

<hr>

<p>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.</p>

<p>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:</p>

<ul>
<li><p>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.)</p></li>
<li><p>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$).</p></li>
<li><p>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!)</p></li>
</ul>

<p>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!</p>

<p>Let's assume that our cellular automaton is <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Cellular_automaton#Totalistic">totalistic</a>. 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.</p>

<p>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$.</p>

<p>(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.)</p>

<hr>

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

CC BY-SA 3.0
2013-08-08T18:01:32.780Z
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.
Trylks
CC BY-SA 2.5
2010-11-12T17:44:38.060Z
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.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-12T19:47:16.477Z
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
Deyaa
CC BY-SA 2.5
2010-11-12T19:47:30.173Z
@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...
Jukka Suomela
CC BY-SA 2.5
2010-11-12T20:52:06.520Z
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.
Ian
CC BY-SA 2.5
2010-11-12T16:59:25.790Z
2010-11-12T16:59:25.790Z
Jukka Suomela
<p>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:</p>

<p>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.</p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/2894/can-a-computer-simulate-itself-as-part-of-a-simulated-world#comment7050_2894">Mark's comment</a>). 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.).</p>

CC BY-SA 3.0
2015-08-17T11:18:18.480Z
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.
mojuba
CC BY-SA 3.0
2015-08-21T02:14:47.620Z
@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.
Juan
CC BY-SA 3.0
2015-08-22T16:08:03.950Z
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.
mojuba
CC BY-SA 4.0
2022-08-21T10:42:25.177Z
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.
MVTC
CC BY-SA 3.0
2015-08-17T09:36:34.657Z
2015-08-17T22:48:17.227Z
2017-04-13T12:32:28.077Z
Juan
<p>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): <a href="http://meaningofstuff.blogspot.com/2016/03/can-computer-or-human-simulate-itself.html" rel="nofollow">http://meaningofstuff.blogspot.com/2016/03/can-computer-or-human-simulate-itself.html</a></p>

CC BY-SA 3.0
2016-03-05T12:32:49.180Z
2016-03-05T12:32:49.180Z
Mihai Voicu
<p>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?</p>

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

CC BY-SA 2.5
2010-11-11T20:18:41.997Z
(The tag is possibly irrelevant, so please feel free to correct)
mojuba
CC BY-SA 2.5
2010-11-11T20:29:07.420Z
In general, if one wants to simulate every atom then one needs a way to compress a lot of state (perhaps via some kind of powerful quantum representation) or the computer will be at least as large as the universe it is simulating.
András Salamon
CC BY-SA 2.5
2010-11-11T20:35:40.667Z
@András Salamon: But there is obviously some redundancy in the Universe: at least all uncompressed data in our computers ;) And the representation of the Computer itself can be more compact within the model, right?
mojuba
CC BY-SA 2.5
2010-11-11T21:10:28.423Z
perhaps not answering your question, but something in spirit of your question, is Scott's musings on cosmology and complexity. http://www.scottaaronson.com/democritus/lec20.html
gabgoh
CC BY-SA 2.5
2010-11-11T22:55:00.927Z
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.
Mark Reitblatt
CC BY-SA 2.5
2010-11-11T23:27:23.557Z
@Mark Reitblatt: uncertainty: for the sake of argument, let's say it is proven wrong and we can take measurements non-destructively. I don't agree with your overhead argument though, it's not obvious at all. When you first hear about a program that prints itself, your first and immediate thought is "impossible". But I'll think about this a bit more, it probably comes down to redundancy in the Universe. Finally, the diagonalization argument: let's say the computer predicts the moment in time at which it finishes the calculation, so you won't have the whole model during calculation.
mojuba
CC BY-SA 2.5
2010-11-11T23:31:27.093Z
@Mark Reitblatt: also, I'm afraid your diagonalization argument will come down to the problem of free will ;) In my opinion, no, there is no "free will", so in principle you, watching the computer calculating the state of the Universe, are part of that Universe and are predictable.
mojuba
CC BY-SA 2.5
2010-11-11T23:34:20.363Z
It seems that it should, at the very least, violate relativity.
Mark Reitblatt
CC BY-SA 2.5
2010-11-11T23:35:49.690Z
@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.
Mark Reitblatt
CC BY-SA 2.5
2010-11-11T23:37:51.143Z
@mojuba perhaps this is a good opportunity to break in the CSTheory chat, instead of playing comment tag.
Mark Reitblatt
CC BY-SA 2.5
2010-11-11T23:42:23.897Z
@Mark Reitblat: no, I'm not assuming that, I'm asking: can a computer simulate the Universe including itself? We don't know if there is enough redundancy in the Universe that a computer would be able to compress and keep information about everything and itself. The computer can be even bigger than the Universe prior to its construction, it doesn't matter as long as it is of finite size. So the question of whether the Universe is predictable or not (uncertainty aside) is still open.
mojuba
CC BY-SA 2.5
2010-11-12T02:19:53.360Z
@Mark, @mojuba, using chat might be a good idea :)
Suresh Venkat
CC BY-SA 2.5
2010-11-12T02:20:48.247Z
If a computer X can simulate the universe, and since the universe includes X, then X can simulate itself, which reduces to the halting problem.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-12T02:30:17.233Z
@M. Alaggan: can you post an answer here and show how exactly that reduces to the halting problem? Seems like a very interesting claim.
mojuba
CC BY-SA 2.5
2010-11-12T11:49:32.243Z
you are assuming that there the future is determined by current state of universe, which AFAIK is against what is accepted in physics. But lets assume that we are talking about a model (universe), you can think of the universe itself as a machine computing the state of universe in the future, and if you some restriction to make sure that we are not using all of the universe, then Ian's argument below shows that it is not possible.
Kaveh
CC BY-SA 2.5
2010-11-12T11:53:06.500Z
ps: I guess by universe you mean the physical world, otherwise I think if you don't specify what you mean by the universe this question is too speculative and argumentative and I don't think it can be answered. So I suggest closing this question with a link to the chat room and moving the discussion to the chat which seems to be more appropriate for discussions.
Kaveh
<computability>
Can a computer simulate itself as part of a simulated world?
mojuba
# Can a computer simulate itself as part of a simulated world?

(Asked by: username_0 on 2010-11-11)

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?

**Tags:** computability

> **Comments:**
> **username_0**: (The tag is possibly irrelevant, so please feel free to correct)  
> **username_1**: In general, if one wants to simulate every atom then one needs a way to compress a lot of state (perhaps via some kind of powerful quantum representation) or the computer will be at least as large as the universe it is simulating.  
> **username_0**: @username_1: But there is obviously some redundancy in the Universe: at least all uncompressed data in our computers ;) And the representation of the Computer itself can be more compact within the model, right?  
> **username_2**: perhaps not answering your question, but something in spirit of your question, is Scott's musings on cosmology and complexity. http://www.scottaaronson.com/democritus/lec20.html  
> **username_3**: 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.  
> **username_0**: @username_3: uncertainty: for the sake of argument, let's say it is proven wrong and we can take measurements non-destructively. I don't agree with your overhead argument though, it's not obvious at all. When you first hear about a program that prints itself, your first and immediate thought is "impossible". But I'll think about this a bit more, it probably comes down to redundancy in the Universe. Finally, the diagonalization argument: let's say the computer predicts the moment in time at which it finishes the calculation, so you won't have the whole model during calculation.  
> **username_0**: @username_3: also, I'm afraid your diagonalization argument will come down to the problem of free will ;) In my opinion, no, there is no "free will", so in principle you, watching the computer calculating the state of the Universe, are part of that Universe and are predictable.  
> **username_3**: It seems that it should, at the very least, violate relativity.  
> **username_3**: @username_0 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.  
> **username_3**: @username_0 perhaps this is a good opportunity to break in the CSTheory chat, instead of playing comment tag.  
> **username_0**: @Mark Reitblat: no, I'm not assuming that, I'm asking: can a computer simulate the Universe including itself? We don't know if there is enough redundancy in the Universe that a computer would be able to compress and keep information about everything and itself. The computer can be even bigger than the Universe prior to its construction, it doesn't matter as long as it is of finite size. So the question of whether the Universe is predictable or not (uncertainty aside) is still open.  
> **username_4**: @Mark, @username_0, using chat might be a good idea :)  
> **username_5**: If a computer X can simulate the universe, and since the universe includes X, then X can simulate itself, which reduces to the halting problem.  
> **username_0**: @M. Alaggan: can you post an answer here and show how exactly that reduces to the halting problem? Seems like a very interesting claim.  
> **username_6**: you are assuming that there the future is determined by current state of universe, which AFAIK is against what is accepted in physics. But lets assume that we are talking about a model (universe), you can think of the universe itself as a machine computing the state of universe in the future, and if you some restriction to make sure that we are not using all of the universe, then username_7's argument below shows that it is not possible.  
> **username_6**: ps: I guess by universe you mean the physical world, otherwise I think if you don't specify what you mean by the universe this question is too speculative and argumentative and I don't think it can be answered. So I suggest closing this question with a link to the chat room and moving the discussion to the chat which seems to be more appropriate for discussions.  

---

## 5 answers

### Answer by username_7 on 2010-11-12. Score: 25

No, a computer cannot perfectly simulate itself in addition to something else without violating basic [information theory](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_6**: username_7, can't we think of the universe itself as a machine that does the job?  
> **username_5**: @username_6 : Even if so, then why should this kind of simulation be interesting ?  
> **username_7**: @username_6 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**.  
> **username_6**: @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)  
> **username_5**: @username_6: 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.  
> **username_6**: @M. Alaggan: being useless (in whatever sense) is not a good argument. I am referring to this part of OP's comments: "let's say the computer predicts the moment in time at which it finishes the calculation"  
> **username_8**: How do you infer that the universe has more states than the computer?  
> **username_9**: A computer in theory (e.g. a Turing machine) can have an unbounded number of 'states' (configurations).  

---

### Answer by username_5 on 2010-11-12. Score: 8

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.

> **Comments:**
> **username_6**: Turing machines are not part of the physical world, they are mathematical objects and need not be physically realizable.  
> **username_5**: 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.  
> **username_6**: I am not sure, the inputs are more restricted, you might not be able to give the input you want.  
> **username_5**: @username_6: Can you elaborate more ?  
> **username_6**: Try to make your argument more formal and rigorous for the physical world and you will see what I am talking about.  
> **username_10**: -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.  
> **username_5**: @Shor that's what I am trying to say, in fact, in the last sentence...  
> **username_9**: The answer is wrong, and anyway Turing machines can simulate themselves. A universal Turing machine can simulate any Turing machine for example, including itself. You might think, well then one could run forever if the simulation of itself halts. But the Halting problem considers the problem of deciding if a Turing machine `T` will halt on an input  `x`. Suppose you have a machine `M(<T,x>) { loop if T(x) halts else halt }`. Suppose you want to get your contradiction, so you running `M(<M,x>)`. Your problem is that `<M,<M<x>>` is not equal to `<M,x>`.  

---

### Answer by username_11 on 2010-11-12. Score: 7

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](https://secure.wikimedia.org/wikipedia/en/wiki/Cellular_automaton#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$?

> **Comments:**
> **username_5**: 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.  
> **username_12**: 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  
> **username_11**: @username_12: And when you construct and program a physical computer, you will certainly change the state of the world inside the boundaries of the computer...  
> **username_7**: 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.  
> **username_8**: 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.  

---

### Answer by username_13 on 2015-08-17. Score: 3

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](https://cstheory.stackexchange.com/questions/2894/can-a-computer-simulate-itself-as-part-of-a-simulated-world#comment7050_2894)). 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.).

> **Comments:**
> **username_0**: 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.  
> **username_13**: @username_0 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.  
> **username_0**: 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.  
> **username_9**: 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.  

---

### Answer by username_14 on 2016-03-05. Score: -1

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>


---

