SYMBOLIC DYNAMICS AND DEGREES OF UNSOLVABILITY Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.personal.psu.edu/t20/ 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^ZxZ 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^ZxZ 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^ZxZ as Turing oracles. If X and Y are sets of Turing oracles, we say that X is Muchnik reducible to Y if each y\in Y can be used to compute some x\in 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.