TR08-030 Authors: Bruno Durand, Alexander Shen, Andrei Romashchenko

Publication: 18th March 2008 16:41

Downloads: 2171

Keywords:

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.