wang-tiles.md

A Wang tile is a square with a colour on each of its four edges. Take a finite set of them and as many copies of each as you like, and lay them on the square grid without turning or flipping any, so that wherever two tiles touch, the shared edge has the same colour on both sides. Wang 1961 calls them plates, and asks which sets can cover the whole plane.

The figure is a 10 by 10 patch of the set of Jeandel and Rao 2015, 11 tiles on 4 colours. Each edge colour is drawn as a small triangle pointing into its tile, so a matched edge shows as a diamond, two triangles of one colour meeting across the gap. All 11 tiles appear and all 180 inner edges match. The patch is found the way a computer searches: lay tiles in reading order, and step back whenever nothing fits.

Whether a set covers the plane is the domino problem, and half of it is easy. A set that cannot tile some square cannot tile the plane. A set that tiles squares of every size does tile the plane: of the finitely many ways to fill the middle cell, one sits in the middle of infinitely many of those squares, so fix it; among those squares a way to fill the ring round it recurs infinitely often, so fix that, and keep going outward. So a program that tries square after square stops with no whenever the answer is no. For the other half, a set that tiles a square whose left edge matches its right and whose top matches its bottom tiles the plane by repeating that square, periodically. Wang's conjecture is that every set that tiles the plane can also tile it periodically, and if it held, a program that looks for both at once would always stop with the answer.

The conjecture is false. Berger 1966 builds a set of 20,426 tiles that tiles the plane but never periodically, an aperiodic set. With it he turns any computer program into a set of tiles that covers the plane exactly when the program runs for ever. No program can decide which programs run for ever, so no program can decide which sets tile the plane: the domino problem is undecidable. The aperiodic set is not an accident of the proof. If every set that tiles could tile periodically, the two searches above would decide everything.

Far smaller sets exist. Robinson 1971 gives six tiles, squares with notched edges that may be turned and flipped, which tile only without repeating, and a shorter proof of Berger's theorem. Jeandel and Rao reach the end of that road: their 11 tiles on 4 colours are aperiodic, a computer search over every smaller set shows that no set of 10 tiles or fewer is, and no set on fewer than 4 colours is either.

A tiling by a Wang set is a subshift of finite type in two dimensions. The letters are the tiles, written in the cells of the grid, and the forbidden words are the pairs that clash, side by side or one above the other. The other way round, any two-dimensional rule of that kind can be rewritten as a Wang set, with the allowed blocks of its window as tiles and their overlaps as edge colours. On a line the picture is tame: the rule is a walk through a finite table, a walk that goes on for ever must come back to some state, and from there it can repeat its loop, so a line rule that allows anything at all allows a periodic string, and whether it allows anything is read off the table. In the plane both facts fail, and Wang tiles are why.

The history of a cellular automaton is a Wang tiling. For an elementary rule make one tile for each of the eight neighbourhoods (l, c, r): its top edge carries c, its bottom edge the rule's answer for (l, c, r), its left edge the pair (l, c) and its right edge the pair (c, r). Side by side, the right edge of a tile must equal the left edge of the next, so neighbouring tiles agree on the row they read. One above the other, the bottom of a tile must equal the top of the tile below, so each row is the rule applied to the row above. With two colours on their tops and bottoms and four on their sides, the eight tiles cover the plane in exactly the ways the rule can run for all time, the rows being the generations and time running down.

A substitution tiling, built top down by cutting tiles into smaller tiles, can often be held together bottom up by a Wang set, and a theorem of Mozes on substitution tilings makes that exact, which turns many non-repeating substitutions into aperiodic sets of tiles.

In the tree

The automata reads the history of an affine rule from one live cell as a design of the tree, so those designs are patches laid with the eight tiles of their rule, and the wolfram demo runs any of the 256 rules that way. Beneath a design prices window rules on a line, the one-dimensional subshifts of finite type whose counts come from one table; a Wang set is the same kind of rule in the plane, where no single table does the counting.