I'll be teaching one quarter of CS431 in semester 2 this year; the topic is:

Reading Gödel's Theorems

In 1929 Kurt Gödel (at the age of 23) presented his PhD thesis, proving the completeness theorem for the first-order predicate calculus. However, he is better remembered for what followed when, in 1931, he presented his incompleteness theorems, displaying the limitations of formal systems for arithmetic. As well as being of fundamental mathematical importance, these theorems also laid the groundwork for the results of Church and Turing a few years later that gave birth to Computer Science.

In these lectures we'll be reading the actual theorems (in translation - the originals were in German), particularly On formally undecidable propositions of Principia Mathematica and related systems.

Recommended texts

• Collected Works: Volume I: Publications 1929-1936 by Kurt Gödel, Oxford University Press, 1986.
  This has all of Gödel's papers from his "early" period, including the completeness and incompleteness theorems, in German and in English translation. The introductions to the papers are worth reading in themselves.
• From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, by Jean van Heijenoort, Harvard University Press, 2002.
  This is a set of original papers covering the development of modern logic up to the incompleteness theorem.
• The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions by Martin Davis, Dover Publications, 1984.
  This is another set of original papers, this time starting with the incompleteness theorem and going forward to cover the main papers from the foundations of Computer Science.

• Engines of Logic: Mathematicians and the Origin of the Computer by Martin Davis, W. W. Norton & Company, 2002.
  This presents a light and readable narrative history of the development of modern Computer Science "from Leibniz to Turing". (This book has also been published under the title "The Universal Computer").
• Gödel's Proof by Ernest Nagel and James Newman, NYU Press, 2008.
  A short rehearsal of the main points of the incompleteness theorem without getting bogged down in too much detail.
• Godel, Escher, Bach: An Eternal Golden Braid by Douglas R Hofstadter, Penguin, 2000
  This is a very roundabout treatment of the topic with an AI sub-theme; amusing if you have time on your hands.

• Wikipedia: Gödel's Incompleteness theorems
• Stanford Encyclopedia of Philosophy: Kurt Gödel