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 class P of {0,1}N, there is an SFT X such that P×Z2 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.