Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-030 | 16th November 2007 00:00

Fixed Point and Aperiodic Tilings


Authors: Bruno Durand, Alexander Shen, Andrei Romashchenko
Publication: 18th March 2008 16:41
Downloads: 2946


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.

ISSN 1433-8092 | Imprint