Notes

Chapter 9: Fundamental Physics

Section 2: The Notion of Reversibility


Generalized additive [cellular automaton] rules

Additive cellular automata of the kind discussed on page 952 can be generalized by allowing the new value of each cell to be obtained from combinations of cells on s previous steps. For rule 90 the combination c can be specified as {{1,0,1}}, while for rule 150R it can be specified as {{0,1,0},{1,1,1}}. All generalized additive rules ultimately yield nested patterns. Starting with a list of the initial conditions for s steps, the configurations for the next s steps are given by

Append[Rest[list], Map[Mod[Apply[Plus, Flatten[c #]], 2]&, Transpose[Table[RotateLeft[list, {0, i}], {i, -r, r}], {3, 2, 1}]]]

where r = (Length[First[c]]-1)/2.

Just as for ordinary additive rules on page 1091, an algebraic analysis for generalized additive rules can be given. The objects that appear are solutions to linear recurrences of order s, and in general involve s^th roots. For rule 150R, the configuration at step t as shown in the picture on page 439 is given by (u^t - v^t)/Sqrt[4 + h^2], where {u,v}=z /. Solve[z^2==h z + 1] and h=(1/x+1+x). (See also page 1078.)

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