DEGREES OF UNSOLVABILITY OF 2-DIMENSIONAL SUBSHIFTS OF FINITE TYPE Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.personal.psu.edu/t20 August 21, 2007 This is an abstract and references for a talk to be given at a Dynamical Systems Workshop at the Pennsylvania State University, Department of Mathematics, October 18-21, 2007. ABSTRACT We apply some fundamental concepts and results from mathematical logic in order to obtain an apparently new counterexample in symbolic dynamics. Two sets X and Y are said to be strongly equivalent if there exist partial recursive functionals from X into Y and vice versa. The strong degree of X is the equivalence class of X under strong equivalence. There is an extensive recursion-theoretic literature on the lattice of strong degrees of nonempty Pi^0_1 subsets of the Cantor space. This lattice is known as P_s. We prove that P_s consists precisely of the strong degrees of 2-dimensional subshifts of finite type. We use this result to obtain an infinite collection of 2-dimensional subshifts of finite type which are, in a certain sense, mutually incompatible. REFERENCES Stephen Binns and Stephen G. Simpson. Embeddings into the Medvedev and Muchnik lattices of Pi^0_1 classes. Archive for Mathematical Logic, 43:399-414, 2004. Albert A. Muchnik. On strong and weak reducibilities of algorithmic problems. Sibirskii Matematicheskii Zhurnal, 4:1328--1341, 1963. In Russian. Stephen G. Simpson. Medvedev degrees of 2-dimensional subshifts of finite type. Ergodic Theory and Dynamical Systems, to appear. Preprint, 8 pages, 1 May 2007. Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, 11:1-27, 2005. Stephen G. Simpson. An extension of the recursively enumerable Turing degrees. Journal of the London Mathematical Society, 75:287--297, 2007. Stephen G. Simpson. Mass problems and almost everywhere domination. Mathematical Logic Quarterly, 53:483--492, 2007. Stephen G. Simpson. Mass problems and intuitionism. Preprint, 9 pages, 1 August 2007, submitted for publication.