Tiles

Mathematical Weirdness
You Can Hold In Your Hand




Paul Harrison @paulfharrison

Wang Invents Wang Tiles
And Makes A Wrong Conjecture

Wang (1961, section 4.1, A Generalized Game Of Dominos)

Given a set of squares with colored edges, can we tile the plane with copies of these squares so all the edge colors match?
(Rotations and reflections are not allowed.)


Wang's conjecture:
If we can tile the plane, we can do so with a repeating pattern.


Wang's student Berger (1966) showed this is wrong.
There are aperiodic tile-sets.

Aperiodic Wang Tile-sets

Berger's initial construction used 20,426 tiles.

The number of tiles needed has been whittled down over time.

Jeandel and Rao (2015) proved the minimum to be 11 tiles:

(Images from paper.)Berger's main application of this was to be able to construct, for any specified Turing machine, a tile-set that contains somewhere within it the Turing machine tape at any number of steps of evaluation. If the Turing machine halts, the tiles will not tile the plane. Since the halting problem is undecidable, knowing in all cases whether a tile-set will tile the plane is also undecidable.

Penrose Tiles

Penrose (1974, patented 1975) found a set of 6 tiles that is aperiodic, and later reduced this to 2 tiles. Roughly, Penrose tiles are obtained by trying to tile the regular pentagon, which does not work and needs further shapes to fill in gaps.

There are several versions of Penrose tiles with only 2 tiles. This variant has thin and fat rhombuses: