A rule that remembers one row back

An elementary cellular automaton computes each new row from the row above it: every cell looks at itself and its two neighbours and applies a fixed table. Eight rules and a triangle counted which of the 256 possible tables can be undone — which rules send different rows to different rows, so that the previous row can always be recovered — and found six. They are the rules that copy each cell, shift the whole row one place left or right, or do one of those and flip every cell. Every other rule, and in particular every rule that does anything interesting, sends some pairs of different rows to the same row, and information about the past is lost for good.

That seems to settle the matter: complexity and reversibility do not mix in elementary automata. Edward Fredkin found a way round it in the 1970s that works for every rule at once.

The trick is to let the new row depend on two rows, not one. Compute what the rule would produce from the current row, and then combine that, cell by cell, with the row before the current one, using exclusive or: the result is $1$ where exactly one of the two is $1$. In symbols, with $f$ the rule and $\oplus$ exclusive or,

$$x_{t+1} = f(x_t) \oplus x_{t-1}.$$

The figure runs rule 30 this way for sixty steps from a small seed: the pattern spreads into the familiar disordered triangle. Then it swaps the last two rows and runs the same rule forward again. After sixty more steps it arrives at the exact starting row, every cell correct.

Why it runs backwards #

The reason is one line of algebra, and it holds whatever the rule $f$ is.

Exclusive or undoes itself: $a \oplus b \oplus b = a$. So from $x_{t+1} = f(x_t) \oplus x_{t-1}$ it follows that

$$x_{t-1} = f(x_t) \oplus x_{t+1}.$$

That is the same rule with the roles of past and future exchanged. Given any two consecutive rows, the rule produces the next one; given the same two rows in the opposite order, the same rule produces the previous one. The rule $f$ need not be reversible at all — rule 30 certainly is not — because the construction never tries to undo $f$. It only uses $f$ to scramble the previous row, and scrambling by exclusive or with a known pattern is undone by doing it again.

The state of the second-order system is therefore not a row but a pair of consecutive rows, and the map from $(x_{t-1}, x_t)$ to $(x_t, x_{t+1})$ is a bijection on pairs. The first-order rule 30 in the figure above sends different rows to the same row; the second-order rule built from it never sends different pairs to the same pair.

Every rule, the same way #

Nothing in the construction used anything particular to rule 30.

Rule 90, which takes the exclusive or of each cell’s two neighbours and drew the Sierpiński triangle of eight rules and a triangle, becomes reversible in the same way, and so does every one of the 256 elementary rules. The second-order patterns differ from the first-order ones, since the extra row feeds its own structure into every step, but each can be run backwards exactly. Fredkin’s construction turns every rule into a reversible one, at the cost of remembering one extra row.

Two rows are a position and a velocity #

Keeping two rows instead of one has a familiar counterpart in physics. Newton’s laws are second order in time: the state of a system is not its positions alone but its positions and velocities, or equivalently its positions at two nearby moments. Given both, the future is determined, and so is the past; reverse the velocities and the motion runs backwards. That is why Newtonian mechanics is reversible while many first-order processes, like the spread of heat, are not.

Fredkin’s construction gives an automaton the same structure. The pair $(x_{t-1}, x_t)$ plays the part of position and velocity, and swapping the two rows is reversing every velocity at once. The second-order rule is, in this sense, a discrete mechanics: its “law of motion” is the rule $f$, and exclusive or plays the part of the subtraction in a discrete wave equation, where the next value is a function of the present minus the previous. Reversibility comes from the order of the equation, not from any special property of the law.

The wave equation is the standard example. A plucked string keeps its corners followed a string whose shape at each moment is determined by its shape at the two previous moments, and whose motion can be run backwards by the same rule; a kink in the string travels without smoothing, where the heat equation would round it off irreversibly. The second-order automaton is the same kind of object in a world of bits: a disturbance in it travels and scatters, but it is never smoothed away, and the swapped rows bring every kink back.

Counting what a rule forgets #

The difference between the two kinds of rule can be measured by counting how many different rows are still possible after a few steps.

