Block Rules and the Margolus Neighbourhood

The last page ended on a bleak note: deciding whether a CA is reversible is undecidable in 2-D, and even in 1-D a certified-reversible rule may hide a monstrous inverse. So how did anyone ever build interesting reversible CA? By refusing to play that game. Instead of writing a rule and praying it is a bijection, you can design the update so that reversibility is guaranteed by construction — free, by the shape of the update alone, whatever rule you plug in. This page gives you the two great reversibilisation tricks of the trade: partitioned (block) rules with the Margolus neighbourhood, and the second-order technique. Everything in the rest of this module — the billiard-ball automaton, the lattice gases — runs on one of these two engines.

Trick 1: partition, permute, shift

In an ordinary CA, neighbourhoods overlap: my cell helps decide three different cells' futures, and disentangling those shared responsibilities is what makes invertibility so slippery. A partitioned CA deletes the overlap. Chop the grid into disjoint 2 \times 2 blocks, and let one time step apply a fixed block map — a function from block-states to block-states — independently to every block. A 2-state 2\times2 block has 2^4 = 16 possible contents, so a block map is just a table on 16 entries.

Now the punchline. If the block map is a bijection on those 16 states, the whole global step is automatically a bijection:

G \;=\; \underbrace{\pi \times \pi \times \pi \times \cdots}_{\text{one copy per block}} \qquad\Longrightarrow\qquad G^{-1} \;=\; \pi^{-1} \times \pi^{-1} \times \pi^{-1} \times \cdots

Because the blocks are disjoint, the global map is a product of independent invertible maps — to run time backwards, apply the inverse block map to each block. No Garden-of-Eden hunting, no undecidability: reversibility is free. Compare the price list: checking an arbitrary 2-D rule is undecidable; checking a block rule means checking that a 16-row table has no repeated output. A five-second job.

One catch: with a fixed partition, each 2\times2 block is a sealed four-cell universe — nothing can ever cross a block boundary, so nothing interesting can happen. The fix, due to Norman Margolus, is beautifully cheap: alternate the partition. On even steps use blocks aligned at even coordinates; on odd steps shift the whole partition by (1,1) — one cell across and one cell down. Every cell then shares a block with its diagonal neighbours on one step and the other diagonal neighbours on the next, and information percolates across the grid. This alternating pair of partitions is the Margolus neighbourhood.

The two partitions, side by side in time

The figure shows a 4 \times 4 patch of grid. Step through it: first the aligned partition (solid), then the shifted one (dashed). A cell sitting at the corner of a solid block sits at the centre of a dashed block — the two partitions interlock like bricks in a wall, which is exactly why gluing them in alternation lets signals travel.

A worked block rule: the rotation rule

Here is a complete reversible CA in one sentence: "each step, rotate the contents of every block a quarter-turn clockwise." Writing a block's four cells as \begin{psmallmatrix} a & b \\ c & d \end{psmallmatrix}, the block map is

\pi:\ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \longmapsto \begin{pmatrix} c & a \\ d & b \end{pmatrix},

a permutation of the four cell positions, hence certainly a bijection on the 16 block states — reversible, no further questions. Its inverse is the quarter-turn anticlockwise. Run forwards for a while and the grid churns like a tray of interlocking gears (blocks rotate, then the shifted blocks rotate the rotated pieces…); to rewind, apply anticlockwise turns with the partition sequence reversed. Note what this rule incidentally does: it moves 1-cells around without ever creating or destroying one. Block maps that preserve the number of 1s give conservative dynamics — "particles" — and choosing the block map wisely turns those particles into billiard balls: that is precisely the billiard-ball computer's collision rule, waiting on the next page.

A classic slip: to invert a Margolus CA you apply the inverse block map — and you must also run the partition schedule backwards. If the forward run went aligned, shifted, aligned, shifted, the backward run must go shifted, aligned, shifted, aligned, undoing the most recent step first. Apply \pi^{-1} on the wrong partition and you are not inverting anything — you are running some unrelated (though still reversible!) dynamics. The inverse of "do A then B" is "undo B then undo A" — composition reverses order, here as everywhere.

