The New Turing Omnibus Chapter 5 Gödel's Theorem

The Chapter

We began by discussing the "Big Picture" from Tom's notes, focussing on the ideas of David Hilbert in 1920 to formulate mathematics on a solid and complete logical foundation.

• Hilbert's Program
• Hilbert's second problem

With this context in mind, we discussed how Kurt Gödel proved Hilbert's program was impossible and the possible ramifications of this discovery. We wondered how this related to the halting problem and Bertrand Russell and Alfred North Whitehead's idea of logicism.

We were careful to first understand that Gödel's findings (and Hilbert's ideas) were specifically about formal systems and James walked us through an example system from Douglas Hofstadter's "Gödel, Escher, Bach: an Eternal Golden Braid":

We discussed what it means for a formal system to be sound and what it means to be complete, using the aforementioned example pq- system to solidify our understanding.

We revisited the Predicate Calculus chapter to view it as a formal system and how it is both complete and sound.

With this in place, we then looked at arithmetic as a formal system and walked through a proof that 1 + 1 = 2 using the axioms given in the chapter.

With less than an hour remaining, we attempted to walk through Gödel's theorem, first discussing how every string can be encoded as a Gödel number and can therefore be subject to arithmetic itself. Chris demonstrated his Gödel number encoder/decoder:

Joel uses Chris' Gödel number encoder/decoder

Finally: Tom led us through the rest of the theorem, explaining how any sufficiently powerful system (such as arithmetic) cannot be complete as it will always be able to express a string that cannot be proven but is true.

Retrospective

• There was general consensus that this was one of the most difficult chapters we've encountered so far and greatly appreciated Tom's preparation;
• We discussed the possibility that this topic might have been better spread over several meetings but how this was at odds with our desire to keep each meeting self-contained (in an effort to attract more attendees);
• There was concern that the difficulty of this subject matter (and amount of mathematics) would scare away potential attendees;
• We reiterated our preference for having meeting shepherds (viz. at least one member of the group having read the chapter and done some preparation);
• Once more, we encouraged using material outside the book to aid discussion and to have meetings that aren't about The New Turing Omnibus at all.

Thanks

Thanks to Daniel and Geckoboard for hosting, to Tom Stuart for shepherding, to James for his examples on the whiteboard and to Chris for his Gödel number generator.