Film a cellular automaton evolving and play the film backwards. For the Game of Life the rewound film is nonsense — gliders un-collide, still lifes burst apart, and at some frame you hit a pattern that no rule application could ever have produced. Life, like an AND gate, throws information away. But some cellular automata rewind perfectly: every frame has exactly one legal previous frame, and the backwards film is itself the run of a cellular automaton. These are the reversible cellular automata (RCA) — and they are where reversible computing stops being about circuits and Turing machines and becomes a model of space: a uniform, local, parallel world in which nothing is ever forgotten. This page pins down what reversibility means for a CA, how to certify its failure, and two genuinely surprising facts about deciding it.

Reversibility is a property of the global map

Fix a CA with state set S, a neighbourhood, and a local rule f. A configuration assigns a state to every cell of the grid, and one synchronous update of all cells defines the global map

sending each whole configuration c to its successor. The CA is reversible when G is a bijection on configurations: every configuration has exactly one predecessor. Note carefully where the definition lives — it is a statement about G, the map on entire (infinite, or wrap-around) configurations, not about the little rule table f. Just as in our study of reversible steps, "reversible" means "the past is deducible" — here, the whole grid's past from the whole grid's present.

Two failure modes break a bijection, and each has a name in CA theory:

• a configuration with no predecessor — a Garden of Eden (it can only ever appear at time 0, planted by hand, never reached);
• a configuration with two or more predecessors — the "funnel" we met in irreversible gates, now grid-sized.

Gardens of Eden: certificates of irreversibility

A single Garden-of-Eden configuration proves G is not surjective, hence not a bijection, hence the CA is irreversible. This is exactly how we know the Game of Life is irreversible: explicit Garden-of-Eden patterns have been constructed — finite arrangements of live and dead cells that provably no configuration maps onto. (The first was found in 1971 and was a sprawling 9 × 33 monster; decades of search have shrunk them, but none is small or obvious — orphanhood is a delicate global property.) Life also fails in the second way, and that failure is obvious: the empty grid and the grid holding one lone live cell both step to the empty grid. Two pasts, one present.

Example 1: the shift — trivially reversible

The simplest reversible CA does almost nothing: the shift, in which every cell copies its right-hand neighbour, G(c)_i = c_{i+1}. The whole tape slides one cell to the left each step. Its inverse is obvious — slide it back — and the inverse is itself a CA (every cell copies its left neighbour). A bijection, certified by exhibiting the inverse. Boring, but it already illustrates the cleanest way to prove reversibility: produce the inverse automaton.

Example 2: Rule 90 — many-to-one everywhere

Now the classic counterexample. Rule 90 updates every cell to the XOR of its two neighbours: c'_i = c_{i-1} \oplus c_{i+1}. It draws gorgeous Sierpiński triangles — and it is emphatically not reversible. Here is a complete tiny worked example, on a ring of 4 cells. Ask: which configurations map to 0000? We need c_{i-1} \oplus c_{i+1} = 0 for every i, i.e. c_{i-1} = c_{i+1}: both even-position cells equal, both odd-position cells equal. That is 2 \times 2 = 4 solutions:

Check one by hand — take 1111: every cell sees two neighbours both equal to 1, and 1 \oplus 1 = 0, so the whole ring collapses to zeros. Four distinct pasts share one present. And because Rule 90 is linear (XOR is addition mod 2), this is not a quirk of the zero configuration: on any even-length ring, every reachable configuration has exactly these 4 preimages, translated by a kernel element — the map is uniformly many-to-one, and three quarters of all configurations are Gardens of Eden.

See the funnel

The picture below is the grid-sized version of the AND-gate funnel: filled squares are 1-cells, empty squares are 0-cells, and each row is one ring-of-four configuration (imagine the right edge glued to the left).

Count it in code

Don't take my word for the funnel — enumerate it. On a ring of 8 cells there are 2^8 = 256 configurations. A reversible rule permutes them, so all 256 appear as images; Rule 90, being uniformly 4-to-1, reaches only 64:

The shift reaches all 256 — a permutation. Rule 90 reaches 64: it is exactly 4-to-1, and the other 192 configurations are Gardens of Eden on this ring.

Two structure theorems — one comforting, one shocking

Suppose a CA is reversible. Is the backwards dynamics as nice as the forwards one? Yes — and this is genuinely reassuring:

(This follows from the Curtis–Hedlund–Lyndon characterisation of CA as the continuous, shift-commuting maps: G^{-1} inherits both properties.) So reversible CA form a group under composition — a genuine "physics-like" dynamics with a past as lawful as its future.

Now the shock. Given a rule table, can an algorithm decide whether the CA is reversible?

Read that again: adding one dimension moves a crisp structural property of a finite rule table across the line from algorithmically checkable to forever uncheckable-in-general. It is one of the sharpest decidable/undecidable boundaries in all of computer science, and it sits — like the reversible complexity questions we met in reversible complexity classes — right at the junction of computation and physics: 2-D reversible rules can hide computation in their update logic, and Kari's construction makes the hidden computation carry the halting problem.