Degrees of unsolvability of
2-dimensional subshifts of finite type

Stephen G. Simpson
Pennsylvania State University
NSF DMS-0600823, DMS-0652637

Dynamical Systems Seminar
University of Maryland
Thursday, November 13, 2008


We apply some concepts and results from mathematical logic in order to
obtain an apparently new counterexample in 2-dimensional symbolic
dynamics.  A set X is said to be Muchnik reducible to a set Y if each
point of Y can be used as a Turing oracle to compute a point of X.
The Muchnik degree of X is the equivalence class of X under the
equivalence relation of mutual Muchnik reducibility.  There is an
extensive recursion-theoretic literature concerning the lattice of
Muchnik degrees of nonempty effectively closed sets in Euclidean
space.  This lattice is known as P_w.  We prove that P_w consists
precisely of the Muchnik degrees of 2-dimensional subshifts of finite
type.  We apply this result to obtain an infinite collection of
2-dimensional subshifts of finite type which are, in a certain sense,
mutually incompatible.  Our application is stated in purely dynamical
terms, with no mention of recursion theory.  We speculate on possible
correlations between the dynamical properties of a 2-dimensional
subshift of finite type and its Muchnik degree.