Syllabus for Math 497A: Computability, Unsolvability, Randomness

Stephen G. Simpson

August 21, 2007 Last revised August 24, 2007

• Week 1, August 27–31.

register-machine programs, computable functions, recursion.

• Monday September 3, no lecture, Labor Day.

• Week 2, September 3–7.

partial recursive functions, the enumeration theorem, the halting problem.

• Week 3, September 10–14.

unsolvable mathematical problems, many-one reducibility, the arithmetical hierarchy.

• Week 4, September 17–21.

oracles, relativization, Turing reducibility, degrees of unsolvability, the jump operator.

• Week 5, September 24–28.

finite approximation, the structure of the Turing degrees.

• Week 6, October 1–5.

Monday, review; Wednesday, midterm exam.

• Week 7, October 8–12.

machines, prefix-free machines, Kolmogorov complexity.

• Week 8, October 15–19.

the fair-coin probability measure, tests for randomness.

• Week 9, October 22–26.

randomness, strong randomness, weak randomness.

• Week 10, October 29 – November 2.

basis theorems, Turing degrees of random sequences.

• Week 11, November 5–9.

relative randomness, van Lambalgen’s Theorem.

• Week 12, November 12–16.

initial segment complexity, Schnorr’s Theorem.

• November 19–23, no lectures, Thanksgiving week.

• Week 13, November 26–30.

LR-reducibility.

• Week 14, December 3–7.

Monday, last lecture; Tuesday through Friday, study days.

• Week 15, December 10–14.

oral final examinations.