Computability theory

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 |