Turing degrees of multidimensional SFTs

Details Turing degrees of multidimensional SFTs Turing degrees of multidimensional SFTs

2011-08-04

arxiv.org/abs/1108.1012v2

Computer Science

Computational Complexity

arXiv admin note: substantial text overlap with arXiv:1102.1189

Scientific paper

In this paper we are interested in computability aspects of subshifts and in particular Turing degrees of 2-dimensional SFTs (i.e. tilings). To be more precise, we prove that given any \pizu subset $P$ of $\{0,1\}^\NN$ there is a SFT $X$ such that $P\times\ZZ^2$ is recursively homeomorphic to $X\setminus U$ where $U$ is a computable set of points. As a consequence, if $P$ contains a recursive member, $P$ and $X$ have the exact same set of Turing degrees. On the other hand, we prove that if $X$ contains only non-recursive members, some of its members always have different but comparable degrees. This gives a fairly complete study of Turing degrees of SFTs.

Affiliated with

Also associated with

No associations

Rating

Turing degrees of multidimensional SFTs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Turing degrees of multidimensional SFTs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turing degrees of multidimensional SFTs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-13898