Recursion Theory and Symbolic Dynamics

Stephen G. Simpson Department of Mathematics 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 set P ⊆ {0, 1}^{ℕ} 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 ⊆ {0, 1}^{ℕ} is said to be Π_{1}^{0} 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 Π_{1}^{0} subsets of {0, 1}^{ℕ} 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 ℤ × ℤ on the compact space A^{ℤ×ℤ}. A two-dimensional subshift is a nonempty closed subset of A^{ℤ×ℤ} 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 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 Π_{1}^{0} subset of A^{ℤ×ℤ}, hence its Muchnik degree belongs to P_{w}. Conversely, we prove that every Muchnik degree in P_{w} is the Muchnik degree of a twodimensional 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.