Recursion Theory and Symbolic Dynamics
Stephen G. Simpson
Pennsylvania State University
http://www.math.psu.edu/simpson/
Trimester on Methods of Proof Theory
Max Planck Institute for Mathematics
Bonn, Germany
May 30, 2007
Abstract
A subset P of {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 subset P of {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. The lattice P_w of Muchnik degrees of
mass problems associated with nonempty Pi^0_1 subsets of {0,1}^N 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.
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 forbidden 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.