MASS PROBLEMS

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

March 26, 2008

This is the abstract of my 1-hour plenary talk at Logic Colloquium
2008, to be held in Bern, Switzerland, July 3-8, 2008.

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(weak) be the lattice of weak
degrees.  There is an obvious, natural embedding of the Turing degrees
into D(weak), 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(weak) is a model of intuitionistic propositional
calculus.  Since 1999 I have been studying the sublattice P(weak)
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 P(weak).  Moreover,
I have discovered that P(weak) 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 P(weak) to the study of 2-dimensional symbolic
dynamics.  The purpose of this talk is to introduce P(weak) and to
survey what is known about it.