Chapter 9: Fundamental Physics

Section 2: The Notion of Reversibility

Inverse [cellular automaton] rules

Some reversible rules are self-inverse, so that applying the same rule twice yields the identity. Other rules come in distinct pairs. Most often a rule that involves r neighbors has an inverse that also involves at most r neighbors. But for both k=2, r=2 and k=3, r=1 there turn out to be reversible rules whose inverses involve larger numbers of neighbors. For any given rule one can define the neighborhood size s to be the largest block of cells that is ever needed to determine the color of a single new cell. In general s <= 2r + 1, and for a simple identity or shift rule, s=1. For k=2, r=1, it then turns out that all the reversible rules and their inverses have s=1. For k=2, r=2, the reversible rules have values of s from 1 to 5, but their inverses have values OverBar[s] from 1 to 6. There are only 8 rules (the inequivalent ones being 16740555 and 3327051468) where OverBar[s]>s, and in each case OverBar[s]=6 while s=5. For k=3, r=1, there are a total of 936 rules with this property: 576, 216 and 144 with OverBar[s]=4, 5 and 6, and in all cases s=3. Examples with OverBar[s]=3, 4, 5 and 6 are shown below. For arbitrary k and r, it is not clear what the maximum OverBar[s] can be; the only bound rigorously established so far is OverBar[s]<= r + k^(2 r + 1) (k^(2 r)-1) /2.

From Stephen Wolfram: A New Kind of Science [citation]