[Converting from CAs with] more colors
Given a rule that involves three colors and nearest neighbors, the following converts each case of the rule to a collection of cases for a rule with two colors:
CA3ToCA2[{a_, b_, c_} d_] := Union[Flatten[Table[Thread[Partition[Flatten[{l, a, b, c, r} /. coding], 11, 1]〚{2, 3, 4}〛 (d /. coding)], {l, 0, 2}, {r, 0, 2}], 2]]
coding = {0 {0, 0, 0}, 1 {0, 0, 1}, 2 {0, 1, 1}}
The problem of encoding cells with several colors by blocks of black and white cells is related to standard problems in coding theory (see page 560). One approach is to use {1, 1} to indicate the boundary of each block, and then within each block to use all possible digit sequences which do not contain {1, 1}, as in the Fibonacci number system discussed on page 892. Note that the original rule with k colors and r neighbors involves Log[2, kk2 r + 1] bits of information; the two-color rule that emulates it involves Log[2, 222 s + 1] bits. As a result, the minimum possible s for k = 3, r = 1 is about 2.2; in the specific example shown in the main text it is 5.