Nothing decides whether a set of tiles tiles the plane

Everything else in this collection is decided. A pattern either has a symmetry or it does not, and finding out is integer arithmetic with no tolerance to choose. A lattice either permits a five-fold rotation or it does not. A set of translations either closes into a group or it does not. Twelve fields of that make it easy to believe that the subject is decidable throughout, and it is not.

One question away sits a problem no algorithm answers: given a finite set of tiles, do they cover the plane?

The result is Berger’s, from 1966, and it is called the domino problem. Robinson gave a shorter proof in 1971. What is being said is not that the search is long: it is that a set of tiles can be made to carry out a computation, so an algorithm deciding tiling would decide whether a machine halts, and no algorithm does that.

The two half-searches #

What is available is two procedures, each of which answers one way and never the other.

A periodic certificate. Search for a block that tiles a torus: one whose right edge matches its own left and whose top matches its own bottom. Finding one settles the question, because the block repeats and the repetition covers the plane. This search terminates on every set that tiles periodically and runs for ever on the rest.

A finite obstruction. Search for a square that cannot be tiled at all. Finding one settles the question the other way, because a tiling of the plane contains squares of every size, so a square that cannot be filled means the plane cannot be either. This search terminates on every set that cannot tile and runs for ever on the rest.

Run both at once and every set that either tiles periodically or fails outright is decided. What is left over is the set of tile sets that cover the plane and admit no periodic tiling at all. That residue is not empty — aperiodic sets exist, and are the reason Penrose’s rhombs are famous — and on such a set both searches run for ever.

The residue, measured #

The theorem says the gap cannot be closed. What can be done is to look at it.

Tile sets are generated from a fixed seed, both searches are run to a stated bound, and the three outcomes are counted: tiles, with a block; cannot, with the square that fails; and unknown at this bound.

Raising the bound moves sets out of the third column, one or two at a time, and the cost of each step rises much faster than the number of answers it buys.

And there is an argument that no bound can ever be enough, which does not need the theorem restated. Suppose the size of the smallest periodic block were bounded by some computable function of the number of tiles. Then the two searches together would decide every case: run the block search up to that bound, and if nothing is found, the set cannot tile periodically — and by the bound, cannot tile at all. That would decide the domino problem. So no such function exists, and the smallest block a tiling set needs grows faster than anything that can be computed.

Why a torus is enough #

The certificate search looks for a tiling of a torus rather than of a square, and the difference is worth a paragraph because it is what makes the search a proof.

A tiled square proves nothing about the plane: the edges may be a dead end, with no legal way to continue outwards, and a search that filled a hundred-square region would still have proved only that a hundred-square region can be filled. A tiled torus is different. Its right edge matches its own left and its top matches its own bottom, so the block may be laid down beside itself in every direction without ever consulting the tiles again. The infinite object is built by a rule the block itself certifies.

That is the same structure as a lattice translation: a finite piece plus a repetition, with the repetition guaranteed by the piece. The block is a fundamental domain and the torus is the quotient, and the certificate is a statement that the quotient can be tiled.

What an aperiodic set is, in this language #

A set is aperiodic when it tiles the plane and no tiling by it has any translational symmetry. Such a set is precisely a permanent inhabitant of the third column: the obstruction search fails at every size because every square can be filled, and the block search fails at every size because no periodic tiling exists.

Berger’s proof produced one with 20,426 tiles. Robinson reduced it to six; Culik and Kari found sets of thirteen; and in 2015 Jeandel and Rao showed by an exhaustive search that eleven tiles and four colours is the smallest possible — a result that is itself a computation, and one much larger than anything here.

Nothing in this collection reproduces any of that. No Turing machine is built here, encoded here, or simulated here; the undecidability is cited. What is measured is the behaviour of the two searches, which is a fact about them.

A set whose smallest block is large behaves exactly like an aperiodic set until the search reaches it, and from outside there is nothing to tell them apart. Both fill every square the obstruction search tries; both defeat every block size the certificate search reaches. The only difference is that one of them would eventually yield, at a size nobody knows in advance and no computable function bounds. That is why the third column is a statement about the bound rather than about the tile sets, and why calling it “the aperiodic ones” would be an error the measurement itself cannot detect.

Why the shapes on this site are not in that difficulty #

It is worth being exact about what remains decidable, because most of this collection lives there.

Whether a given pattern has a given symmetry is decidable, and cheaply: apply the operation, compare the point sets. That is the round trip and it is the site’s whole method.

Whether a shape tiles the plane by a group is decidable for a fixed group: it is a question about a fundamental domain and comes down to solving finitely many equations. Which convex polygons tile the plane alone is a harder question of a different kind, and for convex polygons it is settled — the answer is a finite list, closed in 2017 — because convexity is a very strong restriction.

