# Notes

## 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 2 r + 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 s from 1 to 6. There are only 8 rules (the inequivalent ones being 16740555 and 3327051468) where s > s, and in each case 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 s = 4, 5 and 6, and in all cases s = 3. Examples with s = 3, 4, 5 and 6 are shown below. For arbitrary k and r, it is not clear what the maximum s can be; the only bound rigorously established so far is s r + 1/2k2 r + 1 (k2 r - 1).

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