Turing degrees of multidimensional SFTs

DOI10.1016/j.tcs.2012.08.027zbMath1417.03241arXiv1108.1012OpenAlexW2025295595MaRDI QIDQ393140

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

undecidabilitysubshift of finite typetilings\(\Pi_1^0\) classesTuring degree

Mathematics Subject Classification ID

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

Related Items (11)

Factor maps and embeddings for random \(\mathbb{Z}^d\) shifts of finite type ⋮ Computability in Symbolic Dynamics ⋮ Cototal enumeration degrees and their applications to effective mathematics ⋮ Turing degree spectra of minimal subshifts ⋮ Computability of topological pressure on compact shift spaces beyond finite type* ⋮ Quasiperiodicity and Non-computability in Tilings ⋮ The relationship between word complexity and computational complexity in subshifts ⋮ Computability of countable subshifts in one dimension ⋮ The expressiveness of quasiperiodic and minimal shifts of finite type ⋮ Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy ⋮ On the Expressive Power of Quasiperiodic SFT.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computability of countable subshifts in one dimension
• Mass problems associated with effectively closed sets
• Effectively closed sets and enumerations
• An aperiodic set of 13 Wang tiles
• A small aperiodic set of Wang tiles
• Tilings and quasiperiodicity.
• Undecidability and nonperiodicity for tilings of the plane
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Complex tilings
• Computable symbolic dynamics
• Nonrecursive tilings of the plane. I
• Nonrecursive tilings of the plane. II
• An Introduction to Symbolic Dynamics and Coding
• Effective Symbolic Dynamics
• The undecidability of the domino problem
• ∏ 0 1 Classes and Degrees of Theories

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