Degrees of unsolvability of 2-dimensional subshifts of finite type

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

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 recursiontheoretic literature on the lattice of strong degrees of nonempty Π_{1}^{0} 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

[1] Stephen Binns and Stephen G. Simpson. Embeddings into the Medvedev and Muchnik lattices of Π_{1}^{0} classes. Archive for Mathematical Logic, 43:399– 414, 2004.

[2] Albert A. Muchnik. On strong and weak reducibilities of algorithmic problems. Sibirskii Matematicheskii Zhurnal, 4:1328–1341, 1963. In Russian.

[3] 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.

[4] Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, 11:1–27, 2005.

[5] Stephen G. Simpson. An extension of the recursively enumerable Turing degrees. Journal of the London Mathematical Society, 75:287–297, 2007.

[6] Stephen G. Simpson. Mass problems and almost everywhere domination. Mathematical Logic Quarterly, 53:483–492, 2007.

[7] Stephen G. Simpson. Mass problems and intuitionism. Preprint, 9 pages, 1 August 2007, submitted for publication.