Whether a single connected shape tiles the plane is not known to be decidable and not known to be undecidable, which is a third state worth naming.

The obstruction search, and why it is the useful half #

In practice the two half-searches are not symmetric. Almost every set that cannot tile fails at a small square, because failure usually comes from a local incompatibility — a colour that appears on no other tile’s opposite edge, or a pair that cannot meet in either order. Those are caught at two or three tiles across.

The block search is the expensive one. Its cost grows with the fourth power of the block’s side in the size of the state space alone, and the sets that need a large block are exactly the ones the search cannot afford to reach. So the practical shape of the computation is: obstructions first, cheaply, and then as much of the block search as there is time for.

That asymmetry is not a fact about undecidability, and it is worth separating from one. Both procedures are semi-decisions and neither is preferred by the theorem; what differs is how much of the sample each of them settles at a given cost, which is a measurement of these tile sets and not of the problem.

From twenty thousand tiles to one #

The aperiodic sets are the reason the problem is undecidable, and the size of the smallest known one has fallen by four orders of magnitude in sixty years. The sequence is worth having, because each step is a different kind of achievement.

Berger’s set, 1966: 20,426 tiles. It exists because the proof needed one, and its size is the size a Turing machine’s encoding happened to come to. Nobody was economising.

Robinson’s set, 1971: six tiles. A deliberate simplification, built round a hierarchy of squares forcing squares of twice the size, and small enough to draw. This is the set most often reproduced.

Penrose’s tiles, 1974: two. The kite and dart, with matching rules — and with a five-fold structure that turned out to be the geometry a diffraction pattern would later show, which is why they are the pair everybody knows.

And one, in 2023. A single connected shape — the hat, found by Smith, Myers, Kaplan and Goodman-Strauss — tiles the plane and admits no periodic tiling, using reflected copies as well as rotated ones. A second shape, the spectre, followed within weeks and needs no reflections at all, which closes the objection that a shape and its mirror image are two tiles.

That last step had been open since the question was first asked, and it matters here for a specific reason. A single aperiodic tile does not make the single-tile problem undecidable — undecidability needs a family rich enough to encode a computation, and one shape is one shape. What it does is remove the only structural reason anybody had for expecting the single-tile question to be easier than the general one, which leaves that question exactly where this essay left it: not known to be decidable, and not known not to be.

What happens one dimension down #

The boundary the last section is about can be located precisely on one side, and locating it says how little room there is between decidable and not.

Run the same problem in one dimension. The tiles are bars with a colour at each end, a tiling of the line is a sequence in which adjacent ends match, and the question is whether an infinite such sequence exists. That is decidable, easily. Build a graph with one vertex per colour and one edge per tile; a tiling of the line is an infinite walk on that graph, and an infinite walk exists exactly when the graph has a cycle reachable from somewhere — which a finite search settles.

The same argument says more: if a set of bars tiles the line at all, it tiles it periodically, because an infinite walk on a finite graph must repeat a vertex. So there are no aperiodic sets in one dimension, both half-searches always terminate, and the third column of the census is empty by a theorem.

Everything therefore happens between one dimension and two, and what changes is that a tiling of the plane has no such linear structure to be pumped. A walk revisiting a vertex closes; a partial tiling revisiting a configuration need not, because the configuration it revisits is a whole frontier rather than a single state, and the frontier grows.

The growing frontier is the whole of the difference and it is worth saying precisely why it defeats the argument. A pumping argument needs a state space that does not depend on how far the construction has gone: a finite graph has finitely many vertices, so a walk of length greater than the vertex count must repeat one, and the segment between the two visits can be repeated for ever. Extend a partial tiling of the plane outward and the boundary that has to be remembered is the whole perimeter of what has been placed, which grows without bound — so the number of distinct states grows without bound too, and no walk is long enough to be forced to repeat one.

That is not a failure of ingenuity; it is a structural difference, and it recurs. Every decidable question in this collection has a bounded state to carry: a fundamental domain, a finite set of operations, a Gram matrix, a residue class. Every undecidable one has a state that grows with the object. The dimer count of the previous rung is a good contrast — its transfer matrix carries a boundary too, but the boundary is one row of a rectangle of fixed width, so the state stays bounded and the count stays computable, and widening the rectangle is what makes the cost explode rather than making the question undecidable.

One more consequence is worth drawing, because it explains the shape of the aperiodic sets themselves. If a tiling set is to defeat the block search at every size, its tilings must contain structure at every scale — there must always be something larger than the block just tried. Robinson’s six tiles do that explicitly, by forcing squares that force squares of twice the size, for ever; Penrose’s do it by inflation. A hierarchy is not one way of building an aperiodic set; it is close to being the only way anybody has found, and the reason is legible in the search it has to defeat.

