# Notes

## 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 km is (1/2k (k + 1))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]