Abstract:
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. The flexibility of this construction simplifies proofs of some known results and 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. Our construction of an aperiodic self-similar tile set 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.