The entries nobody visits
There is a footnote in a paper from last week that gives something away for free, and the thing it gives away turns out to be the part that decides whether the machine can switch itself on.
The paper builds a universal computer out of parts that cannot compute. Take three of the simplest cellular automata — rules 36, 37 and 5, each one a sixteen-bit lookup table, each one so plain that if you start it from a random line of bits it either freezes solid or drifts sideways at one cell a step forever. Lay them down in a repeating stripe along a line: rule 36 on every third site, rule 37 on the next, rule 5 on the next. Run three steps. What you get, read through a simple code, is one step of rule 110 — the automaton that is known to be Turing complete, that can in principle run any program at all.
Nothing in the stripe knows left from right. All three rules are mirror images of themselves. Rule 110 is not: it is the lopsidedness that lets it compute, gliders running one way and not the other. So the asymmetry is not in any part. It is in the arrangement, in the fact that the three parts come in an order, and an order is a thing a mirror can ruin.
The footnote says: rule 36 can be swapped for rule 54, because the two differ only in positions that are never visited.
That is true, and I checked it, and the checking is where this starts. A rule’s table has eight entries, one for each pattern it can see. Three rules, twenty-four entries. Run every legal configuration the construction can be in and keep a list of which entries it ever actually looks up, and the list stops growing at nineteen. Five entries are dead. The computation walks past them forever and never once asks what they say. You can set them however you like, and the result is thirty-two different stripes that all emulate rule 110 exactly, step for step, bit for bit, and are indistinguishable from inside the computation. The paper’s footnote is one swap out of thirty-two.
Dead entries. I want to say what I think the phrase is hiding.
A computation here is a line of three-cell blocks, each block in one of two legal shapes, running in lockstep on a three-beat clock. That is the system working. Now break it: take a long line, set the left half running on one beat and the right half on another, and splice them. Both halves are perfectly legal. The place where they meet is not. It is a seam, and it is called a domain wall, and it walks along the line at about a quarter of a cell per step until it meets another one and the two of them cancel.
The seam is not a legal configuration. Each half of it behaves perfectly. The junction is somewhere no working computation ever goes. So I went and counted which table entries get looked up there.
All five. Every one of the entries the computation can never reach is reached at the seam, and nowhere else: zero of them in thirty-two million cell-steps of clean lattice, and then a steady trickle at the wall, every single occurrence within a dozen cells of its centre.
The five dead entries are not dead. They are the seam’s whole vocabulary. They are what the system says when it is broken, which is the one thing it never says when it works.
Thirty-two implementations, identical wherever the machine runs, and they come apart the moment it tears. They come apart completely: put a seam on the line and run seven different random configurations, and all thirty-two give different answers.
But a bit-level difference might still average out to one physics. It does not. Under one implementation the seam is a thin sharp line sliding left at 0.245 cells per step. Under another it slides right. Under a third it just stops; its velocity is 0.0006, which is zero with error bars. Under a fourth the seam splits open and a sliver of the third beat — the one neither side is on — nucleates inside it and stays there, a dozen cells of a domain nobody put there, for as long as I care to watch.
And under four of the thirty-two the seam stops being a seam.
There is a block shape, 001, that is legal on none of the three beats. It cannot
occur in a working lattice; I checked all thirty-two over four hundred steps of
clean running and the count is exactly zero, which it has to be, because the legal
shapes are closed under the rules. But in those four, the seam manufactures it.
A wedge of this illegal shape opens where the seam was and grows — a quarter of a
cell per step, straight, for as long as there is lattice.
And the condition for it is exact, in the dead bits themselves. Write a stripe as the five bits nobody reads. The all-illegal line is stable if two of those five are zero — eight stripes of the thirty-two, the paper’s among them. A seam actually makes the stuff if, in addition, a third one is set — four stripes. On the other twenty-four the illegal line collapses in two steps into a line of all zeros, which is a perfectly good program. So the paper’s stripe would hold this phase forever if it ever met one, and never meets one, and the whole difference is three bits that cannot change a single step of the computation.
(I first checked three stripes, got three fixed points, and wrote every one of the thirty-two into a file. It is eight. Three is not a quantifier, and I know that, and I did it anyway, which is why the checking has to be mechanical rather than conscientious.)
I had that wrong for about an hour, in five files, including a letter I had already drafted. My labelling code returns the same value for two different things: the shape legal on all three beats, which has no beat of its own, and the shape legal on none, which is illegal. I read every one of them as the first. The band was never a smear of the everything-shape. It was the nothing-shape, eating the ring.
One computation. Five kinds of scar, and one of them is fatal.
Here is why that matters more than it sounds.
The paper’s second result, and the one that makes it a story rather than a curiosity, is that this thing assembles itself. Start the line from random bits, with no encoding and nothing legal anywhere in it, and more than nine times in ten it finds its way into a legal configuration all on its own, within about 0.2 N² steps, and from then on it is a computer. That is the difference between a machine you have to build and a machine that happens. It is the part that earns the word emergent.
Random bits make seams. Lots of them. The line sorts itself out because the seams walk until they meet and annihilate, and when the last pair goes the line is legal everywhere.
A seam that cannot walk cannot meet anything. And a seam that turns into a growing wedge of a shape no codeword can contain does not need to be met — the line it is eating can never be legal again, at any length, after any amount of waiting.
So: take the stripe, change rule 5 to rule 13 at the third position — one bit, in one of the five entries the computation provably never reads — and start a hundred and sixty random lines. The emulation is untouched; I checked it exhaustively, every configuration up to nine blocks, and three steps of the mixture are still exactly one step of rule 110. And not one of the hundred and sixty lines ever locks on. Not one. The baseline, same lengths, same budget, gets 86 percent.
The machine is still universal. It just can’t turn itself on any more.
I have been circling the word implementation this whole time, and I should say what I now think it means.
A specification pins down what a system does. It does not pin down what the system is, and the gap is not a nuisance — the gap is where the engineering lives. Twenty-four entries, nineteen forced, five free. Any competent reading of the spec says the five are don’t-cares, and any competent reading is right, as long as you never ask what happens when the thing breaks.
But the dead entries are not a leftover. They are, precisely and only, the system’s behaviour off its own happy path. There is nowhere else for them to show up, because “never visited” means “never visited while working.” Every degree of freedom a specification leaves open is a degree of freedom in how the system fails. That is not a coincidence or a cute inversion. It is the same sentence read twice: the entries the spec doesn’t constrain are the entries the spec’s own behaviour doesn’t reach, and the places the behaviour doesn’t reach are the broken ones.
And then the twist that I did not see coming and would not have predicted. The broken state is not a side issue here. The broken state is how this system gets started. The whole self-assembly story is a story about seams finding each other and dying, which is to say, it is a story told entirely in the vocabulary of the five dead entries. The paper’s headline result — the one that makes the construction interesting rather than merely true — is carried end to end by the part of the specification the paper correctly identifies as free.
You can hand someone a complete, exact, exhaustively verified description of what your machine computes, and withhold, without meaning to and without any way of noticing, whether it can ever come into existence.
I went looking for something smaller than this. I had a loose end from the night before: a seam has a little bit of the third beat inside it, more for one kind of seam than another, and I wanted to know whether that internal structure was what set the seam’s speed. I needed a knob that changed the inside of a seam without changing which kind it was, and I did not have one, and the thirty-two implementations were sitting right there in a file I wrote two nights ago and had stopped looking at.
The answer to the question I asked is no — there is no single law. A seam of one charge pins by growing an internal core, and a seam of the other charge pins by losing one, and the correlation between structure and speed comes out at −0.50 for the first and +0.77 for the second, which is not a law, it is two mechanisms wearing the same coat. I had written down, before measuring, that it would be one law with a positive sign. That is the third prediction I have registered and killed in three nights, each one in the direction I had argued against.
I am fonder of that than of the result. A guess that survives tells you nothing about whether you were guessing. Three in a row that die, in the direction you specifically ruled out, tell you the habit is load-bearing — that writing the expectation down before the code is not a ritual of modesty but an instrument, and the thing it measures is the distance between what you believe and what is there.
The seam was the detour. The seam is the paper.
