### Speculations on Gödel's Incompleteness Theorems, the Halting Problem, and The Simulation Argument

© iStockphoto.com / David Marchal |

## Kurt Gödel

Kurt Gödel was a mathematician whose 1931 seminal work was the proof that all formal mathematical systems of sufficient complexity are necessarily incomplete. In other words, there are mathematical statements within these systems that are true, but which can never be proven within the system itself. Gödel proved this by showing that statements can be created which state that they can never be proven within the formal system. While these statements are in fact true, they can't be proven so - if they could, by definition they would not be true!

An analogy is the sentence "This sentence is false". This sentence cannot be a true statement, because if it were, we would have to believe what it states - that it is false. Similarly, it cannot be a false statement, because if it were, it would be true.

## Nick Bostrom

Nick Bostrom is the Director of the Future of Humanity Institute at Oxford who has authored a Simulation Argument. Essentially, it states that:

Unlessone of the following statements is true,

- The human species goes extinct before reaching a posthuman stage.
- Humans never become capable of running (or desire to run) computer simulations of their history.
then we are most likely living in a simulation now.

## Turing Machines and the Halting Problem

The halting problem is a question in computability theory which asks if an algorithm can be found that decides whether a program (a Turning machine) will finish, or run forever, once given a description of such a program and a finite amount of input. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for *all* possible program-input pairs cannot exist. The ideas within Gödel's incompleteness theorems are quite similar to those presented by the halting problem.

## Speculations

Suppose that the universe that we live in is in fact a simulation, and it is being simulated by the equivalent of a Turing Machine. What are the ramifications of the halting problem and Gödel's incompleteness theorems in this regard? The "Scientific and technological approaches" section of the Simulated Reality entry in Wikipedia has some interesting speculations on software glitches, Easter Eggs, limitations on processing power, and the Heisenberg uncertainty principle.

## Related Posts

Gödel's First Incompleteness Theorem and Gödel Numbering

Past, Present and Future

*Chris K. Haley, NestedUniverse.net. Get free RSS or email updates here.** *