Math 29 Detailed Schedule
Note: x refers to chapter and x.y to chapter.section in Cutland.
| Section | Dates | Reading |
|---|---|---|
| Introduction: Notation and Historical Background | Mar 28 | 1.1 |
| Module 1: Turing Machines | Mar 30, Apr 2 | 3.4, handout |
| Homework (due Monday, April 9) | ||
| Interlude: Coding | Apr 2 | 1.5, 3.6 |
| Module 2: Partial Recursive Functions | Apr 4, 6, 9 | 2, 3.2-3 |
| Interlude: The Church-Turing Thesis | Apr 6, 9 | 3.7 |
| Homework: 2.5.4 #1, 3.7.2 #1 (ignore URM-computable; you're not giving a | ||
| machine/recursion definition anyway) (due Friday, Apr 13) | ||
| Module 3: Listing Programs and Universal Machines | Apr 11-16 | 4, 5 |
| Homework: 4.2.3, 4.3.2 #1,4, 4.4.1 #1 (due Monday, Apr 23) | ||
| (still subject to change) | |
| Computing and enumerating | |
| Noncomputable sets (simple sets) | |
| Turing reduction and Post's problem (oracle Turing machines) | |
| (Aside: finite injury priority arguments) | |
| Turing degrees (equivalence relations, partial orders) | |
| Relativization and the Turing jump (the arithmetic hierarchy) | |
| Lattice-theoretic questions | |
| Homework: Look at this LaTeX example and then typeset this document (due Monday, May 14). | |
| Favorable-looking ways to get TeX: TeX for Macs, TeX for Windows. | |
| A second LaTeX example. | |
| A LaTeX template file. | |
| Overview of randomness | |
| Kolmogorov complexity | |
| Relative randomness | |
| K-triviality | |
| Some open questions | |
| If time: reverse math |
Relevant Web Links:
Module 1: Turing Machine Simulators Online
Back to main 29 page.