Notes

Chapter 6: Starting from Randomness

Section 5: Randomness in Class 3 Systems


Additive [cellular automaton] rules

Of the 256 elementary cellular automata 8 are additive: {0, 60, 90, 102, 150, 170, 204, 240}. All of these are either trivial or essentially equivalent to rules 90 or 150.

Of all k^k^(2r+1) rules with k colors and range r it turns out that there are always exactly k^(2r+1) additive ones—each obtained by taking the cells in the neighborhood and adding them modulo k with weights between 0 and k-1. As discussed on page 955, any rule based on addition modulo k must yield a nested pattern, and it therefore follows that any rule that is additive must give a nested pattern, as in the examples below. (See also page 870.)

Note that each step in the evolution of any additive cellular automaton can be computed as

Mod[ListCorrelate[w, list, Ceiling[Length[w]/2]], k]

(See page 1087 for a discussion of partial additivity.)

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