Dominoes that no algorithm can match

The undecidable problems in the essays before this one were all about programs. Whether a program halts, whether it ever prints a 7, whether it computes a given function — every one of them was a question about what a machine does, and the proofs that no algorithm answers them were diagonal arguments about machines reading machines. The pattern goes back to the start of the sequence: the row missing from every list was built by reading a list against itself, the sentence that says it has no proof by letting a formal system describe its own sentences, and the program that prints itself by handing a program its own text. That leaves an impression that undecidability lives in self-reference, and that a question with no programs in it would be safe.

In 1946 Emil Post found a question with no programs in it at all. It is a puzzle about dominoes. Each domino carries a string on its top half and a string on its bottom half. Given a finite set of them, with as many copies of each as needed, is there a row of dominoes, at least one long, in which the top halves spell exactly the same word as the bottom halves?

This is a set of four dominoes from the standard textbook account of the problem, and the figure shows a match. Laid in the order 2, 1, 3, 2, 4, the tops spell a, b, ca, a, abc — abcaaabc — and the bottoms spell ab, ca, a, ab, c — the same word. The tints show the trick: the top and bottom rows cut the word in different places, and the dominoes have been chosen so that the cuts can be made to come out level at the end.

Post proved that no algorithm can take an arbitrary set of dominoes and decide whether it has a match. The puzzle is now called Post’s correspondence problem, and it has become the standard route by which undecidability is carried into places where there are no programs: grammars, matrices, tilings, equations over words. This essay is about why a puzzle this plain can hide a computer, and what that does to the length of its answers.

Searching by the overhang #

The first thing to notice is that the problem is half-decidable. If a set of dominoes has a match, a search will find it: try every row of length one, then every row of length two, and so on, and check each. The search only has to remember one thing about a partial row — which edge is ahead, and by what characters — because that is all that decides which dominoes can come next. Everything already matched is finished business.

The figure runs that search on a set of three small dominoes: 0 over 01, 010 over 0, and 1 over 00. A row has to start with a domino whose top and bottom agree as far as the shorter one goes, which rules out the third. The first leaves the bottom one character ahead, a 1; the second leaves the top ahead by 10, and from there no domino can follow, because every domino’s bottom starts with 0. From the surviving position the search extends one domino at a time, and each box records only the overhang: the characters the longer row has written that the shorter one still owes. The rows of the search widen slowly, a position at a time.

The search is breadth-first, so the first match it finds is a shortest one. And it is a procedure that stops when a match exists. What it cannot do is stop when no match exists. The positions can go on multiplying for ever, each one consistent so far, and nothing in the search distinguishes a set that will eventually match from one that never will. Post’s theorem says that this is not a weakness of the search but of every method: there is no algorithm that always stops and always answers correctly.

Three dominoes, thirty-six in a row #

Before turning to why, it is worth seeing how long the search can take on sets that do have a match.

The three dominoes in the search figure have a match, and the shortest one is thirty-six dominoes long. It spells a word of sixty characters, and the search visits 7,379 positions before reaching it. The chart under the sequence shows why it takes so long. The bottom row runs ahead from the first domino, the overhang growing to ten characters, and then hovers for most of the sequence while the dominoes rearrange what the overhang contains. Only at the end does the top catch up, and only one exact arrangement of the owed characters allows it to.

A shortest match of thirty-six from three dominoes with no string longer than three characters is not a curiosity. Among small sets of dominoes, short strings over two letters already produce shortest matches in the dozens and, in published searches of slightly larger sets, run into the hundreds. The obvious question is whether the length of the shortest match can be bounded in advance, by some formula in the number and size of the dominoes. If it could, the problem would be decidable: search up to the bound, and if nothing is found, there is nothing to find. The theorem therefore says something precise about these lengths: no computable formula bounds them.

A machine laid out in dominoes #

The proof of Post’s theorem is a translation. Given a Turing machine, it builds a set of dominoes that has a match exactly when the machine, started on a blank tape, halts. Since whether a machine halts cannot be decided, neither can whether dominoes match.

