The following is a tentative syllabus for the course. This page will be updated irregularly. On the other hand, the weekly syllabus contained in the Homework assignments page will always be accurate.
Broadly, I plan to cover the first seven chapters, which is approximately the material described in the ORC course description, followed by additional topics as I judge appropriate based on time and your interests. The pace of this schedule will be adjusted as needed, but the date of the midterm is firm.
Lectures | Brief description | Sections in text |
---|---|---|
3/27 | What is computable? Then and now | Chapter 1 |
3/29 | Recursive versus computable: competing notions | 2.1-2.2 |
3/31 | URMs: the "easy" Turing machines | 2.3 |
4/3 | Play ball: build your own Turing machine | 2.4 |
4/5 | Church's thesis revisited: is it a theorem? | 2.5 |
4/7 | Logic and modern mathematics: I think this would be a good time for a beer | Chapter 3 |
4/10 | How many Turing machines can there be? | 4.1-4.2 |
4/12 | How many Turing machines need there be? | 4.3-4.5 |
4/14 | Out of the ashes: into incomputability | 5.1-5.2 |
4/17 | Unsolvability of the halting problem | 5.2-5.4 |
4/19 | Creative sets: a natural selection | 6.1 |
4/21 | No, after you: simple sets | 6.2 |
4/24 | What doesn't kill you makes you stronger | Review Chapters 1-5, 6.1 |
4/26 | MIDTERM | |
4/28 | A treat | 6.3 |
5/1 | E pluribus unum | 7.1 |
5/3 | A new universe | 7.2 |
5/5 | More creativity | 7.3 |
5/8 | The architect (who created the oracle) | 10.1-10.3 |
5/10 | Higher arithmetic | 10.4-10.5 |
5/12 | Finally some rich structure | 10.6 |
5/15 | When they go low | 12.1 |
5/17 | (Can't) lock her up: immunity | 12.2-12.3 |
5/19 | TBA | |
5/22 | TBA | |
5/24 | TBA | |
5/26 | The fast and the furious | Review for the final |
5/29 | Memorial day (no class) | |
6/1 | FINAL EXAM |