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

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 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_in_ZFC http://en.wikipedia.org/wiki/List_of_statements_undecidable_...