Trick 2: second-order (Fredkin) rules

The second reversibilisation trick doesn't touch the neighbourhood at all — it touches time. Take any function f of the neighbourhood — any rule whatsoever, as irreversible as you like — and define the new state from the last two time steps:

s_i(t+1) \;=\; f\big(\text{neighbourhood of } i \text{ at time } t\big) \;\oplus\; s_i(t-1).

This is Edward Fredkin's second-order technique, and it is automatically reversible, for any f. Why? XOR the equation with s_i(t+1) — since x \oplus x = 0, the equation solves for the past:

s_i(t-1) \;=\; f\big(\text{neighbourhood at } t\big) \;\oplus\; s_i(t+1).

The same formula runs the film in both directions: knowing rows t and t+1, you recompute row t-1 exactly. (Formally the state pair (s(t-1), s(t)) is what evolves bijectively, so the second-order CA is an ordinary reversible CA on a doubled state set.) Worked micro-example: if f = 1 at some cell and s_i(t+1) = 1, then s_i(t-1) = 1 \oplus 1 = 0 — recovered, no search required. Applied to the chaotic elementary rules this yields the famous reversible rules "90R", "110R", "150R"… — every one of the 256 elementary CA has a reversible second-order shadow.

Run one backwards, in code

Below is Rule 90R — the second-order version of the very rule we convicted of irreversibility on the previous page: s_i(t+1) = s_{i-1}(t) \oplus s_{i+1}(t) \oplus s_i(t-1). We run it forward from a single seed, then perform the entire time-reversal in one line — swap the two remembered rows — and step the same function again. Watch the triangle rebuild itself in mirror image, back to the seed:

const W = 31, T = 12; const show = (s: number[]): string => s.map((c) => (c ? "█" : "·")).join(""); // One second-order step: next = (left XOR right) XOR previous. Rule 90, made reversible. const step = (prev: number[], cur: number[]): number[] => cur.map((_, i) => cur[(i + W - 1) % W] ^ cur[(i + 1) % W] ^ prev[i]); let prev: number[] = new Array(W).fill(0); let cur: number[] = new Array(W).fill(0); cur[15] = 1; // a single seed cell const start = show(cur); console.log("forward:"); for (let t = 0; t < T; t++) { console.log(show(cur)); const next = step(prev, cur); prev = cur; cur = next; } // Time reversal: swap the two remembered rows, keep using the SAME step function. [prev, cur] = [cur, prev]; console.log("reversed:"); let last = ""; for (let t = 0; t < T; t++) { last = show(cur); console.log(last); const next = step(prev, cur); prev = cur; cur = next; } console.log("recovered the seed row? " + (last === start));

No inverse rule was derived, no equations solved: the XOR structure means the dynamics is its own rewind button. Two remembered rows are the entire cost of never forgetting anything.

Second-order-in-time reversibility should feel familiar: it is how mechanics works. Newton's F = ma is second-order — acceleration relates positions at three successive instants — and a discrete integrator like Verlet's, x(t+1) = 2x(t) - x(t-1) + a(t)\,\Delta t^2, has exactly the shape of Fredkin's rule with XOR replaced by ± arithmetic: solve it for x(t-1) and you get the same formula back. That is why Verlet integration is the workhorse of molecular dynamics — it inherits time-reversibility from the physics it simulates. Fredkin's XOR version is the mod-2 spirit of Newton: a discrete universe whose future needs two frames of the past, and whose past needs two frames of the future. Physics permitting, motion is a second-order affair.

Two engines, one guarantee

Note what is not on the requirements list: the block map does not need to conserve particles, respect symmetries, or be gentle in any way — bijectivity alone buys reversibility. Conservation laws are an extra design choice, and the next two pages spend it deliberately: the billiard-ball collision rule conserves balls to mimic mechanics, and the lattice gases conserve momentum to mimic fluids.