Turing degrees of multidimensional SFTs
From MaRDI portal
Publication:393140
DOI10.1016/j.tcs.2012.08.027zbMath1417.03241arXiv1108.1012MaRDI 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
37B10: Symbolic dynamics
52C20: Tilings in (2) dimensions (aspects of discrete geometry)
03D28: Other Turing degree structures
Related Items
Cototal enumeration degrees and their applications to effective mathematics, The expressiveness of quasiperiodic and minimal shifts of finite type, Computability of topological pressure on compact shift spaces beyond finite type*, On the Expressive Power of Quasiperiodic SFT., Computability of countable subshifts in one dimension, 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, Computability in Symbolic Dynamics
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