Incompleteness and Undecidability

Number	Lecture Date	Subject	Reading in Kleene's IM	Homework
1	April 1	History and Introduction	Chapters II and III	Assignment 1
2	April 3	Examples of First-order Theories	Chapter IV	Assignment 2
3	April 8	Peano's Arithmetic, non-standard models, Skolem's paradox	Chapter IV	No assignment.
4	April 10	Primitive Recursive Functions	Chapter IX, sections 43-46 and Chapter XI, pages 270-274	Assignment 4
5	April 15	The Halting Problem	no reading in Kleene	Assignment 5
6	April 17	Turing Machines, Intro and examples Movie shown in class of a hobbyist's working Turing machine	Chapter XIII, sections 67 and 70	Assignment 6
7	April 22	Primitive recursion is Turing computable	no reading in Kleene	Assignment 7
8	April 24	Computation by Turing Machines	no reading in Kleene	Assignment 8
9	April 29	The recursion theorem The lambda calculus	no reading in Kleene	Assignment 9
10	May 1	Proof and Computation	Chapter VIII,sections 38-40	Assignment 10 (revised)
11	May 6	Peano Arithmetic and Primitive Recursion	Chapter VIII,section 41	Assignment 11
12	May 8	Arithmetization of Syntax	Chapter IX	Assignment 12
13	May 13	The First Incompleteness Theorem	Chapter VIII, section 42	Assignment 13
	May 15	We worked on some problems from Assignment 11 in class
14	May 20	Rosser's Theorem, the length of proofs, Robinson's Arithmetic, and Church's theorem	Section 42, Theorem 29 is Rosser's theorem Section 76 for Church's theorem	Assignment 14
15	May 22	The Second Incompleteness Theorem	Chapter VIII, Theorem 30	Assignment 15
16	May 27	Chaitin's work	No reading in Kleene	Assignment 16
17	May 29	Discussion of incompleteness	No reading in Kleene	No homework to turn in. Review old homework and bring any unresolved questions to class.
18	June 3	Loose ends; student questions; go over old homework Here is the final exam, due June 11 at noon.		All students earned A on the last homework assignment
19	We don't get here	Intuitionism	Chapter XV, section 81
20	We don't get here	Recursive Realizability	Chapter XV, section 82