Degrees of unsolvability of 2-dimensional subshifts of finite type

Stephen G. Simpson Pennsylvania State University NSF DMS-0600823, DMS-0652637 http://www.math.psu.edu/simpson/ simpson@math.psu.edu

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

Abstract

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.