Recent Aspects of Mass Problems: Symbolic Dynamics and Intuitionism

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

February 12, 2008

This note consists of an abstract and references for a talk to be
given February 19-20, 2008 at a workshop at Tohoku University in
Sendai, Japan.


ABSTRACT

MASS PROBLEMS

A set P included in {0,1}^N may be viewed as a mass problem, i.e., a
decision problem with more than one solution.  By definition, the
solutions of P are the elements of P.  A mass problem is said to be
solvable if at least one of its solutions is recursive.  A mass
problem P is said to be Muchnik reducible to a mass problem Q if for
each solution of Q there exists a solution of P which is Turing
reducible to the given solution of Q.  A Muchnik degree is an
equivalence class of mass problems under mutual Muchnik reducibility.

A set P included in {0,1}^N is said to be Pi^0_1 if it is effectively
closed, i.e., it is the complement of the union of a recursive
sequence of basic open sets.  Let P_w be the lattice of Muchnik
degrees of mass problems associated with nonempty Pi^0_1 subsets of
{0,1}^N.  The lattice P_w has been investigated by the speaker and
others.  It is known that P_w contains many specific, natural Muchnik
degrees which are related to various topics in the foundations of
mathematics.  Among these topics are algorithmic randomness, reverse
mathematics, almost everywhere domination, hyperarithmeticity,
resource-bounded computational complexity, Kolmogorov complexity, and
subrecursive hierarchies.

SYMBOLIC DYNAMICS

Let A be a finite set of symbols.  The full two-dimensional shift on A
is the dynamical system consisting of the natural action of the group
ZxZ on the compact space A^ZxZ.  A two-dimensional subshift is a
nonempty closed subset of A^ZxZ which is invariant under the action of
ZxZ.  A two-dimensional subshift is said to be of finite type if it is
defined by a finite set of excluded configurations.  The
two-dimensional subshifts of finite type are known to form an
important class of dynamical systems, with connections to mathematical
physics, etc.

Clearly every two-dimensional subshift of finite type is a nonempty
Pi^0_1 subset of A^ZxZ, hence its Muchnik degree belongs to
P_w.  Conversely, we prove that every Muchnik degree in P_w is the
Muchnik degree of a two-dimensional subshift of finite type.  The
proof of this result uses tilings of the plane.  We present an
application of this result to symbolic dynamics.  Our application is
stated purely in terms of two-dimensional subshifts of finite type,
with no mention of Muchnik degrees.

INTUITIONISM

Historically, the study of mass problems originated from
intuitionistic considerations.  Kolmogorov 1932 proposed to view
intuitionism as a "calculus of problems."  Muchnik 1963 introduced
Muchnik degrees as a rigorous elaboration of Kolmogorov's proposal.
As noted by Muchnik, the lattice of all Muchnik degrees is Brouwerian.

The question arises, is the sublattice P_w Brouwerian?  We prove
that it is not.  The proof uses our adaptation of a technique of
Posner and Robinson.


REFERENCES

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

Andrei N. Kolmogorov, Zur Deutung der intuitionistischen Logik,
Mathematische Zeitschrift, 35, 1932, 58-65.

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

David B. Posner and Robert W. Robinson, Degrees joining to 0',
Journal of Symbolic Logic, 46, 1981, 714-722.

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

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

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

Stephen G. Simpson, Medvedev degrees of 2-dimensional subshifts of
finite type, 8 pages, 2007, Ergodic Theory and Dynamical Systems, to
appear.

Stephen G. Simpson, Mass problems and intuitionism, 9 pages, 2007,
Notre Dame Journal of Formal Logic, to appear.