Math 597B is a graduate topics course which I taught in Spring 2007.
The course was suitable for all mathematics graduate students. The
title of the course was **Computability and Randomness**. The
course included an introduction to Turing's theory of computability
and unsolvability, which is basic for theoretical computer science and
the study of unsolvable mathematical problems. The course also
included an introduction to a research area which is currently very
active, namely, algorithmic randomness and Kolmogorov complexity.

The schedule number was 775234. Lectures were Monday Wednesday Friday 10:10 - 11:00 AM. According to the registar we were to meet in 102 Pond, but actually we met in 315 McAllister.

My office is 305 McAllister. My office hours for Spring 2007 were Tuesday-Wednesday-Thursday 1:00-2:00, or you could drop in whenever my door was open, or make an appointment.

Some relevant readings are available on-line:

- Lecture notes by Peter Cholak. (69 pages.)
- Book in preparation, by Rod Downey and Denis Hirschfeldt. (>500 pages.)
- Book in preparation, by Andre Nies. (>240 pages.)
- Lecture notes from my topics course, Spring 2005. (89 pages. Sections 3.10 and 3.11 are an introduction to Turing reducibility. Chapter 4 is an introduction to randomness.)
- Lecture notes from my topics course, Spring 2004. (104 pages. Chapter 2 is an introduction to degrees of unsolvability.)
- My
semi-expository paper
*Almost everywhere domination and superhighness*. (28 pages.)

Here are some additional course materials:

- Homework #1: PDF, PS, DVI.
- Homework #2: PDF, PS, DVI.
- Homework #3: PDF, PS, DVI.
- Homework #4: PDF, PS, DVI.
- Homework #5: PDF, PS, DVI.
- Homework #6: PDF, PS, DVI.

This same semester, Spring 2007, I also taught Math 558, a course on foundations of mathematics, which includes an introduction to Turing's theory of computability and unsolvability.

t20@psu.edu / 7 May 2007