Mass problems
by
Stephen G. Simpson
Pennsylvania State University

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).

PDF

Date received: March 3, 2008