Explaining Gödel's Incompleteness Theorem to a Twelve Year Old

Great observation; as an undergrad, noticing this suddenly made GIT (which was taught to me by a mathematician in all its intricate detail) seem a lot less scary.

Indeed, the proof of the halting problem is much easier to sketch than the proof of Godel's incompleteness theorem (which the OP doesn't even attempt). So here he goes: a proof sketch of the halting problem for 12 year old programmers.

Suppose that somebody wrote us a program that can check whether another program will loop indefinitely or eventually halt when run on a particular input:

    bool halts(string program, string input){ 
       // halting checking code that checks 
       // whether program's main function
       // halts when given input
       // returns true or false
    }

For example:

    string program = 
      "void main(string foo){" +
      "  if(foo[0] == 'a'){ return; }" +
      "  else{ while(true){} }" +
      "}";
    
    halts(program, "abc") // returns true
    halts(program, "bar") // returns false

Now we can write the following program:

    bool halts(string program, string input){
       // same halting checking code as above
    }

    void main(string program){
      if(halts(program, program)){
        while(true){ }
      }
    }

Note that this is a perfectly valid program. halts() is supposed to work on any program, including a program that happens to contain the source code of halts(). We can just reuse the code that the person gave us and copy-paste it here.

Now the question is: what will our halts() function say about this program, when given its own code as input? In other words: what will the following code print?

    bool halts(string program, string input){
       // same halting checking code as above
    }
   
    void main(){
      string program = 
        "bool halts(string program, string input){" +
        "   // same halting checking code as above" +
        "}" +
        "void main(string program){" +
        "  if(halts(program, program)){" +
        "    while(true){ }" +
        "  }" +
        "}";

      print(halts(program,program));
    }

There are just 2 possibilities: either this program prints true, or this program prints false (if this program never terminates then halts() has a bug).

Case 1: suppose halts(program,program) returns true.

If the halts function is working correctly, that means that when we actually run the code in `program` with `program` as its input, it will halt. But now lets see what actually happens. When we run the main() function in `program` with `program` as its input, it first checks `if(halts(program,program))`. Well, we already assumed that halts returns true, so control flow will go inside the if block to the infinite loop. But that means that halts lied to us!

Case 2: suppose that halts(program,program) returns false.

Now a similar argument holds. run the code in `program` with `program` as its input, the condition of the if statement will be false, and the main function will terminate. So even though halts(program,program) returns false, the program actually terminates. It lied again!

As you can see, no matter what halts returns, it cannot tell the truth about the program we constructed. Hence it is impossible to fill in the missing code in halts() so that it will work correctly.

Thank god-you are one of the rare individuals who can use the English language to explain a complex idea. The hideous bias I have encountered in the "hi tech" world is because my mind works like yours and I have always found your talent to be rare gem. Why anyone would think the reduction of complexity into simple terms means putting it into "12 year old" terms is beyond me. So I remain an exile.

Exactly. An "explain like I'm twelve" for Godel's Incompleteness Theorum itself would revolve around the idea of self-referential statements (such as 'the set of all sets which don't contain themselves', or 'the barber of Seville shaves everybody who doesn't shave themselves').

In my understanding, Godel created a system that mapped statements to numbers, and then looked at the numbers that represented statements like 'this statement is provable' and found a way to show that the equivalent number had a property that wasn't provable.

Is that so? I think you mean that this is an explanation of the theorem, but not of a proof of the theorem.

Haven't read that one, but I try to re-read Nagel and Newman's at least once a year: http://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/081475837...

One thing I love about N&N is that it's short (160 pages) and the paperback is cheap ($7.65) so that I have no compunctions in lending it out.

Yeah. It should be something like "any sufficiently strong theory". But that's still a justifiable simplification. Other parts of the explanation are totally incomprehensible to someone who doesn't already know what's he talking about.

I don't think there is a contradiction, but someone please correct me if I'm wrong. Godel's theories are something I've recently begun trying to wrap my head around.

Godel's completeness theorem proves the equivalence of logical implication and deducibility. Logical implication being the formal definition of what it means for a collection of sentences (axioms) to logically imply another sentence (theorem); deducibility being the method with which a working mathematician would like to use to show logical implication (i.e. any proof you've ever read in a mathematical textbook).

