On the undecidability of the tiling problem. (English) Zbl 1133.03020

Kari, Jarkko

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)

Keywords:

Wang tiles; mortality problem; Turing machine