On the Undecidability of the Tiling Problem

DOI10.1007/978-3-540-77566-9_7zbMath1133.03020OpenAlexW2131176118MaRDI QIDQ5448639

Jarkko Kari

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

zbMATH Keywords

Turing machineWang tilesmortality problem

Mathematics Subject Classification ID

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