Mass Problems

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

February 12, 2008

This note consists of an abstract and references for a two-hour tutorial given February 22-23, 2008 at a workshop in Matsushima, Japan.

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 $\mathrm{CPA}$ be the problem of finding a completion of Peano Arithmetic. A well-known theorem going back to Gödel and Tarski says that $\mathrm{CPA}$ is unsolvable, in the sense that there are no computable completions of Peano Arithmetic. Note that, in describing $\mathrm{CPA}$ as a ``problem'' whose ``solutions'' are the completions of Peano Arithmetic, we are implicitly viewing $\mathrm{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 $\mathrm{CPA}$.

Formally, a mass problem is defined to be an arbitrary set of Turing oracles, i.e., an arbitrary subset of the Baire space, $\mathbb{N}^\mathbb{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 $\mathcal{D}_w$ be the lattice of all Muchnik degrees. Let $\mathcal{P}_w$ be the sublattice of $\mathcal{D}_w$ consisting of the Muchnik degrees of mass problems associated with nonempty $\Pi^0_1$ subsets of the Cantor space, $\{0,1\}^\mathbb{N}$. Recent research beginning in 1999 has revealed that $\mathcal{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 $\mathcal{P}_w$ is the Muchnik degree of $\mathrm{CPA}$, the set of completions of Peano Arithmetic. Other specific, natural Muchnik degrees in $\mathcal{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, effective Hausdorff dimension, and Kolmogorov complexity.

The purpose of this tutorial is to introduce $\mathcal{P}_w$ and to survey some recent discoveries regarding specific, natural Muchnik degrees in $\mathcal{P}_w$.

Bibliography

1

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

2

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.

3

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

4

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

5

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

6

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

7

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

8

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

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 abstract2

The translation was initiated by Stephen G Simpson on 2008-02-28