« April 2008 | Main | August 2008 »

July 2008

July 31, 2008

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

My last post talked about Kurt Gödel's incompleteness theorems. Gödel used a technique called Gödel numbering to prove his first incompleteness theorem. This numbering system allows mathematical statements to talk about other mathematical statements - in other words, it is a meta-mathematical system. Essentially, Gödel numbering can be thought of as a function that assigns a unique integer to every mathematical statement in a formal language.

For example, consider the arbitrary symbol mapping below. Note that symbol mappings do not have to be unique. In fact, an infinite number of these mappings can be created which still give unique Gödel numbers to all possible correctly formed formulas.

Symbol Mapping
+ 1
0 2
x0 3
^ 4
1 5
x1 6
* 7
2 8
x2 9
= 10
3 11
x3 12
) 13
4 14
x4 15
( 16
... ...

In general,

# 3 * # - 2
x# 3 * (# + 1)
3 * # + 1

Note that multiple, infinite sequences of symbols can be mapped by interleaving them within the sequence.

For example, the formula

   (x0 + 1) = x02 + 2x0 + 1

maps to the following sequence of integers:

   16, 3, 1, 5, 13, 10, 3, 4, 8, 1, 8, 7, 3, 1, 5

In order to encode this sequence, and therefore the original statement, as a unique Gödel number, the following function can be used

   GödelNumber(y0,y1,y2,...) = 2y0 * 3y1 * 5y2 * 7y3 * 11y4 * ... * primenxn

with subsequent terms following the sequence of prime numbers. The fundamental theorem of arithmetic guarantees that any natural number greater than 1 can be written as a unique product of prime numbers. Therefore, the original sequence of integers can be recovered uniquely through factorization. Our example statement can be mapped to the number



Note that the number is broken into two parts for presentation only - it is in reality a single 95 digit number. Mathematical proofs can, in a similar manner, be represented by sequences of Gödel numbers called Gödel sentences. Now assume that all the Gödel sentences which represent proofs that are true can be listed in a sequence:

  a, b, c, d, ...

Encode the statement "this mathematical proof does not appear in the list of Gödel sentences" as a Gödel sentence. Can it be found in the list? Assume that it can. If so, it must be false, because it states that it is not in the list. Therefore, it must in fact never appear in the list. This means that it is fact a true proof, and since it does not appear in the list, our list of "all true mathematical proofs" is necessarily incomplete.

Related Posts

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

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


July 22, 2008

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

Fermi Paradox
© 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:

Unless one 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.


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. Subscribe Get free RSS or email updates here.