Mass Problems

Stephen G. Simpson

Department of Mathematics

Pennsylvania State University

http://www.math.psu.edu/simpson/

March 26, 2008

Kolmogorov 1923 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 is a mass problem, the
*solutions* of are the elements of . We say that is
*solvable* if there exists a computable solution of . We say
that is *weakly reducible* to if each solution of can
be used as a Turing oracle to compute some solution of . A
*weak degree* is an equivalence class of mass problems under
mutual weak reducibility. Let be the lattice of weak degrees.
There is an obvious, natural embedding of the Turing degrees into
, 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 is a model of intuitionistic propositional
calculus. Since 1999 I have been studying the sublattice
consisting of the weak degrees of nonempty effectively closed sets in
Euclidean space. I have discovered that there is a natural embedding
of the recursively enumerable Turing degrees into . Moreover, I
have discovered that 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 have applied to the study of 2-dimensional symbolic
dynamics. The purpose of this talk is to introduce and to
survey what is known about it.