Philosophy of Everything

A virtual machine is a common example of simulation. It can take the description of a (virtual) "computer" state and continue the execution from that point on. You can simulate a huge computer given a computer with more memory than the virtual machine, although it might be way slower. However, such virtual machine does not answer the problem because it normally simulates a computer with less memory. The question is, can a computer to simulate a virtual computer that has the same capabilities as itself? Before answering this, let's exclude some trivial (forbidden) cases of "simulations": A calculator will always do exactly what it does, it will be identical with itself, we will not call this a simulation of itself. Copying the exact state of another identical computer in a "twin brother" will not be considered simulation. Starting 2 identical computers with the same input will not be considered like one is simulating the other.

We have this requirement: "Create the smallest program that will print the full text of the play Othello by William Shakespeare". I should warn you that the requirement hides a trick and you will hate the solution. The program does not need to run efficiently. Actually, it does not need to run in reasonable time. It just has to be very short. And to be proven to answer the requirement, eventually... No external random source is allowed and no input from user.

A friend told me once that we are living in an Universe full of unprovable truths. He was referring to the Gödel's incompleteness theorems . Without being very formal, this says that there are many mathematical propositions that might be true but we cannot prove them using a computer program or any predictive way of checking, no matter how huge amount of time we can spend. We can find the proof for some, by luck, but for most of them we cannot find either a proof or disproof. In fact this "unprovable" propositions are way more many than the provable propositions. The provable propositions are like the set of natural numbers "N" and the unprovable propositions are like the set of real numbers (R).