Next: The Halting Problem Up: Mathematical structure Previous: Cardinal numbers   Contents

# Gödel's Incompleteness Theorem

This section lays the groundwork for a simplified version of Gödel's theorem that is proven in the next section. The proof is for the Halting Problem. Gödel proved that any formal system that defines the primitive recursive functions must be either incomplete or inconsistent. In particular one could not prove from within the system that the system itself was consistent even though the question could be formulated within the system.

The consistency of any finite formal system is equivalent to the Halting Problem for a particular computer program that is easily constructed from the axioms of the system. Gödel's result is more general than the Halting Problem because it is not limited to finite formal systems.

All formal systems that humans can write down are finite. However the idea of an arbitrary real number seems so obvious that mathematicians claim as formal systems a finite set of axioms plus an axiom for each real number that asserts the existence of that number.

Given a solution for the Halting Problem one could solve the consistency problem for finite formal systems. The idea of the proof is simple. A finite formal system is a mechanistic process for deducing theorems. Thus one can construct a computer program to generate all the theorems deducible from the axioms of the system. One can add to this program a check that tests each theorem as it is generated to see if it is inconsistent with any theorem previously generated. If an inconsistency is found the program halts.

Such a program will halt if and only if the original formal system is inconsistent. For the program will eventually generate and check every theorem that can be deduced from the system against every other theorem to insure no theorem is proved to be both true and false.

Crucial to the proof of the unsolvability of the Halting Problem is the ability to assign a unique integer to every computer program. Assigning a unique number to each element in a class of objects is known as Gödel numbering. It is trivial to see this is possible today when we Gödel number anything stored in computer memory including computer programs. In Gödel's time this aspect of his proof was very complex and its construction was a stroke of genius.

In a computer's memory programs are represented as a very long sequence of zeros and ones. Computer memory is almost always binary with two possible states at each storage element. These `bits' (elements that can store 0 or 1) are organized in groups of eight known as bytes. When computer programs are stored in memory as bytes they are Gödel numbered. The numbering depends on the architecture of the computer running the program.

The proof of the Halting Problem depends on a Universal Turing Machine capable of simulating every possible program. Almost any computer is a Universal Turing Machine provided it has some way to reference a potentially infinite storage device. For example it might request that the next or previous disk be loaded from a set of disks that can grow without limit. The requirement in Gödel's proof that the formal system be powerful enough to embed the primitive recursive functions implies that the system must be able to model a Universal Turing Machine.

A Universal Truing Machine has two inputs. One is s computer program that can be executed on a particular computer. The other input is a complete description of the computer that can execute the program. The Universal Truing Machine uses the description of the computer to perform exactly the same operations that the real machine would do if it were executing the program. Of course this simulation will be much slower than executing the program directly on a machine designed for that programming language.

Computer programs often have parameters. Whenever a web site asks you to type in information you are entering a parameter to a computer program. Programs typically produce different responses to different input parameters. Using this capability of generating an output for each input one can create computer programs that define a function on the integers. For any integer input the program outputs a particular integer result.

Represent this function as where is the program is the input and the value of is the output the program produces with input . There may be no output for some inputs.