Turing degrees of multidimensional SFTs
In this paper, we are interested in computability aspects of subshifts and in particular Turing degrees of two-dimensional subshifts of finite type (SFTs) (i.e., tilings). To be more precise, we prove that, given any Pi(0)(1) class P of {0, 1}(N), there is an SFT X such that P x Z(2) is recursively homeomorphic to X \ U, where U is a computable set of points. As a consequence, if P contains a computable member, P and X have the exact same set of Turing degrees. On the other hand, we prove that, if X contains only non-computable members, some of its members always have different but comparable degrees. This gives a fairly complete study of Turing degrees of SFTs. (C) 2012 Elsevier B.V. All rights reserved.
turing degree subshift of finite type tilings pi(0)(1) classes undecidability