×

zbMATH — the first resource for mathematics

The tiling problem revisited (extended abstract). (English) Zbl 1211.03062
Durand-Lose, Jérôme (ed.) et al., Machines, computations, and universality. 5th international conference, MCU 2007, Orléans, France, September 10–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74592-1/pbk). Lecture Notes in Computer Science 4664, 72-79 (2007).
Summary: We give a new proof for the undecidability of the tiling problem. Then we show how the proof can be modified to demonstrate the undecidability of the tiling problem on the hyperbolic plane, thus answering an open problem posed by R. M. Robinson [“Undecidability and nonperiodicity for tilings of the plane”, Invent. Math. 12, 177–209 (1970; Zbl 0197.46801)].
For the entire collection see [Zbl 1129.68003].

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