On a ring of ten cells there are $1{,}024$ possible rows. Start from all of them at once and apply a first-order rule: some rows land on the same next row, and the number of distinct rows drops. Apply it again and it drops further; it can never rise, since a rule sends each row to a single row. Rule 90 collapses to $256$ distinct rows in a single step. Rule 110 falls to $131$; rule 30 falls more slowly, to $443$ after twelve steps. Each loss is information about the starting row destroyed for good.

The second-order versions lose nothing. Since the map on pairs is a bijection, all $1{,}048{,}576$ pairs of rows remain distinct forever, and every row still appears as a current row after any number of steps. The flat line in the figure is not an approximation or a sample; the figure checks on thousands of pairs that different pairs go to different pairs.

Disorder rises, and falls again #

Reversibility raises an old puzzle in a clean form.

Started from a small seed, the second-order rule 30 spreads outward and the number of live cells climbs, with the irregular fluctuations of a gas released from one corner of a box. It looks exactly like the growth of disorder that physics calls the second law of thermodynamics. Then the rows are swapped and the rule run again, and the count retraces its climb, fluctuation for fluctuation, back down to the seed.

Johann Loschmidt raised this objection against Ludwig Boltzmann in 1876: if the laws of motion of molecules can be run backwards, as Newton’s can, how can disorder always increase? Reverse every velocity and the gas would un-spread. The second-order automaton is a model in which that reversal can actually be performed, and it behaves exactly as Loschmidt said. Nothing in the rule prefers one direction of time. The apparent arrow comes entirely from the starting state: a seed is a very special configuration, and almost every configuration the rule passes through is disordered, so starting from order and running either way leads to disorder. Running backwards from a disordered state that came from a seed is possible only because the state was prepared with perfect knowledge of every cell.

Running backwards needs every cell #

The reversal in the figures works because every cell of the swapped rows is exactly right. Change one cell — flip a single bit in the last row before running backwards — and the run does not return to the seed. The error spreads outward at one cell per step in both directions, since every cell’s next value depends on its neighbours, and by the time the backward run should be reassembling the seed it has contaminated a wide region.

That is the practical content of Loschmidt’s paradox and its answer. A reversible law can be run backwards only with perfect knowledge of the present; any error, however small, grows as the run proceeds, exactly as the tiny differences of a difference too small to draw grew under a chaotic map. In a gas of real molecules, knowledge of every velocity to the necessary precision is impossible, and the reversal that the automaton performs flawlessly cannot be performed. The arrow of time survives as a statement about what can be known, not about what the laws allow.

Why reversibility matters for computing #

The construction is not only a curiosity. In 1961 Rolf Landauer argued that erasing a bit of information has an unavoidable cost in energy — at least $kT \ln 2$ per bit, where $T$ is the temperature — because erasure reduces the number of possible states, and that reduction must be paid for by increasing the disorder somewhere else. A first-order rule that merges rows is erasing information at every step, as the census shows. A reversible rule erases nothing.

Charles Bennett showed in 1973 that any computation can be done reversibly, keeping a record from which every step can be undone, so that in principle computation need not dissipate energy at all. Fredkin and Tommaso Toffoli built the idea into a model of computation made of billiard balls colliding elastically, and Norman Margolus turned that into a reversible cellular automaton that can simulate any computer. The rule that computes showed that the first-order rule 110 is computationally universal; reversible automata can be universal too, and in them nothing is ever forgotten.

The idea has a sharper modern form. A quantum computer’s operations must be reversible, because the laws of quantum mechanics are: every step is a rotation of the state, which can be undone by rotating back. So quantum algorithms are built from reversible gates, and ordinary computations that erase information have to be recast in a reversible form before a quantum computer can run them — Bennett’s construction, keeping the history and then uncomputing it, is exactly the tool used.

The price is memory, and it is paid in full. The second-order rule carries two rows where the first-order rule carried one, and a reversible computer must keep, in some form, the history it would otherwise have thrown away — or spend steps undoing its own work before it can reuse the space.

The other way to be reversible #

