Math 597C: Mass Problems

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