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.