×

zbMATH — the first resource for mathematics

Fixed point and aperiodic tilings. (English) Zbl 1161.68033
Ito, Masami (ed.) et al., Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85779-2/pbk). Lecture Notes in Computer Science 5257, 276-288 (2008).
Summary: An aperiodic tile set was first constructed by R. Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals)
We present a new construction of an aperiodic tile set that is based on Kleene’s fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann self-reproducing automata; similar ideas were also used by P. Gács in the context of error-correcting computations.
The flexibility of this construction allows us to construct a “robust” aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. This property was not known for any of the existing aperiodic tile sets.
For the entire collection see [Zbl 1147.68007].

MSC:
68Q80 Cellular automata (computational aspects)
05B45 Combinatorial aspects of tessellation and tiling problems
PDF BibTeX XML Cite
Full Text: DOI arXiv