The translation writes the machine’s run as a string. A configuration — the tape, the machine’s state and the position of its head — is written as the tape’s symbols with the state’s letter inserted just before the cell the head is reading, and configurations are separated by the symbol #. A run from start to halt is then a long word: configuration, #, configuration, #, and so on. The dominoes are designed so that the only way to make the top and bottom spell the same word is to spell this one.

The first domino has # on top and # followed by the starting configuration on the bottom, so from the outset the bottom is one configuration ahead. To catch up, the top must reproduce that configuration, and the dominoes that let it do so each copy a cell — 1 over 1, blank over blank, # over # — except near the head. There the only dominoes available are the machine’s rules: a domino with the state and the symbol it reads on top, and on the bottom what the machine writes, with the new state moved one cell along. Copying the configuration on the top therefore forces the bottom to write the next configuration. The bottom stays exactly one configuration ahead, and the top can never catch up as long as the machine is running.

When the machine reaches its halting state H, a last group of dominoes comes into play. They let the H on top absorb a neighbouring cell while the bottom writes only H, so each new configuration on the bottom is one cell shorter; when only H is left, a final domino with H## on top and # underneath closes the gap. The match exists because the machine halted, and it has the whole run written into it. If the machine never halts, the bottom is always one configuration ahead and no match exists.

In the figure, the machine has three states, each writing a 1 and moving right, and the third halting. Its twelve dominoes have a shortest match of thirty-one, and cutting its top row at each # gives back the four configurations of the run, and then the four rows in which the tape is eaten. The figures check that the configurations read from the match are exactly the ones a direct simulation of the machine produces.

The match is the run #

The translation is literal enough that a machine’s run can be read off its match, and the figure for the three-state busy beaver shows it.

Tibor Radó’s busy beaver game, as he posed it in 1962, asked which machine of a given size leaves the most 1s on a blank tape before halting; the machines that need a reason never to stop followed the companion question, which machine runs longest. Among three-state machines the most 1s is six, and the machine drawn here is the one that leaves them, halting after 14 steps — the longest-running three-state machine takes 21 and would give a longer match still. Its seventeen dominoes have a shortest match of 121, and the top row of that match is its whole run: fifteen configurations, the head sweeping right across the tape, back left, and right again. The bottom row of the match is the same run, shifted one configuration ahead.

That is where the diagonal argument has gone. Nothing in the dominoes refers to itself, and nothing in the puzzle asks about a program. But the puzzle can contain a program’s run, and the undecidability of the halting problem — which was proved by a diagonal argument about machines reading their own descriptions — is carried across by the translation. The translation is mechanical and always stops: given any machine, it writes down the dominoes. So an algorithm for dominoes would give an algorithm for halting, and there is none.

Two technical points are hidden in the figures. The dominoes above are meant to be used with the start domino first, which is a slightly different puzzle; a standard trick, inserting a marker between every pair of characters so that only the start domino can begin a match, turns it into Post’s original puzzle without changing which sets match. And the tape here is given its length in advance — enough room for the run — where the full translation adds dominoes that extend the tape on demand. Neither changes the argument.

Length grows with running time #

Because a match writes out the whole run, a machine that runs longer produces dominoes whose shortest match is longer. The machines that write $k$ 1s run $k$ steps, and their matches grow from 10 dominoes to 136 as $k$ goes from 1 to 8, faster than linearly because each configuration grows with the tape. The two-state busy beaver runs six steps and needs a match of 43; the three-state machine that leaves the most 1s runs fourteen and needs 121. In every case the shortest match is at least as long as the run — one configuration per step, each at least a few dominoes.

This is the precise sense in which no formula bounds the length of a shortest match. Suppose there were a computable function that, given a set of dominoes, bounded the length of its shortest match when one exists. Applied to the dominoes built from a machine, it would bound the machine’s running time, if it halts, by a computable function of the machine’s size. But the busy beaver function — the longest running time among halting machines of each size — grows faster than every computable function. So shortest matches for sets of $n$ dominoes, at their longest, must also outgrow every computable function of $n$. The thirty-six of the three small dominoes is a very early glimpse of a function that soon becomes larger than anything that can be written down.

Where the dominoes reach #

Post’s problem matters less for itself than as a carrier. Once it is known to be undecidable, any other problem into which it can be translated is undecidable too, and its structure — two strings built up in parallel, one consistent with the other — appears in places where no program is in sight.

