RECENT ASPECTS OF MASS PROBLEMS: SYMBOLIC DYNAMICS AND INTUITIONISM

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

March 6, 2008 (references updated May 8, 2008)

This is an abstract for my talk at Workshop ID Number 0815,
Mathematical Logic: Proof Theory, Constructive Mathematics, organized
by Samuel R. Buss, Ulrich Kohlenbach, and Helmut Schwichtenberg, April
6-12, 2008, Mathematisches Forschungsinstitut Oberwolfach,
http://www.mfo.de/.

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 weakly 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 weak degree is an equivalence
class of mass problems under mutual weak reducibility.  The lattice
D_w of all weak degrees is due to Muchnik 1963.  There is an obvious
embedding of the Turing degrees into D_w.

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 denote the sublattice of D_w
consisting of the mass problems associated with nonempty Pi^0_1
subsets of {0,1}^N.  The lattice P_w has been investigated by Simpson
and his collaborators.  There is a non-obvious but natural embedding
of the recursively enumerable Turing degrees into P_w.  It is known
that P_w contains many specific, natural weak degrees which are
related to various topics in the foundations of mathematics.  Among
these topics are reverse mathematics, algorithmic randomness,
Kolmogorov complexity, almost everywhere domination,
hyperarithmeticity, effective Hausdorff dimension, resource-bounded
computational 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
Z x Z 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 weak degree belongs to P_w.
Conversely, we prove that every weak degree in P_w is the weak 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.  Namely, we obtain an infinite family of
two-dimensional subshifts of finite type which are, in a certain
sense, mutually incompatible.  Our application is stated purely in
terms of two-dimensional subshifts of finite type, with no mention of
weak 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
weak degrees as a rigorous elaboration of Kolmogorov's proposal.  As
noted by Muchnik, the lattice D_w of all weak 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

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

Joshua A. Cole and Stephen G. Simpson, Mass problems and
hyperarithmeticity, 20 pages, 2006, to appear in Journal of
Mathematical Logic.

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, Mass problems and intuitionism, Notre Dame Journal
of Formal Logic, 49, 2008, 127-136.

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