Syllabus

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