A context-free grammar generates strings by rewriting rules, as a programming language’s syntax does. Whether a given grammar is ambiguous — whether some string can be generated in two different ways — is undecidable, because two grammars can be built from a set of dominoes, one generating the top rows and one the bottom rows, and an ambiguity in their combination is a match. Whether two context-free languages share a string is undecidable by the same construction.

In 1970 Michael Paterson showed that whether some product of a given finite set of 3-by-3 integer matrices equals the zero matrix is undecidable, by encoding strings as matrices so that multiplying matrices concatenates strings, and a zero product appears exactly when a match does. A question of linear algebra, about multiplying a few small matrices together in some order, inherits the halting problem through dominoes. Equations over the whole numbers inherit it through a different and much longer translation, and the word problem for groups through yet another; Post’s puzzle is the shortest bridge in that family.

The closest relative is a puzzle about tiles. Tiles that never repeat described Hao Wang’s square tiles with coloured edges, which must be placed so that touching edges agree, and the theorem that no algorithm decides whether a set of them tiles the whole plane. The two puzzles are built on the same idea. A row of dominoes forces each configuration to be followed by the next one along a line; a tiling forces each row of tiles to be followed by the next one above it, so that a tiling of the plane is a computation that never ends, written out row by row. Post’s dominoes ask whether a computation stops, and Wang’s tiles ask whether one can go on for ever, and both questions inherit the halting problem the same way: by making the only way to complete the puzzle be to run the machine.

Three dominoes against five #

The undecidability theorem is about sets of any size, and the size at which it begins is a natural question. For a set of one domino the answer is trivial: a single domino matches with copies of itself only if its top and bottom are the same string. For two dominoes, Andrzej Ehrenfeucht, Juhani Karhumäki and Grzegorz Rozenberg proved in 1982 that the problem is decidable — there is an algorithm, and a long and intricate one, that settles every pair. The search-tree argument cannot explain that; the proof analyses the structure of the strings themselves.

From above, the bound has come down over decades. The problem was shown undecidable for sets of seven dominoes by Yuri Matiyasevich and Géraud Sénizergues in 2005, by translating very small universal machines rather than general ones, and for sets of five by Turlough Neary in 2015. For three and four dominoes nobody knows. The dominoes in the second figure are three of the kind no theorem covers: whether every set of three dominoes can be settled by some algorithm is open.

What the figures establish and what they do not #

The figures compute shortest matches by breadth-first search on the overhang, and each figure checks that its search could not have missed a shorter match: a match shorter than the one found would have had a smaller overhang than the search allows. For the machines, they check that the match’s top row is exactly the machine’s simulated run, configuration by configuration. These are facts about the particular dominoes drawn.

They do not prove Post’s theorem; they illustrate the translation at its heart, on machines small enough that the translation’s output can be drawn. The theorem is the argument that the translation works for every machine — that a match can never come from anything but a halting run, which depends on a careful choice of dominoes so that no cheating alignment exists — and that argument is a proof, not a computation. The claim that small sets of dominoes have long shortest matches is supported by the one drawn and by published searches, and the statement that no computable formula bounds them is the theorem’s consequence, not something the figures could measure.

Still open: three dominoes and four #

Whether Post’s correspondence problem is decidable for sets of three dominoes, or of four, is open. Two are decidable, by the 1982 proof; five are not, by Neary’s 2015 construction. The gap is not for lack of searching. Programs that hunt for shortest matches among small sets have mapped the sets of three dominoes with short strings and found most of them settled — by a match, or by a simple reason why none can exist — and a residue that resists both, like the machines that resisted every simple reason among three-state Turing machines. Whether that residue is a sign of undecidability at three, or only of the limits of the methods tried, is not known.

The two possible answers point in different directions. If three dominoes are undecidable, then a universal computer can be built from three pairs of strings, which would be a striking compression of the constructions that currently need five. If they are decidable, there is an algorithm, presumably of a structure like the one for two, that understands every set of three — and the shortest matches of three-domino sets are then bounded by some computable function, however large. The thirty-six in the figure is consistent with either.