Aperiodic Tiling

An aperiodic tiling is a tiling obtained from an aperiodic set of tiles. A set of tile-types (or prototiles) is aperiodic if there are some tilings using only these types, and all such tilings are non-periodic. Properly speaking, aperiodicity is a property of the set of prototiles; the tilings themselves are merely non-periodic. Typically, distinct tilings may be obtained from a single aperiodic set of tiles.

The various Penrose tiles are the best-known examples of an aperiodic set of tiles.

Quasicrystals — physical materials with the apparent structure of the Penrose tilings — were discovered in 1982 by Dan Shechtman who subsequently won the Nobel prize in 2011. However, the specific local structure of these materials is still poorly understood.

A given set of tiles, in the Euclidean plane or some other geometric setting, admits a tiling if non-overlapping copies of the tiles in the set can be fitted together to cover the entire space. A given set of tiles might admit periodic tilings — that is, tilings which remain invariant after being shifted by a translation (for example, a lattice of square tiles is periodic). It is not difficult to design a set of tiles that admits non-periodic tilings as well (for example, randomly arranged tilings using a 2×2 square and 2×1 rectangle will typically be non-periodic). An aperiodic set of tiles, however, admits only non-periodic tilings.

Few methods for constructing aperiodic tilings are known. This is perhaps natural: the underlying undecidability of the Domino problem implies that there exist aperiodic sets of tiles for which there can be no proof that they are aperiodic.