Recent Aspects of Mass Problems:

Symbolic Dynamics and Intuitionism

Stephen G. Simpson

Department of Mathematics

Pennsylvania State University

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

March 6, 2008

Symbolic Dynamics and Intuitionism

Stephen G. Simpson

Department of Mathematics

Pennsylvania State University

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

March 6, 2008

This is a research summary and talk proposal for 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/.

A set
may be viewed as a *mass problem*,
i.e., a decision problem with more than one solution. By definition,
the *solutions* of are the elements of . A mass problem
is said to be *solvable* if at least one of its solutions is
recursive. A mass problem is said to be *weakly reducible*
to a mass problem if for each solution of there exists a
solution of which is Turing reducible to the given solution of
. A *weak degree* is an equivalence class of mass problems
under mutual weak reducibility. The lattice of all weak degrees
is due to Muchnik 1963. There is an obvious embedding of the Turing
degrees into .

A set
is said to be if it is
*effectively closed*, i.e., it is the complement of the union of
a recursive sequence of basic open sets. Let denote the
sublattice of consisting of the mass problems associated with
nonempty subsets of
. The lattice has
been investigated by Simpson and his collaborators. There is a
non-obvious but natural embedding of the recursively enumerable Turing
degrees into . It is known that 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.

Let be a finite set of symbols. The *full two-dimensional
shift* on is the dynamical system consisting of the natural
action of the group
on the compact space
. A
*two-dimensional subshift* is a nonempty closed subset of
which is invariant under the action of
. 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 subset of , hence its weak degree belongs to . Conversely, we prove that every weak degree in 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.

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 of all weak degrees is Brouwerian.

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

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

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 ,
*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, 9 pages,
2007, *Notre Dame Journal of Formal Logic*, to appear.

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

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-03-17

Stephen G Simpson 2008-03-17