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 |