Instructor: Justin Miller

Course on


Date: Lecture Topic: Lecture Notes Assignments Due:
3/25 Introduction Download Introduction
3/27 Numbers, Functions, and Sets Download Numbers, Functions, and Sets
3/29 Register Machines Download Register Machines Homework 0 Download Homework 0
4/01 More Register Machines Download More Register Machines
4/03 Other Models of Computation Download Other Models of Computation
4/05 Codes Download Codes

Homework 1 Download Homework 1

Solutions Download Solutions

4/08 No class (Eclipse)
4/10 Universal Machines Download Universal Machines
4/11 The Recursion Theorem Download The Recursion Theorem
4/12 Noncomputability Download Noncomputability

Homework 2 Download Homework 2

Solutions Download Solutions

4/15 The Halting Problem Download The Halting Problem
4/17 Creative Sets Download Creative Sets
4/18 Simple Sets Download Simple Sets


4/19 No Class

Homework 3 Download Homework 3 

Solutions Download Solutions

4/22 No Class


4/24 Applying Computability Download Applying Computability
4/25 Noncomputable Problems from Mathematics Download Noncomputable Problems from Mathematics
4/26 Reducibility Download Reducibility

Homework 4 Download Homework 4

Solutions Download Solutions

4/29 Complete Sets Download Complete Sets
5/01 Oracles Download Oracles
5/02 Midterm Quiz Solutions Download Solutions
5/03 Turing Reducibility Download Turing Reducibility  
5/06 Relativization Download Relativization Take-Home Midterm Download Take-Home Midterm
5/08 The Jump Download The Jump
5/10 The Limit Lemma Download The Limit Lemma

Project Proposal Download Project Proposal


Homework 5 Download Homework 5

5/13 Arslanov's Completeness Criterion Download Arslanov's Completeness Criterion
5/15 Low and High Sets Download Low and High Sets
5/17 Measures and Randomness Download Measures and Randomness Homework 6 Download Homework 6
5/20 Kolmogorov Complexity
5/22 Presentations and Advanced Topics
5/24 Presentations   Homework 7 Download Homework 7
5/27 Memorial Day! (NO CLASS)
5/29 Presentations
TBD Final Quiz   Final Quiz
6/04 Final Project