Proof of Godel's Incompleteness Theorem

The following is a free translation (with some modifications too) of Cem Say's article Gödel'in Eksiklik Teoremi (i.e. Gödel's Incompleteness Theorem) in the popular mathematics magazine Matematik Dünyasi (i.e. The MathWorld) 2005-1, published every three months.

Actually, the proof we will consider is a proof of Turing's theorem which is essentially the same as Gödel's theorem. You will be convinced to it in the first reading. (If not, try the original proof. Then you'll get convinced as we can't understand a word of it. :) )


First, a program is a finite sequence of commands designed to do specific job. For example
1. Write ”Hello” to sheet A.
is a program.

To run a program is just to follow the commands. So, we can in fact run a program ourselves without using computers.

Now, some programs halt, some don't. The above example halts after accomplishing the first step. But how about this one:

1.Delete sheet A.
2.Delete sheet B.
3.Write ”Hello” to sheet A.
4.Copy everything on sheet A to sheet B.
5.Return to command 4.

Well, this program does not halt -if you don't believe me, try it. Those who took any course on programming know about infinite loops I suppose.

Our sequences begin with the empty sequence. Then, if we use English the second sequence is just “A”. Then comes “B”. and so on. After finishing the alphabet, we continue by “AA”. So, we get every possible sequence once. If you like, you might include numbers and strange symbols too. But it will not matter, because as in the proof of rationals being countable, we get every sequence once.

We are finally able to write Gödel's ...
Theorem: In any formal system where every proven statement is true and where halting and non-halting properties of programs can be proven, there is a true statement which cannot be proven.

What does that mean?
*By formal system, roughly consider any system where we can symbolize things without strange uses rhetorics.
*If I prove a statement, then it has to be true. No discussions, I hope.
*Also, you would like to be able to find out if a program will halt or not, right?
With these assumptions, I'll give you a statement which we can't prove.

Take a formal system S. To avoid confusion I will skip the detail that 'to prove' means 'to prove in the system S '. Off we go !
First consider the following:

2.Copy the text in sheet A to sheet B by taking it between quotation marks.
3.Before the text in sheet B, write ”1.Write” and the text in sheet A and ”to sheet B.” in this order.
4.Put quotation marks before and after the text in sheet B and add “program does not halt.” afterwards.
5.Delete sheet K.
6.If the text in K is a proof of the text in B, HALT.
7.Erase the sequence in K and write the next sequence in the ordering.
8.Return to command 6.

Call this program as Q.

Now, writing “Write Q to sheet B.” before Q, we get a new program, say P. Weird? Let's see what we have.

1. Write
“ 2. Copy the text in sheet A to sheet B by taking it between quotation marks.
3. Before the text in sheet B, write ”1.Write” and the text in sheet A and ”to sheet B.” in this order.
4. Put quotation marks before and after the text in sheet B and add “program does not halt.” afterwards.
5. Delete sheet K.
6. If the text in K is a proof of the text in B, HALT.
7. Erase the sequence in K and write the next sequence in the ordering.
8. Return to command 6.”
to sheet B.
2. Copy the text in sheet A to sheet B by taking it between quotation marks.
3. Before the text in sheet B, write ”1.Write” and the text in sheet A and ”to sheet B.” in this order.
4. Put quotation marks before and after the text in sheet B and add “program does not halt.” afterwards.
5. Delete sheet K.
6. If the text in K is a proof of the text in B, HALT.
7. Erase the sequence in K and write the next sequence in the ordering.
8. Return to command 6.

So, this is our program, called P.
Excuse me, what again? Oh okay, I promised you to give a statement which cannot be proven. There you go.

P program does not halt.


So, I suppose you want me to prove that this statement cannot be proven. Let's first run our program P to see what happens.



First command tells us to write the sequence Q to sheet B. Let's do it. Now here is what we have in sheet B:

2. Copy the text in sheet A to sheet B by taking it between quotation marks.
3. Before the text in sheet B, write “1.Write” and the text in sheet A and “to sheet B.” in this order.
4. Put quotation marks before and after the text in sheet B and add “program does not halt.” afterwards.
5. Delete sheet K.
6. If the text in K is a proof of the text in B, HALT.
7. Erase the sequence in K and write the next sequence in the ordering.
8. Return to command 6.
Now if we go to second command, the same would be written between quotation marks to sheet A.

If we apply third command, what we in B is the same as our program P.

So, the first three commands of our program is just to copy itself to sheet B. Thus, not only living beings, but also programs can breed as you see.

If we now apply the fourth command, the statement in B should look familiar. What we have in B is just:
P program does not halt.

Fifth step doesn't do much. It only makes sheet K clean so that we don't bother our selves if someone else made some scratch on it before.

As you might have realised, we get into a loop in the steps 6,7,8.

In those steps, we get every possible sequence written once and only once, on sheet K. So sheet K will eventually contain every candidate as a proof for the text in sheet B.

In short, this program P halts if only if the statement which says that it will not halt (Program P does not halt.) is provable. Let's see if our program halts or not:

If program P halts, then the statement “Program P does not halt.” is provable. So it will not halt; which then implies that the statement is true but cannot be proven.
The proof is finished.