Notes

Chapter 2: The Crucial Experiment

Section 1: How Do Simple Programs Behave?


More colors [in additive cellular automata]

The pictures below show generalizations of rule 90 to k possible colors using the rule

CAStep[k_Integer, a_List] := Mod[RotateLeft[a] + RotateRight[a], k]

or equivalently Mod[ListCorrelate[{1,0,1},a,2],k]. The number of cells that are not white on row t in this case is given by Apply[Times, 1 + IntegerDigits[t, k]]. (For non-prime k, the patterns are obtained by superimposing the patterns corresponding to the factors of k.) A related result is that IntegerExponent[Binomial[t, n],k] is given by the number of borrows in the base k subtraction of n from t. Mod[Binomial[t, n], k] is given for prime k by

With[{d = Ceiling[Log[k, Max[t, n]+1]]}, Mod[ Apply[Times,Apply[Binomial , Transpose[{IntegerDigits[t, k, d] , IntegerDigits[n, k, d] }], {1}]], k] ]

The patterns obtained for any k are nested. For prime k the total number of non-white cells down to step k^m is (k (k+1)/2)^m and the patterns have fractal dimension 1 + Log[k, (k+1)/2] (see page 955). These are examples of additive rules, discussed further on page 952. (See also page 922 for the continuous case.)

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