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

# Gödel's Incompleteness Theorem

In this section we lay the groundwork for a simplified version of Gödel's theorem that we prove in the next section. The proof we give 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. They assert the existence of other infinite formal systems including ones that could solve the Halting Problems.

We now informally prove that if we could solve the Halting Problem we 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. This means we can construct a computer program to generate all the theorems deducible from the axioms of the system. We 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 we find an inconsistency we cause the program to halt.

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 proven 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.

For the proof of the Halting Problem we need 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 sequence 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.

The Gödel number of real computer programs as binary images in computer memory is effective. That is we can execute the Gödel numbering to see what the program will do. A universal computer can simulate any other computer including itself.

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 produces different responses to different input parameters. Using this capability of generating an output for each input we can create computer programs that define a function on the integers. For any integer input the program outputs a particular integer result.

We can represent such a 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.

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

Mountain Math Software