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

\(\Pi_1^0\) classessubshift of finite typetilingsTuring degreeundecidability

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Symbolic dynamics (37B10) 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

• A small aperiodic set of Wang tiles
• An aperiodic set of 13 Wang tiles
• An Introduction to Symbolic Dynamics and Coding
• 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
• 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?)
• 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

(16)

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

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)