Course Schedule

DateSubjectTextbook SectionLecture NotesHomework Due
3/28Introduction and History1.23/28
3/30Numbers, Functions, and Sets3.1, 3.43/30
3/31(X) The Language of Arithmetic2.1, 2.2, 2.3
4/01Register Machines4/01
4/04More Register Machines4/04
4/06Turing Machines3.24/06Homework #1
4/07(X) Induction2.5
4/08More Turing Machines3.24/08
4/11Codes3.4, 3.64/11
4/13Universal Turing Machine3.5, 4.34/13Homework #2
4/14(X) Primitive Recursion
4/15The Recursion Theorem4.44/15
4/18Noncomputability4.54/18
4/20Halting Problems4.1, 4.24/20Homework #3
4/21(X) Least Number Operator
4/22Creative Sets4/22
4/25Simple Sets5.44/25
4/27Review4/27Homework #4
4/28(X) Midterm
4/29Applying Computability4/29
5/02Noncomputable Problems from Mathematics5/02
5/04Reducibility5/04Take-home Midterm
5/05(X) Quantifiers
5/06Complete Sets7.2, 7.35/06
5/09Oracles6.15/09
5/11Turing Reducibility5/11Homework #5
5/12(X) The Arithmetic Hierarchy7.2, 7.3
5/13Relativization7.15/13
5/16The Jump7.15/16
5/18The Limit Lemma8.15/18Homework #6
5/19(X) Post's Theorem
5/20Arslanov's Completeness Criterion8.25/20
5/23Low and High Sets5/23
5/25RandomnessHomework #7
5/26(X) Advanced Topics
5/27Randomness
5/30No Class (Memorial Day)
6/01Review6/01Homework #8
6/06Final Exam
6/07Take-home FinalFinal