Résumé
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. Gacs in the context of error-correcting
computations. This construction it rather flexible, so it can be used in many
ways: we show how it can be used to implement substitution rules, to construct
strongly aperiodic tile sets (any tiling is far from any periodic tiling), to
give a new proof for the undecidability of the domino problem and related
results, characterize effectively closed 1D subshift it terms of 2D shifts of
finite type (improvement of a result by M. Hochman), to construct a tile set
which has only complex tilings, and 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. For the latter we develop a hierarchical
classification of points in random sets into islands of different ranks.
Finally, we combine and modify our tools to prove our main result: there exists
a tile set such that all tilings have high Kolmogorov complexity even if
(sparse enough) tiling errors are allowed.