# Recursion Theory and Symbolic Dynamics

Stephen G. Simpson

Pennsylvania State University

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.