On the Undecidability of the Tiling Problem
From MaRDI portal
Publication:5448639
DOI10.1007/978-3-540-77566-9_7zbMath1133.03020OpenAlexW2131176118MaRDI QIDQ5448639
Publication date: 7 March 2008
Published in: SOFSEM 2008: Theory and Practice of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-77566-9_7
Undecidability and degrees of sets of sentences (03D35) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Turing machines and related notions (03D10)
Related Items (9)
Aperiodic SFTs on Baumslag-Solitar groups ⋮ \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\) ⋮ Full sets of pictures to encode pictures ⋮ Monadic second-order logic and the domino problem on self-similar graphs ⋮ About the Domino Problem for Subshifts on Groups ⋮ Two-dimensional translation-invariant probability distributions: approximations, characterizations and no-go theorems ⋮ Subshifts with sparse traces ⋮ Unnamed Item ⋮ From decidability to undecidability by considering regular sets of instances
Cites Work
- Unnamed Item
- A strongly aperiodic set of tiles in the hyperbolic plane
- A small aperiodic set of Wang tiles
- Computability with low-dimensional dynamical systems
- The Tiling Problem Revisited (Extended Abstract)
- The undecidability of the Turing machine immortality problem
- The undecidability of the domino problem
- Deciding stability and mortality of piecewise affine dynamical systems
This page was built for publication: On the Undecidability of the Tiling Problem
