Mass Problems

Stephen G. Simpson

Department of Mathematics

Pennsylvania State University

http://www.math.psu.edu/simpson/

December 18, 2008

Stephen G. Simpson

Department of Mathematics

Pennsylvania State University

http://www.math.psu.edu/simpson/

December 18, 2008

This is the abstract of my invited 50-minute talk at the Very Informal Gathering of Logicians at UCLA, January 30 to February 1, 2009, in honor of the 60th birthday of John Steel.

Kolmogorov 1932 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 discovered a natural embedding of the recursively
enumerable Turing degrees into . Moreover, I 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 applied
to the study of 2-dimensional symbolic dynamics. The purpose of
this talk is to introduce and survey what is known about it.

This document was generated using the
**LaTeX**2`HTML` 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 abstract`

The translation was initiated by Stephen G Simpson on 2008-12-18

Stephen G Simpson 2008-12-18