The syllabus is somewhat approximate and subject to change.
| 29 January | Introductory Meeting, Chapter 1 |
| 1 February | Chapter 2 |
| Problem Set #1 due 8 February | |
| 3–8 February | Chapter 3; Section 4.1 It's still worth reading Turing's original paper "On Computable Numbers", Proceedings of the London Mathematical Society s2-42 (1937), pp. 230-65 (Oxford Journals Archive). Section 9 of that paper contains a fascinating justification of his definition of computability in terms of a "conceptual analysis" of the intuitive notion. It's also worth looking at his paper "Computing Machinery and Intelligence", Mind 59 (1950), pp. 433-60 (JSTOR). |
| Problem Set #2 due 15 February | |
| 10–15 February | Chapters 5–6 |
| Problem Set #3 due 24 February | |
| 17–19 February | Chapter 7 |
| 22 February | No Class: Presidents' Day Holiday |
| 24 February | Section 8.1 There is a handout, "Coding Turing Machine Computations", that contains the definitions of a lot of the functions we need to do that. |
| Problem Set #4 due 2 March | |
| 26 February–4 March | Chapters 9–10 A somewhat less formal presentation of Tarski's definition of truth can be found in the handout "Tarski's Theory of Truth", which I use in other classes. Note that this definition is given for the language of arithmetic, and only for the standard interpretation of that language. But it might nonetheless prove helpful. |
| Problem Set #5 due 11 March | |
| 7–14 March | Section 11.1; Chapter 13 There is a handout that summarizes some of the important definitions and lemmas in the proof of the Compactness Theorem. |
| Problem Set #6 due 21 March | |
| 16–25 March | Chapters 14–15 You should have a look also at the handout on the simplified sequent calculus, which is the formal system we will actually discuss. |
| Problem Set #7 due 6 April | |
| 28 March–1 April | No Class: Spring Break |
| 4–13 April | Chapter 16 |
| Problem Set #8 due 20 April | |
| 15–20 April | Chapter 17 You can find a very informal exposition of one form of the diagonal lemma here. You may also find it helpful to read the only slightly more formal exposition in §10 of this document. |
| Problem Set #9 due 27 April | |
| 22–27 April | Chapter 18 |
| 29 April-9 May |
Reading Period It is not unlikely we will need an additional session or two. Just so you know. |
| 19 May, 2pm | Final Examination |