I was recently arguing with a friend over whether or not our universe could contain a perfect simulation of itself. I've got a feeling that this question has already been discussed on LW, and possibly discussed to the point of being answered and agreed upon. This has been a fun problem to try and think through, and I'd appreciate feedback/comments of the general form of my reasoning.

Can our universe contain a perfect simulation of itself?

It seems like what counts as a perfect simulation hides most of the complexity of this problem. For now, I'm going to hand wave a bit and say a perfect simulation is anything that can asses the truth value of a arbitrary proposition about the universe.

Simulating the universe in "hard mode" (when you are within the universe) seems to be, or at least be similar to, the problem of naturalized induction. From reading only that paper, I don't get a sense that those working on naturalized induction are trying to do anything as crazy as perfectly simulate the universe.

Creating a perfect simulation has a strong feeling of mathematical impossibility to it. Here's a chain of logic to try and find an easier proposition to disprove.

1. If you cannot create an accurate "snapshot" of the entire universe, you cannot have a system that accurately models the evolution of the universe's state over time.

2. If it is impossible for a snapshot of the universe to exist within the universe, then you can't create a snapshot.

3. If a binary string of length n called the universe, cannot be completely encoded into a sub-string of length m where m < n, then in general, a universe cannot contain a snapshot of itself.

2-3 is a jump that I think is valid, yet I'd have a hard time defending. It comes from a sense of, "If we can't solve the simplified binary string version, we won't be able to solve the harder version."

Here's a "solution" to the sub-string encoding problem that feels like cheating:

Suppose $m$ is half the length of $n$ . Let the sub-string be the exact same sequence as the bits from $m+1$ to $n$ . Use an encoding scheme like "The sub-string tells you the bit pattern for the non sub-string part of the universe, and the sub-string bit pattern is described by the sub-string bit pattern itself."

The part that feels like screwy is the "and the sub-string bit pattern is described by the sub-string bit pattern itself." While, yes, if the above scheme was used, then an "outside observer" who was aware of the encoding scheme could look at only the sub-string an be able to recreate the entire universe string.

But if we are relying on an outside the universe observer to just know what encoding pattern is being used, that's just offloading the work to outside the universe! My sense is that if we have to specify any part of this encoding outside of the universe, it can't be meaningfully considered to be an encoding.

Another "solution" that feels like cheating:

Let the sub-string be any bit pattern. Then say, "Done". This counts as an encoding because there logically exists some Turing Machine that when fed the sub-string as input, spits out the entire universe string.

This can be handled with an argument from Scott Aaronson's "Why Philosophers Should Care About Computational Complexity" (which was mostly over my head). From the part about Computationalism and Waterfalls:

In my view, there is an important lesson here for debates about computationalism. Suppose we want to claim, for example, that a computation that plays chess is “equivalent” to some other computation that simulates a waterfall. Then our claim is only non-vacuous if it’s possible to exhibit the equivalence (i.e., give the reductions) within a model of computation that isn’t itself powerful enough to solve the chess or waterfall problems.

So it would only be meaningful to say that a sub-string encodes the universe string if the Turing Machine that did the decoding was less complex than the universe string itself.

Putting that all together, here's my shot at what's need for a Minimum Meaningful Encoding:

If a sub-string of the universe string is said to encode the entire universe string, then:

1. There must exist a Turing Machine which requires less than n bits to specify that takes the sub-string as input, and spits out the universe string.

2. The bit pattern of the above Turing Machine must be present somewhere in the universe string.

I still believe that it's impossible to have such a universe string, but that seems to come mostly from fuzzy intuitions I'm having trouble pining down. This is also the point where I wish I'd already taken a class in compatibility and logic.

For Feedback:

1. Was the reduction to the sub-string problem reasonable?

2. What do you think of the proposed Minimum Meaningful Encoding? (Shannon's source coding theorem seemed like it might have been useful, but I couldn't parse it)

3. Does this entire chain feel misguided, or valid but not rigorous enough + unfinished?

4. How might you prove or disprove the original claim?