The Domino Problem of the Hyperbolic Plane Is Undecidable: New Proof
Maurice Margenstern
Laboratoire de Génie Informatique, de Production et de Maintenance
EA 3096
Université de Lorraine, Bâtiment A de l’UFR MIM
3 rue Augustin Fresnel
BP 45112
57073 Metz Cedex 03, France
maurice.margenstern@univ-lorraine.fr
Abstract
The present paper revisits the proof given in a paper of the author published in 2008 proving that the general tiling problem of the hyperbolic plane is algorithmically unsolvable by proving a slightly stronger version using only a regular polygon as the basic shape of the tiles. The problem was raised by a paper of Raphael Robinson in 1971, in his famous simplified proof that the general tiling problem is algorithmically unsolvable for the Euclidean plane, initially proved by Robert Berger in 1966. The present construction improves that of the 2008 paper. It also very strongly reduces the number of prototiles.
Keywords: hyperbolic plane; tilings; tiling problem; algorithmic unsolvability
Cite this publication as:
M. Margenstern, “The Domino Problem of the Hyperbolic Plane Is Undecidable: New Proof,” Complex Systems, 32(1), 2023 pp. 19–56.
https://doi.org/10.25088/ComplexSystems.32.1.19
