Turing degrees of multidimensional SFTs

DOI10.1016/J.TCS.2012.08.027MaRDI QIDQ393140zbMATH OpenOpenAlexFDO

Authors Emmanuel Jeandel, Pascal Vanier

Publication date 16 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.1012

zbMATH Keywords

tilingsundecidabilitysubshift of finite type\(\Pi_1^0\) classesTuring degree

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Other Turing degree structures (03D28) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Abstract: 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}^{N}N$ there is a SFT $X$ such that $$ is recursively homeomorphic to $XsetminusU$ 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.

Recommendations

• Multidimensional shifts of finite type and sofic shifts
• $\it \Pi^0_1$ Sets and Tilings
• Characterizations of periods of multi-dimensional shifts
• Computability of countable subshifts
• Computability of countable subshifts in one dimension

Cites work

• scientific article; zbMATH DE number 1303200 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 3222108 (Why is no real title available?)
• A small aperiodic set of Wang tiles
• An Introduction to Symbolic Dynamics and Coding
• An aperiodic set of 13 Wang tiles
• Complex tilings
• Computability of countable subshifts in one dimension
• Computable symbolic dynamics
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Effective symbolic dynamics
• Effectively closed sets and enumerations
• Mass problems associated with effectively closed sets
• Nonrecursive tilings of the plane. I
• Nonrecursive tilings of the plane. II
• Structural aspects of tilings
• The undecidability of the domino problem
• Tilings and quasiperiodicity.
• Undecidability and nonperiodicity for tilings of the plane
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(15)

• Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type
• Computability of countable subshifts in one dimension
• The relationship between word complexity and computational complexity in subshifts
• Medvedev degrees of two-dimensional subshifts of finite type
• The expressiveness of quasiperiodic and minimal shifts of finite type
• Quasiperiodicity and non-computability in tilings
• On the expressive power of quasiperiodic SFT
• Computability in Symbolic Dynamics
• Turing degree spectra of minimal subshifts
• Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy
• Computability of topological pressure on compact shift spaces beyond finite type*
• Factor maps and embeddings for random \(\mathbb{Z}^d\) shifts of finite type
• Cototal enumeration degrees and their applications to effective mathematics
• On derivatives and subpattern orders of countable subshifts
• Seas of squares with sizes from a \(\Pi_{1}^{0}\) set

This page was built for publication: Turing degrees of multidimensional SFTs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393140)