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 from 1 to 6. There are only 8 rules (the inequivalent ones being 16740555 and 3327051468) where , and in each case > s while = 6s = 5. For k = 3, r = 1, there are a total of 936 rules with this property: 576, 216 and 144 with , = 45 and 6, and in all cases s = 3. Examples with , = 34, 5 and 6 are shown below. For arbitrary k and r, it is not clear what the maximum can be; the only bound rigorously established so far is ≤ r + 1/2k^{2 r + 1} (k^{2 r} - 1).