Fredkin’s construction is one route to reversibility; there is another that keeps a single row. Divide the row into blocks of two cells, and apply to each block a permutation of its four possible states. A permutation can be undone, so the step is reversible. Then shift the block boundaries by one cell and do it again. Alternating the two partitions lets information travel along the row, and the whole process is reversible because each step is.

These block or partitioned automata, developed by Norman Margolus and Tommaso Toffoli in the 1980s, include the billiard-ball automaton that can simulate any computation. They are not elementary automata in the strict sense, since their neighbourhoods alternate, but they show that the six trivial reversible elementary rules are an artefact of the three-cell neighbourhood rather than a law: with a different way of dividing the row, reversible rules are as rich as any.

Conservation is not reversibility #

It is worth separating reversibility from a property that looks similar. A road where nobody overtakes studied rule 184, which conserves the number of cars: no row has more or fewer ones than the row before. Conservation is a kind of bookkeeping that nothing is lost — but rule 184 is not reversible. A jam and a slightly different jam with the same number of cars can lead to the same next row, and the census’s rule 184 curve falls just like the others.

Conservation says one number is preserved; reversibility says every piece of information is. The second-order construction gives the stronger property, and in exchange it gives up the simple conserved quantity: the number of live cells in the second-order runs rises and falls freely, as the live-cell count above shows. The traffic rules of a jam that comes from nowhere are neither: they conserve cars but add randomness, which destroys information on purpose.

Forgetting and the Garden of Eden #

The census connects to a theorem from the same essay that found the six reversible rules. A Garden of Eden is a row that no row can produce — a state with no past. Eight rules and a triangle stated the Moore–Myhill theorem: a rule has a Garden of Eden exactly when two different finite rows can lead to the same result.

In the census, a first-order rule’s count of distinct rows falls on the very first step exactly because it merges rows, and so by Moore and Myhill it has rows with no past. The second-order construction removes both defects at once: nothing merges, and every pair of rows has a unique predecessor pair. Remembering one row back abolishes the Garden of Eden, because the extra row supplies exactly the information that merging would have destroyed.

What the figures can and cannot show #

The reversal is checked cell by cell. Each figure runs the rule forwards and backwards and requires every cell of the final row to equal the starting row, and the census checks on thousands of pairs of rows that the second-order map never merges two of them.

The seeds are small and the rings are finite. A ring wraps round, so a pattern that spreads far enough meets itself; the figures stop before that happens, and the reversal would still be exact after it, since wrapping round changes nothing in the algebra. What it would change is the look of the pattern, which would fill the ring with interference between the two fronts.

Only elementary rules and small rings. The census counts rows exactly on a ring of ten cells, where there are only $1{,}024$; for large rings the same argument holds but the count cannot be done by listing.

The arrow of time is modelled, not explained. The live-cell count rising and retracing shows that the rule has no preferred direction; why the universe began in a state of low disorder is a question about the universe, not about the rule.

Still open: what rule 30 does to one column #

The second-order construction makes rule 30 reversible; the first-order rule 30, the one that forgets, still hides simple questions nobody can answer. Stephen Wolfram, who catalogued the elementary rules in the 1980s and used rule 30’s centre column as a source of random bits, posed three of them publicly in 2019.

Start rule 30 from a single live cell and read down the centre column. Does that column ever become periodic? It has been checked for billions of steps and shows no period. Does it contain ones and zeros with equal long-run frequency? It appears to. Can the $n$-th cell of the column be computed with less work than running the rule for $n$ steps? Nobody knows a shortcut and nobody can prove there is none. For a rule defined by an eight-entry table, applied to a single cell, all three are open.

Keeping the past in the present #

The habit worth keeping is to ask where information goes.

A rule that computes each row from the one above it can lose information, and almost every interesting rule does; the census shows it disappearing step by step. Fredkin’s construction keeps one more row and combines it with the rule’s output in a way that can be undone, and the loss stops completely, whatever the rule. The disorder that remains is not destroyed information but information spread thin, and the swapped rows prove it is all still there, by bringing back the seed.