Message(s) of the day:

Notice the revised, easier schedule.

Venue:

• Room: PH 225
• Time: MW 11:30-12:50

Instructor: Kevin T. Kelly.

• E-mail kk3n@andrew.cmu.edu.
• Phone: X8567.
• Office: 135 K BH
• Office hours: After class on Mon, 11:00-12:00 on Tues. or by appointment through e-mail.

Grader: Nicola De Pisapia

Texts:

• Main: Epstein and Carnielli, Computability, Computable Functions, Logic, and the Foundations o Mathematics
• Useful: Cutland, Computability

Requirements:

• Undergraduates:
• 100% exercises. Some exercises may be worth more than others.
• Graduates:
• 70% exercises
• 30% final project (e.g., a cl ean writeup of Gödel's theorem, an application, or a historical paper.)
• Exercises are to be turned in at the end class on the date they are due. Note that assignments and exercises are listed in the course outline below.
• Late Policy: 10% penalty per day late.
• The course outline may be modified during the term, so please consult the online copy regularly.

Description:

The class concerns two closely related subjects, uncomputability and incompleteness. In fact, the theory of computability was developed prior to the advent of digital computers in order to fully unpack the significance of Gödel's thoerem. A unique feature of our text is that it emphasizes the underlying philosophical issues while providing a fully rigorous presentation of Gödel's celebrated incompleteness results.

Depending on time, we may consider related topics in computability and the elements of NP-completeness theory, which was developed along lines closely analogous to the theory of computability.

Course Goals:

To understand Gödel's theorem and the elements of computability theory, with some sense of their connections and underlying motivation.

Ideally, understanding mathematics involves the following elements:

1. What is the proof of the claim?
2. What is the high level "strategy" of the proof (how would you explalin it to a friend at lunch?)
3. What extra information can be extracted from the proof?
4. Could the proof be strengthened to yield a stronger result?
5. If not, what are the couterexamples to the obvious strenghtened versions?
6. Where do attempted proofs of the negation break down?
7. How could anybody have found he proof?
8. Why were people interested in the result at the time?
9. Why weren't they interested in it before?
10. What philosophical moral does the result carry, if any?

Course Outline

I. Background

1. (Jan 11) Paradoxes: Chapter 1, exercises 1-6, p. 6, due Jan 20.
2. (Jan 13) Platonism and Finitism: Chapter 2, exercises 1-3, p. 17, due Jan 20.
3. (Jan 13) Review of Basics: Chapters 3and 4. exercises 1-3, p. 20, due Jan 20. Note: in exercise #3 on p. 20, the formula should be grouped as (a + b sqt(2))/(c + (d sqt(2)).
4. (Jan 20) Proofs: Chapter 5. exercises 1-6, p. 37, due Jan 25. These are a bit more challenging.
5. (Jan 25) More Proofs: exercises at the end of the linked syntax tutorial. Due Feb 1.
6. (Jan 27, Feb 3) Some set theory: exercises in linked set theory tutorial. Due Feb 8.
7. Infinity (Feb 8): Chapter 6. exercises 1-10, p 41, due Feb 15. These will be important later. Especially pay attention to #4 and #5. Note that "nonnegative" in #8 should be "nonpositive".
8. (Feb 10) Hilbert's "On the Infinite": Chapter 7. No exercises.

II. Computability

1. (Feb 10) Formal models of computability: Chapter 8, exercise 5, p. 71, Due Feb 22. Chapter 9, exercises 1.a, 5, 7 (and make the encoding bijective!), 8, 9, p. 83. Due Feb 22.
2. (Feb 15) Church's thesis: Chapter 10 No exercises!
3. (Feb 15) Primitive recursion: Chapter 11, exercises 1-9, p. 96. This stuff will all be used later in Gödel's theorem, so be especially careful (due Feb 24).
4. (Feb 22) More primitive recursion: Chapter 11, all exercises on p. 104 except 18.a and 22. (Due March 1).
5. (Feb 24) Elementary functions: Chapter 12: Prove theorem 1, p. 109. This result is important since it tells us how easy to compute our encoding of tuples is. (Due March 8)
6. (March 3) Partial recursive functions: Chapters 14, 15, exercises 1-7, p. 127. (Due March 15).
7. (March 8) Partial recursive indices: Chapter 16, exercises 1-10, p. 136. (Due March 29).
8. (March 10, 15) Recursive enumerability: Chapter 17, exercises 1-6, p. 143. (Due March 31).

III. Gödel's incompleteness theorem

1. (March 29) Overview of Gödel's theorem: Chapter 20, no exercises.
2. (March 29) Arithmetic: Chapter 21, exercises 3, 10, 11, 12, 13 on p. 186. (Due April 5)
3. (March 29) Representability: Chapter 22, exercises 2-7, p. 200. (Due April 12).
4. (April 12) Gödel's incompleteness theorems: Chapter 23, exercises 3a, 3b, 4, 5, 6 (Due April 19)
5. (April 14) Unprovability of consistency and the demise of Hilbert's program: Chapter 24, exercises 1.a, 1.b, 2. Be sure to save some time for 2. Bonus: raise your grade on an earlier exercise by correctly doing exercise 3. (Due April 26).

IV. Complexity theory.