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.