MASS PROBLEMS

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

August 13, 2007

This note consists of an abstract and references for a seminar talk to
be given at the University of Chicago, Department of Mathematics,
September 14, 2007.

ABSTRACT

Informally, mass problems are similar to decision problems.  The
difference is that, while a decision problem has only one solution, a
mass problem is allowed to have more than one solution.  Many concepts
which apply to decision problems apply equally well to mass problems.
For instance, a mass problem is said to be solvable if it has at least
one computable solution.  Also, one mass problem is said to be
reducible to another mass problem if, given a solution of the second
problem, we can use it to find a solution of the first problem.

Many unsolvable mathematical problems are most naturally viewed as
mass problems rather than decision problems.  For example, let CPA be
the problem of finding a completion of Peano Arithmetic.  A well-known
theorem going back to G"odel and Tarski says that CPA is unsolvable,
in the sense that there are no computable completions of Peano
Arithmetic.  Note that, in describing CPA as a ``problem'' whose
``solutions'' are the completions of Peano Arithmetic, we are
implicitly viewing CPA as a mass problem rather than a decision
problem.  This is because Peano Arithmetic has many different
completions, with many different Turing degrees.  There is no single
Turing degree which can be said to measure the amount of unsolvability
which is inherent in CPA.

Formally, a mass problem is defined to be an arbitrary set of Turing
oracles, i.e., an arbitrary subset of the Baire space, N^N.  Let P and
Q be mass problems.  We say that P is solvable if P has at least one
recursive element.  We say that P is Muchnik reducible to Q if for all
g in Q there exists f in P such that f is Turing reducible to g.  A
Muchnik degree is an equivalence class of mass problems under mutual
Muchnik reducibility.  The Muchnik degrees are partially ordered in
the obvious way, by Muchnik reducibility.  Under this partial
ordering, it is straightforward to show that the Muchnik degrees form
a complete distributive lattice.  There is an obvious, natural
embedding of the upper semilattice of Turing degrees into the lattice
of Muchnik degrees, obtained by mapping the Turing degree of f to the
Muchnik degree of the singleton set {f}.

The lattice of Muchnik degrees was first introduced by Albert Muchnik
(of Friedberg/Muchnik fame) in 1963.  Subsequently Muchnik degrees
have been used to classify unsolvable problems which arise in various
areas of mathematics including symbolic dynamics, algorithmic
randomness, and model theory.

Let D_w be the lattice of all Muchnik degrees.  Let P_w be the
sublattice of D_w consisting of the Muchnik degrees of mass problems
associated with nonempty Pi^0_1 subsets of the Cantor space, {0,1}^N.
Recent research beginning in 1999 has revealed that the lattice P_w is
mathematically rich and contains many specific, natural Muchnik
degrees corresponding to specific, natural mass problems which are of
great interest.  For example, the top degree in P_w is the Muchnik
degree of CPA, the set of completions of Peano Arithmetic.  Other
specific, natural Muchnik degrees in P_w are closely related to
various foundationally interesting topics such as algorithmic
randomness, reverse mathematics, hyperarithmeticity, diagonal
nonrecursiveness, almost everywhere domination, subrecursive
hierarchies, resource-bounded computational complexity, and Kolmogorov
complexity.

The purpose of this talk is to introduce P_w and to survey some recent
discoveries regarding specific, natural Muchnik degrees in P_w.

REFERENCES

Stephen Binns.
A splitting theorem for the Medvedev and Muchnik lattices.
Mathematical Logic Quarterly, 49:327-335, 2003.

Stephen Binns and Stephen G. Simpson.
Embeddings into the Medvedev and Muchnik lattices of Pi^0_1 classes.
Archive for Mathematical Logic, 43:399-414, 2004.

Joshua A. Cole and Stephen G. Simpson.
Mass problems and hyperarithmeticity.
Preprint, 20 pages, 28 November 2006, submitted for publication.

Bjoern Kjos-Hanssen and Stephen G. Simpson.
Mass problems and Kolmogorov complexity.
Preprint, 1 page, 4 October 2006, in preparation.

Albert A. Muchnik.
On strong and weak reducibilities of algorithmic problems.
Sibirskii Matematicheskii Zhurnal, 4:1328-1341, 1963.
In Russian.

Stephen G. Simpson.
Medvedev degrees of 2-dimensional subshifts of finite type.
Preprint, 8 pages, 1 May 2007, submitted for publication.

Stephen G. Simpson.
Mass problems and randomness.
Bulletin of Symbolic Logic, 11:1-27, 2005.

Stephen G. Simpson.
An extension of the recursively enumerable Turing degrees.
Journal of the London Mathematical Society, 75:287-297, 2007.

Stephen G. Simpson.
Mass problems and almost everywhere domination.
Mathematical Logic Quarterly, 53:483-492, 2007.

Stephen G. Simpson.
Mass problems and intuitionism.
Preprint, 9 pages, 1 August 2007, submitted for publication.