| 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
|
| 5/12 |
|
|
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 |