Incompleteness, on the other hand, shows that there are some true sentences that cannot be deduced from any set of axioms (and therefore, by completeness, are not logically implied by any set of axioms).

This is my understanding after having spent a few weeks reading Enderton's "A Mathematical Introduction to Logic." If I am misunderstanding this, I would love input (so please comment). Godel's theorems are something I'm very anxious to wrap my head around.

The Completeness Theorem (in one of its equivalent forms) says that every consistent first-order theory has a model, linking syntax and semantics. It doesn't tell you any thing about how you would go about justifying that a theory is consistent.

People hoped that some logical system capable of formalizing real mathematics would be able to justify its own consistency. Godel's Incompleteness Theorem (and stronger, related results) imply that any system capable of formalizing real mathematics (or even a very weak subset of it) can not justify its own consistency, requiring an appeal to a stronger system. Obviously, that raises the obvious question of why that stronger system is consistent. There are constructive proofs (due to Godel himself, Gentzen, and others) of the consistency of Peano Arithmetic, but by the Incompleteness Theorem they must all be non-finitary in some fashion, no matter how slight.

However, there are some limits to this understanding of Godel's Incompleteness Theorem. There are theories that are strong enough to prove (and perhaps more importantly, state) their own consistency but not strong enough to formalize diagonalization. If PA is consistent, then there is a theory that can state and prove its own consistency as well as the consistency of PA. The trick is that provability can be formalized on the basis that subtraction and division are total functions, whereas diagonalization requires addition and multiplication to be total functions. These theories can prove that subtraction and division are total functions, but not addition and multiplication.

Yeah that was a tangent. The author got a bit overexcitrd and overshot.

Also not the OP's reply (paraphrased): "Thanks, but I wasn't interested in the understanding logic or math. I am thinking more along the lines of [metaphysical gobbledygook]. What can you say about that? "

I think the CH was used just to provide an example of an undecidable statement, not actually demonstrate something weird about the incompleteness theorem. Since the CH cannot be proven to be true or false within ZF (or ZFC), then you are correct, appending it would just provide an addition axiom.

His example is to do with the first theorem. There are two incompleteness theorems. The one most people think of when they hear Godel is the second even though the first is key. The first one has to do with decidability - for any given statement from a theory is it algorithmically verifiable given the axioms of the theory? If you can encode the natural numbers with its axioms and pose <handwave>certain relations</handwave> with that encoding then no. This ties Godel's work to Turing. http://www.scottaaronson.com/democritus/lec3.html

Here is a list of undecidable statements in ZFC: http://en.wikipedia.org/wiki/List_of_statements_undecidable_...

The situation with Goedel sentence (let's call it G) is actually not very different. As neither G nor negation of G is provable, you could also say that it contains extra information, and add negation of G as a new axiom to PA, just like you could add CH to ZF.

If you do that, you could wonder what your new arithmetic looks like. This is actually very interesting question. Since "not G" says basically "it's not true that there's no proof of me", or, more specifically, "it's not true that there's no number that represents the proof of me", it's clear that "not G" asserts the existence of a certain "natural" number being the proof of G, which is not one of the natural numbers we know (since no "regular" natural number represents the proof of G). In our new universe there are "natural" numbers that you cannot reach by counting. Because of that, one can construct many different nonequivalent "implementations" (models) of PA + not G, which are necessarily different than the standard implementation of artihmetic we know (1, 2 = S(1), 3 = S(S(1)), ..., n = S(S(...S(1)...)), with + and *).

What is interesting about incompleteness theorem is that no matter if we add arbitrarily large number of axioms to PA, or even infinite number of axioms generated by computer program we write, the resulting system will still be incomplete, and each will have its own (many of them, actually) Goedel sentence.

It depends on whether the meaning of "exists" is, I think. By analogy to the finite universe (always dangerous in logic), it is like saying "we live in a sphere of diameter 4. We have proven (due some hypothetical variation of relativity) that all matter in the universe will never be able to move more than distance 1 from the original center of our existence. An object of length 3 can be mathematically described, but is theoretically impossible to construct." Or something.