Section 1
Run, then rewind
Apply a reversible rule to a configuration. Apply the inverse rule to the result. The original configuration returns — exactly, without ambiguity. Repeat in any order, for any number of steps. The tape has no preferred direction of time.
This is the strict condition: the global update map φ on the space {0,1}N of cyclic length-N configurations must be a bijection. Surjectivity is not enough. Every configuration must have exactly one predecessor, not merely at least one. Any many-to-one mapping destroys the rewind: which predecessor do you return to?
For elementary CAs — radius-1 rules on a binary alphabet — this condition is brutally restrictive. Of 256 rules, six pass. Under the standard equivalence (reflection, complement, and both combined), those six belong to exactly four inequivalence classes. The remaining 250 rules are irreversible at some finite tape length.
Section 2
The four classes
Each of the four classes represents a different elementary computation. All four are Wolfram Class II — uniform or periodic behaviour. All four have an explicit inverse that is itself an elementary CA rule.
Identity. Every cell copies itself. The configuration never changes. Trivially reversible: the inverse is itself.
Inverse: Rule 204 (itself)NOT-centre. Every cell flips. Apply twice and the original returns — an order-2 involution. The inverse is itself.
Inverse: Rule 51 (itself)Shift left. Each cell takes its right neighbour's value. The whole pattern translates one step left per generation. Inverse is a shift in the opposite direction.
Inverse: Rule 240 (shift right)NOT-left. Each cell takes the negation of its left neighbour. The pattern shifts right and flips simultaneously. Inverse undoes both the shift and the flip.
Inverse: Rule 85 (NOT-right)The full list of reversible elementary rules is {15, 51, 85, 170, 204, 240}. Rules 85 and 240 are reflections of Rules 15 and 170 respectively, so the six rules collapse to four inequivalence classes. Every reversible ECA is some composition of shift, NOT, and identity — the trivial operations. Hedlund (1969) characterised all bijective endomorphisms of the full shift; in the radius-1 binary case this list is complete.
Section 3
Run-and-rewind
Pick a reversible rule. Play it forward, then backward. The backward direction applies the inverse rule to reconstruct exact prior states — not an approximation, not a guess. Generation counts go negative as the tape rewinds past its starting point.
The green outline marks the current generation. Forward motion appends new rows at the bottom; backward motion prepends reconstructed rows at the top using the inverse rule. Both directions are exact.
Section 4
Why non-reversible rules can't be rewound
Rule 110 — universal, complex, and decidedly non-reversible — maps multiple distinct configurations to the same successor. Rewind is ambiguous: on a tape of length 8 (cyclic), there exists a successor with ten distinct predecessors. Which do you return to?
The configurations below all produce the same successor under Rule 110 on a tape of length 8. The first row (S) is the shared successor. Every row labelled Cn is a distinct predecessor that maps directly to S. Rewinding a non-reversible rule means picking one predecessor arbitrarily — there is no fact of the matter about which one you "came from."
Predecessors (up to 6 shown):
Computed by brute-force over all 28 = 256 configurations of length 8 under Rule 110. The successor shown has the largest predecessor set found. Picking any Cn as "the" rewind would be arbitrary.
Section 5
Making any rule reversible: the XOR construction
Add memory and any rule becomes reversible.read in layers
Start here Keep the previous step. Mix the rule's output with what was there before using XOR. The mix is self-inverse — undo it the same way. Every rule becomes reversible under this construction.
High school A normal CA computes x(t+1) from x(t) alone. A second-order CA also remembers x(t−1). The update is x(t+1) = f(x(t)) XOR x(t−1). To reverse: x(t−1) = f(x(t)) XOR x(t+1). XOR undoes itself. The history encodes exactly enough to run backwards.
Undergrad The construction x(t+1) = f(x(t)) XOR x(t−1) defines a CA on pairs (xt, xt−1). The state space is 22N for a tape of length N. The map (xt, xt−1) ↦ (xt+1, xt) is always bijective — the pair encodes its own inverse — regardless of whether f itself is bijective. This works even when f is many-to-one, because the extra bit of state resolves the ambiguity.
Backward: x(t−1) = f(x(t)) ⊕ x(t+1)
Going deeper Wolfram (NKS, pp. 437–441) explores second-order CAs systematically and notes that Rules 30, 110, and others become reversible under this construction. Margolus (1984) and Toffoli (1977) developed independent routes to reversibility: block (partitioned) CAs, where the update divides the tape into non-overlapping blocks applied in alternation, are natively reversible when each block transition is a bijection. Fredkin and Toffoli's billiard-ball model (1982) extends this to a physical interpretation of reversible computation. The XOR construction trades "1D radius-1" for "1D radius-1 second-order" — a small increase in expressive power that buys universal reversibility. Going to radius 2 or higher dimensions opens a much richer landscape of genuinely reversible and computationally universal CAs.
Section 6
What this rules out, and what it doesn't
✓ Irreversibility is the norm
In the elementary radius-1 setting, 250 of 256 rules are irreversible at some finite tape length. Information loss is not a pathological case — it is the default. Most dynamics compress state space on every step, permanently erasing the past.
✓ Reversibility here is trivial
The four reversible classes are identity, shift, NOT-centre, and NOT-left. Every one is a composition of the most elementary operations possible. None generates complex dynamics. Reversibility in the elementary setting is exactly as simple as it looks.
✓ Richer structure requires more
Moving to radius-2 rules, second-order CAs, or block CAs opens up reversible rules with genuine computational interest. Wolfram's second-order construction, Margolus block CAs, and Fredkin's billiard-ball model all give reversible dynamics that do something. The elementary setting is the easy end of the spectrum.
✗ Irreversibility is not a flaw
Most physical computations of interest are irreversible. The thermodynamic cost of erasing a bit (Landauer's principle) connects information-theoretic irreversibility to heat dissipation. Irreversible CAs like Rule 30 and Rule 110 are interesting precisely because they model dissipative processes and exhibit rich complexity. Reversibility is a constraint, not a virtue.
→ Physics and reversible computation
Reversibility sits at the intersection of CAs and physics. Margolus, Toffoli, and Fredkin used reversible CAs to model reversible computation and explore whether the universe's physical laws could be simulated by a reversible cellular automaton. The question is not whether elementary CAs are reversible — most aren't — but whether reversible CAs at some scale can reproduce physical dynamics.
Section 7
Next: Rule 30 as a random number generator
Rule 30 is irreversible, and spectacularly so — it folds state space aggressively at every step. Wolfram used its centre column as a pseudorandom number generator in Mathematica for years. Whether that column is genuinely unpredictable is an open problem. The audit is next: Rule 30 as a random number generator.