Math 597C is a graduate topics course in mathematical logic, offered in Spring 2009. We are meeting Monday-Wednesday-Friday 9:05-9:55 in 315 McAllister Building.

We begin the course with a review of Turing's theory of computability
and unsolvability. After that we study *degrees of
unsolvability*, a method of measuring and comparing the amount of
algorithmic unsolvability which is inherent in various mathematical
problems. We focus on *mass problems* in the sense of Medvedev
1955 and Muchnik 1963. We present many recently discovered
connections to interesting topics such as:

- reverse mathematics
- algorithmic randomness
- Kolmogorov complexity
- effective Hausdorff dimension
- resource-bounded computational complexity
- almost everywhere domination
- hyperarithmeticity
- constructive mathematics
- 2-dimensional symbolic dynamics
- tiling problems

Lecture notes for the course are on-line here.

My office is 305 McAllister. My office hours for Spring 2009 are Monday-Wednesday 4:00-5:00 or you can drop in whenever my door is open, or make an appointment.

My papers relevant to mass problems are:

- Mass problems and randomness
- An extension of the recursively enumerable Turing degrees
- Some fundamental issues concerning degrees of unsolvability
- Almost everywhere domination and superhighness
- Mass problems and almost everywhere domination
- Mass problems and hyperarithmeticity
- Medvedev degrees of 2-dimensional subshifts of finite type
- Mass problems and intuitionism
- Mass problems and measure-theoretic regularity

t20@psu.edu / 1 December 2009