Symbolic dynamics and degrees of unsolvability

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson/

December 17, 2008

This is the abstract of my 15-minute talk at a special session on Logic and Dynamical Systems, sponsored by the American Mathematical Society (AMS) and the Association for Symbolic Logic (ASL). The session is part of the Joint Mathematics Meetings, January 5–8, 2009 in Washington, DC.

Abstract

Let A be a finite set of symbols. The 2-dimensional shift space on A is A^{ℤ×ℤ} with shift operators S_{1} and S_{2} given by S_{1}(x)(m, n) = x(m+1, n) and S_{2}(x)(m, n) = x(m, n+1). A 2-dimensional subshift is a nonempty, closed subset of A^{ℤ×ℤ} which is invariant under S_{1} and S_{2}. A 2-dimensional subshift is said to be of finite type if it is defined by a finite set of excluded finite configurations of symbols. We regard real numbers and points of A^{ℤ×ℤ} as Turing oracles. If X and Y are sets of Turing oracles, we say that X is Muchnik reducible to Y if each y ∈ Y can be used to compute some x ∈ X. The Muchnik degree of X is the equivalence class of X under mutual Muchnik reducibility. We prove that the Muchnik degrees of 2-dimensional subshifts of finite type are the same as the Muchnik degrees of nonempty, effectively closed sets of real numbers. We then apply known results about such Muchnik degrees to obtain an infinite family of 2-dimensional subshifts of finite type which are, in a certain strong sense, mutually independent. Our application is stated purely in terms of symbolic dynamics, with no mention of Muchnik reducibility.