On the Undecidability of the Tiling Problem

DOI10.1007/978-3-540-77566-9_7MaRDI QIDQ5448639zbMATH OpenOpenAlexFDO

Authors 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

mortality problemTuring machineWang tiles

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Undecidability and degrees of sets of sentences (03D35) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Recommendations

• The Tiling Problem Revisited (Extended Abstract)
• Piecewise affine functions, Sturmian sequences and Wang tiles
• The domino problem of the hyperbolic plane is undecidable
• The 4-way deterministic tiling problem is undecidable
• THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE

Cites work

• A small aperiodic set of Wang tiles
• A strongly aperiodic set of tiles in the hyperbolic plane
• Computability with low-dimensional dynamical systems
• Deciding stability and mortality of piecewise affine dynamical systems
• scientific article; zbMATH DE number 5605129 (Why is no real title available?)
• The Tiling Problem Revisited (Extended Abstract)
• The undecidability of the domino problem
• The undecidability of the Turing machine immortality problem

Cited in

(22)

• The 4-way deterministic tiling problem is undecidable
• From logic to tiling
• Tiling problems and undecidability in the cluster variation method.
• From decidability to undecidability by considering regular sets of instances
• 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
• Tilings: simulation and universality
• The Tiling Problem Revisited (Extended Abstract)
• scientific article; zbMATH DE number 1948487 (Why is no real title available?)
• About the domino problem for subshifts on groups
• Two-dimensional translation-invariant probability distributions: approximations, characterizations and no-go theorems
• Piecewise affine functions, Sturmian sequences and Wang tiles
• Fixed parameter undecidability for Wang tilesets
• The domino problem is undecidable on surface groups
• Subshifts with sparse traces
• The undecidability of the domino problem
• Decision problems on geometric tilings. Wang potatoes and finite local complexity
• Metallic mean Wang tiles. II: The dynamics of an aperiodic computer chip
• A general framework for quasi-isometries in symbolic dynamics beyond groups
• The domino problem of the hyperbolic plane is undecidable

This page was built for publication: On the Undecidability of the Tiling Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5448639)