Where the boundary actually runs #

The instinct after meeting an undecidable problem is that the boundary must lie somewhere exotic. It does not. Three small changes each move the question back across it.

Fix the group. Ask whether a set of tiles admits a tiling invariant under a given plane group, and the question becomes finite: there are finitely many ways to fill a fundamental domain, and closure decides the rest.

Fix the region. Ask whether a set tiles an n × n square and it is a finite search, which is what the obstruction procedure runs.

Ask about a torus rather than a plane. That is the certificate search, and it terminates.

What is undecidable is the combination of an infinite region with no assumed symmetry, and that combination is exactly the situation aperiodic order lives in. It is not a coincidence that the same setting produced Penrose’s tilings and that the first aperiodic sets came out of the proof of undecidability rather than out of any desire for pretty patterns. Berger built his set in order to prove the theorem, and everything since — including the tilings a real quasicrystal is modelled with — descends from a construction whose purpose was a negative result.

What the searches cannot be asked #

Two limits, both about interpretation rather than about code.

An unknown is not an aperiodic set. The residue contains sets whose smallest period is merely large, and no measurement distinguishes them from sets with no period at all. Reporting the third column as “the aperiodic ones” would be a claim the search cannot support, and the count would be wrong in a direction nobody could check.

A sample says nothing about the density of aperiodic sets. The sets here are generated from a seed with a stated number of tiles and colours; changing either changes the proportions completely. Aperiodic sets are rare in any such sample — Jeandel and Rao’s exhaustive search over small sets found very few — and nothing about a sample of eighty licenses an estimate.

What a decision procedure would have to look like #

It is worth asking what is missing, rather than only that something is.

A decision procedure would have to answer in finite time on every input, which means that for each tile set it would have to reach a point where it could stop and commit. The obstruction search commits when it finds a square that fails. The certificate search commits when it finds a block. Any third procedure would have to commit in some other way — on a structural property of the tile set, read off without an unbounded search.

No such property can exist, and the reason is the encoding. Berger’s construction turns a machine and its input into a tile set whose tilings are the machine’s computations, so a structural property deciding tiling would decide halting. The impossibility is not about tiles at all: it is inherited, and tiles are merely a place where computation can be made to live.

That is worth carrying to the rest of this collection. The reason a plane group’s questions are decidable is not that they are easy. It is that assuming a symmetry group collapses an infinite object to a finite one — a fundamental domain, a quotient, a finite set of operations — and every decidability result here rests on that collapse. Remove the assumption and the collapse goes with it.

The clearest case of that collapse in this collection is the list of tilings by regular polygons. Requiring every vertex to look the same is a symmetry assumption wearing other clothes, and it turns an infinite question into an equation in a handful of integers: the angles at a vertex must sum to a full turn, which admits finitely many multisets of regular polygons, and checking which of those extend is a small finite job. Eleven tilings exist and the list is closed. The Wang question permits no such reduction, because nothing has been assumed about how one part of the plane resembles another.

Who found it, and what they were doing #

Hao Wang introduced the tiles in 1961, while working on a decision procedure for a fragment of logic. He observed that the domino problem would be decidable if every tileable set had a periodic tiling, and conjectured that one always did.

Robert Berger, his student, proved the conjecture false in 1966 by constructing an aperiodic set, and then used the same machinery to prove the domino problem undecidable. Raphael Robinson simplified both in 1971, down to six tiles with a hierarchical structure that is still the clearest way to see how a tiling can be forced to encode arbitrarily large structure. Roger Penrose’s rhombs arrived in 1974, and the connection between them and quasicrystals was made after Shechtman’s diffraction pattern in 1982 — which is to say, in the wrong order for a subject that is usually told as physics leading mathematics.

Where the ladder goes next #

The natural next rung asks what can be extracted from a tiling that is not decidable in bulk: local rules that force global structure, which is what matching rules do, and the complexity measures that count patches rather than deciding anything — how many patches of each size a tiling has, which is a measurement that always terminates.

The other direction is the one this collection is otherwise built on: with a group assumed, everything becomes decidable again, and the whole classification of the plane follows. Undecidability is what is left when the assumption of symmetry is removed, and the size of the difference between the two situations is worth carrying back into every essay where the group was simply given.

Both halves of that sequence are worth holding together. The count of tiles fell because people looked for smaller sets; the undecidability did not move at all, because it was never a statement about how many tiles are needed. A set of one aperiodic tile and a theorem that no algorithm decides the general question are compatible, and reading either as evidence about the other is the error the two paragraphs above are arranged to prevent.