3/28 | Introduction and History | 1.2 | 3/28 | |

3/30 | Numbers, Functions, and Sets | 3.1, 3.4 | 3/30 | |

3/31 | (X) The Language of Arithmetic | 2.1, 2.2, 2.3 | | |

4/01 | Register Machines | | 4/01 | |

4/04 | More Register Machines | | 4/04 | |

4/06 | Turing Machines | 3.2 | 4/06 | Homework #1 |

4/07 | (X) Induction | 2.5 | | |

4/08 | More Turing Machines | 3.2 | 4/08 | |

4/11 | Codes | 3.4, 3.6 | 4/11 | |

4/13 | Universal Turing Machine | 3.5, 4.3 | 4/13 | Homework #2 |

4/14 | (X) Primitive Recursion | | | |

4/15 | The Recursion Theorem | 4.4 | 4/15 | |

4/18 | Noncomputability | 4.5 | 4/18 | |

4/20 | Halting Problems | 4.1, 4.2 | 4/20 | Homework #3 |

4/21 | (X) Least Number Operator | | | |

4/22 | Creative Sets | | 4/22 | |

4/25 | Simple Sets | 5.4 | 4/25 | |

4/27 | Review | | 4/27 | Homework #4 |

4/28 | (X) Midterm | | | |

4/29 | Applying Computability | | 4/29 | |

5/02 | Noncomputable Problems from Mathematics | | 5/02 | |

5/04 | Reducibility | | 5/04 | Take-home Midterm |

5/05 | (X) Quantifiers | | | |

5/06 | Complete Sets | 7.2, 7.3 | 5/06 | |

5/09 | Oracles | 6.1 | 5/09 | |

5/11 | Turing Reducibility | | 5/11 | Homework #5 |

5/12 | (X) The Arithmetic Hierarchy | 7.2, 7.3 | | |

5/13 | Relativization | 7.1 | 5/13 | |

5/16 | The Jump | 7.1 | 5/16 | |

5/18 | The Limit Lemma | 8.1 | 5/18 | Homework #6 |

5/19 | (X) Post's Theorem | | | |

5/20 | Arslanov's Completeness Criterion | 8.2 | 5/20 | |

5/23 | Low and High Sets | | 5/23 | |

5/25 | Randomness | | | Homework #7 |

5/26 | (X) Advanced Topics | | | |

5/27 | Randomness | | | |

5/30 | No Class (Memorial Day) | | | |

6/01 | Review | | 6/01 | Homework #8 |

6/06 | Final Exam | | | |

6/07 | Take-home Final | | Final | |