Generalized additivity [in cellular automata]

In general what it means for a system to be additive is that some addition operation ⊕ can be used to combine any set of evolution histories to yield another possible evolution history. If ϕ is the rule for the system, this then requires for any states u and v the distributive property

ϕ[u⊕v]ϕ[u]⊕ϕ[v]

(In mathematical terms this is equivalent to the statement that ϕ is conjugate to itself under the action of ⊕—or alternatively that ϕ defines a homomorphism with respect to the ⊕ operation.) In the usual case, u⊕v is just Mod[u+v, k], yielding say for rule 90 the results below.

But it turns out that some elementary rules show additivity with respect to other addition operations. An example as shown below is rule 250 with u⊕v taken as Max[u, v] (Or).

If a system is additive it means that one can work out how the system will behave from any initial condition just by combining the patterns ("Green's functions") obtained from certain basic initial conditions—say ones containing a single black cell. To get all the familiar properties of additivity one needs an addition operation that is associative (Flat) and commutative (Orderless), and has an identity element (white or 0 in the cases above)—so that it defines a commutative monoid. (Usually it is also convenient to be able to get all possible elements by combining a small number of basic generator elements.)

The inequivalent commutative monoids with up to k = 4 colors are (in total there are 1, 2, 5, 19, 78, 421, 2637, … such objects):

For k = 2, r = 1 the number of rules additive with respect to these is respectively: {8, 9}; for k = 2, r = 2: {32, 33}; for k = 3, r = 1: {28, 27, 35, 244, 28}; for k = 4, r = 1:

{1001, 65, 540, 577, 126, 4225, 540, 9065, 757, 408, 65, 133, 862, 224, 72, 72, 91, 4096, 64}

It turns out to be possible to show that any rules ϕ additive with respect to some addition operation ⊕ must work by applying that operation to values associated with cells in their neighborhood. The values are obtained by applying to cells at each position one of the unary operations (endomorphisms) σ that satisfy σ[a⊕b]σ[a]⊕σ[b] for individual cell values a and b. (For Xor, there are 2 possible σ, while for Or there are 3.)

The basic examples are then rules of the form RotateLeft[a]⊕RotateRight[a]—analogs of rule 90, but with other addition operations (compare page 886). The σ can be used to give analogs of the weights that appear in the note above. And rules that involve more than two cells can be obtained by having several instances of ⊕—which can always be flattened. But in all cases the general results for associative rules on page 956 show that the patterns obtained must be at most nested.

If instead of an ordinary cellular automaton with a limited number of possible colors one considers a system in which every cell can have any integer value then additivity with respect to ordinary addition becomes just traditional linearity. And the only way to achieve this is to have a rule in which the new value of a cell is given by a linear form such as a x + b y. If the values of cells are allowed to be any real number then linear forms such as a x + b y again yield additivity with respect to ordinary addition. But in general one can apply to each cell value any function σ that obeys the so-called Cauchy functional equation σ[x+y]σ[x] + σ[y]. If σ[x] is required to be continuous, then the only form it can have is c x. But if one allows σ to be discontinuous then there can be some other exotic possibilities. It is inevitable that within any rationally related set of values x one must have σ[x] = c x with fixed c. But if one assumes the Axiom of Choice then in principle it becomes possible to construct σ[x] which have different c for different sets of x values. (Note however that I do not believe that such σ could ever actually be constructed in any explicit way by any real computational system—or in fact by any system in our universe.)

In general ⊕ need not be ordinary addition, but can be any operation that defines a commutative monoid—including an infinite one. An example is ordinary numbers modulo an irrational. And indeed a cellular automaton whose rule is based on Mod[x+y, π] will show additivity with respect to this operation (see page 922). If ⊕ has an inverse, so that it defines a group, then the only continuous (Lie group) examples turn out to be combinations of ordinary addition and modular addition (the group U(1)). This assumes, however, that the underlying cellular automaton has discrete cells. But one can also imagine setting up systems whose states are continuous functions of position. ϕ then defines a mapping from one such function to another. To be analogous to cellular automata one can then require this mapping to be local, in which case if it is continuous it must be just a linear differential operator involving Derivative[n]—and at some level its behavior must be fairly simple. (Compare page 161.)