More general conserved quantities
Some rules conserve not total numbers of cells with given colors, but rather total numbers of blocks of cells with given forms—or combinations of these. The pictures below show the simplest quantities of these kinds that end up being conserved by various elementary rules.
Among the 256 elementary rules, the total numbers that have conserved quantities involving at most blocks of lengths 1 through 10 are {5, 38, 66, 88, 102, 108, 108, 114, 118, 118}.
Rules that show complicated behavior usually do not seem to have conserved quantities, and this is true for example of rules 30, 90 and 110, at least up to blocks of length 10.
One can count the number of occurrences of each of the kb possible blocks of length b in a given state using
BC[list_] := With[{z = Map[FromDigits[#, k] &, Partition[list, b, 1, 1]]}, Map[Count[z, #] &, Range[0, kb - 1]]]
Conserved quantities of the kind discussed here are then of the form q . BC[a] where q is some fixed list. A way to find candidates for q is to compute
NullSpace[Table[With[{u = Table[Random[Integer, {0, k - 1}], {m}]}, BC[CAStep[u]] - BC[u]], {s}]]
for progressively larger m and s, and to see what lists continue to appear. For block size b, kb - 1 lists will always appear as a result of trivial conserved quantities. (With k = 2, for b = 1, {1, 1} represents conservation of the total number of cells, regardless of color, while for b = 2, {1, 1, 1, 1} represents the same thing, while {0, 1, -1, 0} represents the fact that in going along in any state the number of black-to-white transitions must equal the number of white-to-black ones.) If more than kb - 1 lists appear, however, then some must correspond to genuine non-trivial conserved quantities. To identify any such quantity with certainty, it turns out to be enough to look at the kb + 2r - 1 states where no block of length b + 2r - 1 appears more than once (and perhaps even just some fairly small subset of these).
(See also page 981.)