The Order of Three Things
Here is a construction I have been living inside for three days.
Take a line of cells, each one a 0 or a 1, and update them all at once by a rule that looks at each cell and its two neighbours. There are 256 such rules. Most of them are boring. A few are not, and one of them, rule 110, is a universal computer: with the right starting pattern it can run any program you like, given enough tape and enough patience. Stephen Wolfram conjectured that in 1985 and Matthew Cook proved it, in Complex Systems volume 15, in 2004.
Rule 110 is lopsided. Its patterns lean. Gliders drift across a patterned background at fixed speeds, different ones at different speeds, and if you hold the picture up to a mirror you get a different rule, number 124, which is not the same rule at all. The lopsidedness is not decoration; it is where the computing happens. Collisions between things moving at different speeds are how one glider pattern turns into another, and without a direction there are no different speeds.
In October a physicist in Copenhagen, Riz Fernando Noronha, published something small and strange about this. Take three rules — 36, 37 and 5 — and apply them not uniformly but in a repeating cycle: rule 36 at every third cell, 37 at the next, 5 at the next, over and over. All three are mirror-symmetric: hold any one of them up to a mirror and you get itself back. None of them can tell left from right. None of them does anything interesting on its own; two of them freeze every pattern you give them within a step or two.
Three steps of that mixture are exactly one step of rule 110.
So the handedness is not in the parts. It is in the order you put them in. I checked this as carefully as I know how, over sixteen million possible triples of rules, and the claim holds in a stronger form than the paper states: exactly forty-two triples work, and exactly two of them are built entirely from mirror-symmetric rules. The construction is not one option among many. It is the only symmetric option there is.
That is the part everyone would tell you is the interesting part. I want to tell you about something further down.
If you start one of these rings from pure noise — every cell a coin flip — it usually sorts itself out. Regions of the ring fall into step and start computing, and the boundaries between regions that are out of step with each other move and collide and eat each other until, nine times in ten, the whole ring is marching together. A few times in a hundred it doesn’t. The ring gets stuck, and stays stuck, apparently forever.
What is left when it gets stuck is always three boundaries. Never two, never four, never five. I ran this on rings of 128, 256, 512 and 1024 units and every single stuck ring ended with three or six.
Three, because of arithmetic. A region can be in step, one beat ahead, or two beats ahead — three choices — and a boundary is where that number jumps. A jump is either +1 or +2, and going all the way around the ring you have to come back to where you started, so the jumps have to add up to a multiple of three. If every boundary on the ring is the same kind, say every one a +1, then there have to be three of them, or six, or nine. Two of the same kind is not rare. It is impossible.
And it has to be the same kind, because of a measurement. A +1 boundary travels at 0.2414 units per step, leftward. A +2 boundary travels at 0.1932, rightward. I measured thirty-eight of them in isolation and the two groups do not overlap — not at the edges, not once. A boundary’s speed is written on its face. So two boundaries of opposite kind are always closing on each other and will always meet, and when they meet they cancel. Two of the same kind are moving at the same speed and will never meet at all.
That gave me a clean story and the clean story was wrong, which is how these things go. The arithmetic says a stuck ring is three boundaries all of the same kind, and there are two ways to be all the same kind: three +1s, or three +2s. I assumed those were the same situation looked at from two sides. They are not.
I built a hundred and sixty rings by hand — three regions each, laid out so I knew in advance what boundaries I would get — and let them run for a hundred and fifty thousand steps.
Eighty of them organised themselves before the clock started and are not part of the count. Of what was left, the rings with three +1 boundaries came apart — fifty-one out of fifty-one. The gaps between the boundaries wandered, slowly, the way a drunk wanders, and sooner or later two of them touched. Median time to come apart: fifty-five thousand steps.
Of the rings with three +2 boundaries, twenty-six out of twenty-six did not. Not one. The gaps wandered too, but they wandered inside a fence — mostly staying sixty to a hundred units apart, dipping to twenty once or twice, and never closing.
The two kinds of ring contain exactly the same three regions. One region in step, one a beat ahead, one two beats ahead, each about a hundred units wide. The only difference between them is the order you meet those regions in as you walk around the circle: in-step, then one-ahead, then two-ahead — or in-step, then two-ahead, then one-ahead. Those two orders are reflections of each other. Nothing else differs. One of them is a structure that dissolves. The other is a structure that appears to be permanent.
I find I want to say this slowly, because it took me most of a day to believe it.
The three rules this thing is made of cannot tell left from right. Not one of them. Every one is its own mirror image, and the paper says so, and I verified it, and it is the whole point of the paper. And yet the defects this system makes — the scars, the places where it failed to organise — come in left-handed and right-handed versions, and the handedness decides whether the scar heals.
It is the paper’s own thesis turning up somewhere the paper never looks. If you only had the parts, you could not predict this. If you only had the parts you could not predict rule 110 either. The arrangement is not a container that the rules sit inside. The arrangement is doing the work, and it keeps doing the work all the way down, past the computation, into the texture of the failures.
I will say the obvious thing once and then stop. There is a version of this observation about people, and about bands, and about which three notes you play in which order, and anyone who has stood in a room while a group of people came into step or failed to knows it already. I don’t think the cellular automaton proves anything about rooms. I think it is a very clean instance of something that is usually too tangled to see: that order is not a label attached to a set of parts. Order is most of the content. Give me the same three things in the other sequence and I have a different object, and sometimes one of them lives forever and the other one comes apart by lunchtime.
A note on being wrong, since I would rather put it here than bury it. Before I ran any of this I wrote down what I expected, in a file, and committed it, so that I could not later discover that I had expected whatever happened. Five of my eleven predictions were wrong. One of them — my guess that a stuck ring would have two boundaries left — was forbidden by an argument I had written down four paragraphs earlier in the same document. I had the premise. I set it on the table, and then I reasoned straight past it and wrote down a number the premise rules out.
That is not a thing I can fix by resolving to be more careful. The only reason I know about it is that the prediction was written down where it could be checked against the thing that actually happened. Which is the argument for writing them down.
