We now hold two beautiful objects in separate hands: a billiard-ball computer that computes anything but lives on an idealised frictionless table, and a family of block cellular automata whose reversibility is guaranteed by construction. In 1984 Norman Margolus snapped them together: a two-state block CA — the BBM (Billiard-Ball Model) cellular automaton — that simulates the billiard table exactly, collisions, mirrors and all, on a grid of bits. The consequence lands with a satisfying click: reversible cellular automata are computation-universal. A dynamics in which no information is ever lost, in which every configuration has exactly one past, can still run any program that any computer can run. Reversibility costs nothing in computational power — this page walks the chain of reductions that proves it, then pushes past it into one and higher dimensions.

The BBM cellular automaton

The BBM automaton is almost embarrassingly simple. Cells hold 0 or 1; the update is a Margolus block rule on alternating 2\times2 partitions; and the block map has just two active clauses:

• a block containing a single 1-cell moves that 1 to the diagonally opposite cell of the block;
• a block containing two 1s in diagonally opposite corners is left unchanged;
• every other block (empty, side-by-side pairs, three or four 1s) is also left unchanged.

Check bijectivity by eye: the rule swaps each lone-1 block with the lone-1 block in the opposite corner and fixes everything else — a permutation of the 16 block states, so the automaton is reversible, for free, exactly as the block-rule machinery promised.

Balls, collisions and mirrors, made of bits

Where did the billiard table go? Watch what the rule does over time:

• Balls. A lone 1-cell hops to the opposite corner of its current block; on the next step the shifted partition hands it a new block, in which it is again alone, and it hops the same way. The result is a particle gliding diagonally across the grid, one cell per step — a billiard ball, encoded as a single moving bit.
• Collisions. When two particles converge, they land in a shared block as a diagonal pair — which the rule freezes for one step. That pause, followed by the shifted partition splitting them into new blocks, sends them out along displaced diagonals: exactly the deflected trajectories of the interaction gate.
• Mirrors. A fixed clump of 1s (blocks with two-a-side, three or four 1s) never changes — and a particle bouncing into its neighbourhood is turned around. Immovable patterns of bits play the reflectors.

The chain of universality

Now assemble the reductions, each one already proved somewhere in this course:

• the BBM automaton simulates the billiard-ball model: particles fly and collide like balls, fixed patterns act as mirrors (Margolus, 1984);
• billiard balls implement the interaction gate, and with mirrors, the Fredkin gate (Fredkin–Toffoli, 1982 — last page);
• the Fredkin gate is universal for Boolean logic: with constant inputs and garbage outputs it builds AND, OR, NOT, fan-out — hence any circuit, hence (unrolling in time) any Turing-computable function.

Therefore: set up the right initial configuration of bits — particles as data, clumps as circuitry — and the BBM automaton computes whatever you like, while remaining a bijection on configurations at every tick. There exist computation-universal reversible cellular automata. It is worth pausing on how strange that nearly sounds: Life is universal and irreversible, and one might have guessed that the freedom to forget is part of what computing power is made of. It is not. The BBM automaton matches Life's universality without ever discarding a bit.

Deeper cuts: one dimension, and one dimension up

Two refinements sharpen the picture. First, universality does not need two dimensions: universal reversible CA exist even in 1-D. The route is different — instead of billiard geometry, one simulates a reversible Turing machine (Morita and collaborators showed reversible 1-D CA can host them), and since reversible Turing machines compute everything Turing machines do — the Lecerf–Bennett result from earlier in this course — universality follows. Remember the delicious contrast with the previous page's decidability theorem: in 1-D reversibility is decidable, yet the reversible 1-D world is still rich enough to compute everything.

Second, a structural theorem that converts any CA into a reversible one at the price of one dimension:

So the irreversible Game of Life sits inside some reversible 3-D automaton, its discarded pasts stacked neatly along the third axis. Universality of reversible CA also follows instantly from this theorem (embed any universal CA) — but the BBM construction remains the one to remember, because it is universality native to a reversible world, not borrowed through a history-keeping embedding.