I've read through Godel Escher Bach, and I loved it, but I never really felt like I had a handle on Incompleteness theorem. Scott Aaronson had a throwaway 2 li

I've read through Godel Escher Bach, and I loved it, but I never really felt like I had a handle on Incompleteness theorem. Scott Aaronson had a throwaway 2 line 'proof' (not technically) of the theorem that intuitively clicked for me: >First, though, let's see how the Incompleteness Theorem is proved. People always say, "the proof of the Incompleteness Theorem was a technical tour de force, it took 30 pages, it requires an elaborate construction involving prime numbers," etc. Unbelievably, 80 years after Gödel, that's still how the proof is presented in math classes! >Alright, should I let you in on a secret? The proof of the Incompleteness Theorem is about two lines. The caveat is that, to give the two-line proof, you first need the concept of a computer. >When I was in junior high, I had a friend who was really good at math, but maybe not so good at programming. He wanted to write a program using arrays, but he didn't know what an array was. So what did he do? He associated each element of the array with a unique prime number, then he multiplied them all together; then, whenever he wanted to read something out of the array, he factored the product. (If he was programming a quantum computer, maybe that wouldn't be quite so bad!) Anyway, what my friend did, that's basically what Gödel did. He made up an elaborate hack in order to program without programming. The rest here: http://www.scottaaronson.com/democritus/lec3.html http://www.scottaaronson.com/democritus/lec3.html