And with this representation, the evolution for t steps is given by SSEvolveList[rule_, init_List, t_Integer] := NestList[Flatten[# /. rule]&, init, t] where in the first example on page 82 , the initial condition is {1} . An alternative approach is to use strings, representing the rule by {"B"  "BA", "A"  "AB"} and the initial condition by "B" . In this case, the evolution can be obtained using SSEvolveList[rule_, init_String, t_Integer] := NestList[StringReplace[#, rule]&, init, t] For a neighbor-dependent substitution system such as the first one on page 85 the rule can be given as {{1, 1}  {0, 1}, {1, 0}  {1, 0}, {0, 1}  {0}, {0, 0}  {0, 1}} And with this representation, the evolution for t steps is given by SS2EvolveList[rule_, init_List, t_Integer] := NestList[Flatten[Partition[#, 2, 1] /. rule]&, init, t] where the initial condition for the first example on page 85 is {0, 1, 1, 0} .

For k = 2 , r = 2 there are 4,294,967,296 rules in all, of which 64 are totalistic. And for k = 3 , r = 1 there are 7,625,597,484,987 rules in all, with 2187 totalistic ones.) … I first introduced totalistic rules in 1983.

Properties [of doubling rules] The number of steps increases irregularly but roughly quadratically with n in rule (a), and roughly linearly in (d) and (e). Rule (b) in the end repeats every 128 steps. The center of the complex pattern in both (d) and (e) emulates k = 2 rule 90.

Rule (k) was shown on the previous page ; rules (d) and (f) on page 205 .

And once again what we see is that for rules with fairly simple behavior the formulas are usually fairly simple. But in cases like rule 30, the formulas one gets are already quite complicated even after just two steps.

With k possible colors for each cell, there are a total of k k 2 possible rules of this type, each specified by a k 2 -digit number in base k (7743 for the rule shown above). For k = 2 , there are 16 possible rules, and the most complicated pattern obtained is nested like the rule 90 elementary cellular automaton. … With rule given by IntegerDigits[num, k, k 2 ] a single step of evolution can be implemented as CAStep[{k_, rule_}, a_List] := rule 〚 k 2 - RotateLeft[a] - k a 〛

Other examples [of cellular automaton computation] Rule 152 and rule 144, which effectively compute Ceiling[n/2] and Ceiling[n/4] , respectively, are shown below with n = 18 initial black cells. As discussed on page 989 rule 184 effectively determines whether its initial conditions correspond to a balanced sequence of open and close parentheses. (Rule 132 can be viewed as being like a syntax checker for a regular language; rule 184 for a context-free language.)

Implementation of general cellular automata With k colors and r neighbors on each side, a single step in the evolution of a general cellular automaton is given by CAStep[CARule[rule_List, k_, r_], a_List] := rule 〚 -1 - ListConvolve[k^Range[0, 2r], a, r + 1] 〛 where rule is obtained from a rule number num by IntegerDigits[num, k, k 2r + 1 ] .

Deducing cellular automaton rules Given a complete cellular automaton pattern it is easy to deduce the rule which produced it just by identifying examples of places where each element in the rule was used, as in the picture below. Given an incomplete pattern, deducing the rule in effect requires solving Boolean equations.

[No text on this page] Totalistic cellular automata whose rules involve nearest and next-nearest neighbors, and where each cell has two possible colors.