zbMATH — the first resource for mathematics

High complexity tilings with sparse errors. (English) Zbl 1248.68266
Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 403-414 (2009).
Summary: Tile sets and tilings of the plane appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals). The idea is to enforce some global properties (of the entire tiling) by means of local rules (for neighbor tiles). A fundamental question: Can local rules enforce a complex (highly irregular) structure of a tiling?
The minimal (and weak) notion of irregularity is aperiodicity. R. Berger constructed a tile set such that every tiling is aperiodic. Though Berger’s tilings are not periodic, they are very regular in an intuitive sense.
In [B. Durand, L. A. Levin and A. Shen, J. Symb. Log. 73, No. 2, 593–613 (2008; Zbl 1141.03021)] a stronger result was proven: There exists a tile set such that all \(n\times n\) squares in all tilings have Kolmogorov complexity \(\Omega (n)\), i.e., contain \(\Omega (n)\) bits of information. Such a tiling cannot be periodic or even computable.
In the present paper we apply the fixed-point argument from [B. Durand, A. Romashchenko and A. Shen, Lect. Notes Comput. Sci. 5257, 276–288 (2008; Zbl 1161.68033)] to give a new construction of a tile set that enforces high Kolmogorov complexity tilings (thus providing an alternative proof of the results of [Durand, Levin and Shen, loc. cit.]). The new construction is quite flexible, and we use it to prove a much stronger result: there exists a tile set such that all tilings have high Kolmogorov complexity even if (sparse enough) tiling errors are allowed.
For the entire collection see [Zbl 1166.68001].

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
05B45 Combinatorial aspects of tessellation and tiling problems
Full Text: DOI