MASS PROBLEMS

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

March 6, 2008

This is the abstract of my 1-hour plenary talk at a conference on
Computability, Complexity, and Randomness to be held at Nanjing
University, Nanjing, China, May 19-23, 2008.

ABSTRACT

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 recursive solution of P.  We say that P is weakly
reducible to Q if each solution of Q computes a solution of P.  A weak
degree is an equivalence class of mass problems under mutual weak
reducibility.  There is an obvious, natural embedding of the Turing
degrees into the weak degrees.  Namely, we identify the Turing degree
of a real with the weak degree of singleton set consisting of that
real.  Let D(weak) be the lattice of weak degrees.  The lattice
D(weak) was first introduced in 1963 by Albert Muchnik, who showed
that it 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 the Cantor space.
I have discovered that there is a natural embedding of the recursively
enumerable Turing degrees into P(weak).  I have also discovered that
P(weak) contains many specific, natural, weak degrees which are
closely related to various foundationally interesting topics.  Among
these topics are reverse mathematics, algorithmic randomness,
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 survey what is known about
P(weak).