An aperiodic set of 11 Wang tiles

A Wang tile is a square tile such that each of its edges is colored. The plane can be tiled with a set of Wang tiles if tiles contained in the set can be placed in the plane without rotations and reflections such that the whole plane is covered and the colors of their edges match at adjacent tiles. Wang tiles were introduced by Wang in 1961 to study decidability in mathematical logic, and they are also of relevance to other areas of theoretical computer science.

Wang conjectured that if the plane can be tiled with a set of Wang tiles, then it can be tiled in a periodic way. This was refuted by Berger in 1966 who described how a Turing machine computation can be emulated by Wang tilings and constructed a set of 104 Wang tiles for which the plane can be tiled with the set but only aperiodically. In the first volume of The Art of Computer Programming, Knuth presented a simplified version of Berger’s set with 92 Wang tiles. Smaller sets of Wang tiles that tile the plane only aperiodically were subsequently constructed with the smallest set containing 13 Wang tiles, found by Culik II in 1996.

The authors construct a set of 11 Wang tiles with edges colored with four colors such that the plane can be tiled with the set but each tiling is aperiodic. Moreover, they establish that there is no set of at most 10 Wang tiles with this property. The number of colors is also the best possible as it is known that every set of Wang tiles with edges colored with at most three colors either can tile the plane periodically or cannot tile the plane at all.