Mass Problems

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson/

December 18, 2008

This is the abstract of my invited 50-minute talk at the Very Informal Gathering of Logicians at UCLA, January 30 to February 1, 2009, in honor of the 60th birthday of John Steel.

Abstract

Kolmogorov 1932 proposed to view intuitionistic logic as a “calculus of problems” (Aufgabenrechnung). This is essentially the famous BHK interpretation of intuitionism. Medvedev 1955 introduced mass problems as a rigorous elaboration of Kolmogorov’s proposal. A mass problem is a set of reals. If P is a mass problem, the solutions of P are the elements of P. We say that P is solvable if there exists a computable solution of P. We say that P is weakly reducible to Q if each solution of Q can be used as a Turing oracle to compute some solution of P. A weak degree is an equivalence class of mass problems under mutual weak reducibility. Let D_{w} be the lattice of weak degrees. There is an obvious, natural embedding of the Turing degrees into D_{w}, obtained by identifying the Turing degree of a real with the weak degree of the singleton set consisting of that real. Muchnik 1963 observed that D_{w} is a model of intuitionistic propositional calculus. Since 1999 I have been studying the sublattice P_{w} consisting of the weak degrees of nonempty effectively closed sets in Euclidean space. I discovered a natural embedding of the recursively enumerable Turing degrees into P_{w}. Moreover, I discovered that P_{w} contains a variety of specific, natural, weak degrees which are closely related to various foundationally interesting topics. Among these topics are reverse mathematics, algorithmic randomness, algorithmic information theory, hyperarithmeticity, diagonal nonrecursiveness, almost everywhere domination, subrecursive hierarchies, resource-bounded computational complexity, effective Hausdorff dimension, and Kolmogorov complexity. Recently I applied P_{w} to the study of 2-dimensional symbolic dynamics. The purpose of this talk is to introduce P_{w} and survey what is known about it.