zbMATH — the first resource for mathematics

On the undecidability of the tiling problem. (English) Zbl 1133.03020
Geffert, Viliam (ed.) et al., SOFSEM 2008: Theory and practice of computer science. 34th conference on current trends in theory and practice of computer science, Nový Smokovec, Slovakia, January 19–25, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-77565-2/pbk). Lecture Notes in Computer Science 4910, 74-82 (2008).
Summary: The tiling problem is the decision problem to determine if a given finite collection of Wang tiles admits a valid tiling of the plane. In this work we give a new proof of this fact based on tiling simulations of certain piecewise affine transformations. A similar proof is also shown to work in the hyperbolic plane, thus answering an open problem posed by R. M. Robinson in [“Undecidability and nonperiodicity for tilings of the plane”, Invent. Math. 12, 177–209 (1971; Zbl 0199.30802)].
For the entire collection see [Zbl 1131.68008].

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