Implementation [of conserved quantity test] Whether a k -color cellular automaton with range r conserves total cell value can be determined from Catch[Do[ (If[Apply[Plus, CAStep[rule, #] - #] ≠ 0, Throw[False]] &)[ IntegerDigits[i, k, m]], {m, w}, {i, 0, k m - 1}]; True] where w can be taken to be k 2r , and perhaps smaller. … Among the 2 32 k = 2 , r = 2 rules 428 do, and of these 2 are symmetric, and 6 are reversible, and all these are just shift and identity rules.

Relation [of powers] to substitution systems Despite the uniform distribution result in the note above, the sequence Floor[(n + 1) h] - Floor[n h] is definitely not completely random, and can in fact be generated by a sequence of substitution rules. The first m rules (which yield far more than m elements of the original sequence) are obtained for any h that is not a rational number from the continued fraction form (see page 914 ) of h by Map[(({0  Join[#, {1}], 1  Join[#, {1, 0}]} &)[Table[0, {# - 1}]]) &, Reverse[Rest[ContinuedFraction[h, m]]]] Given these rules, the original sequence is given by Floor[h] + Fold[Flatten[#1 /. #2] &, {0}, rules] If h is the solution to a quadratic equation, then the continued fraction form is repetitive, and so there are a limited number of different substitution rules.

The rule {2, 3}  {{2, 1}, {1}} specifies that when NeighborNumbers gives {2, 3} for a node i , the connections from that node should become {Follow[list, i, {2, 1}], Follow[list, i, {1}]} . The rule {2, 3}  {{{2, 1}, {1, 1}}, {1}} specifies that a new node should be inserted in the above connection, and this new node should have connections {Follow[list, i, {2, 1}], Follow[list, i, {1, 1}]} . With rules set up in this way, each step in the evolution of a network system is given by NetEvolveStep[{depth_Integer, rule_List}, list_List] := Block[ {new = {}}, Join[Table[Map[NetEvolveStep1[#, list, i] &, Replace[NeighborNumbers[list, i, depth], rule]], {i, Length[list]}], new]] NetEvolveStep1[s : {___Integer}, list_, i_] := Follow[list, i, s] NetEvolveStep1[{s1 : {___Integer}, s2 : {___Integer}}, list_, i_] := Length[list] + Length[ AppendTo[new, {Follow[list, i, s1], Follow[list, i, s2]}]] The set of nodes that can be reached from node i is given by ConnectedNodes[list_, i_] := FixedPoint[Union[Flatten[{#, list 〚 # 〛 }]] &, {i}] and disconnected nodes can be removed using RenumberNodes[list_, seq_] := Map[Position[seq, #] 〚 1, 1 〛 &, list 〚 seq 〛 , {2}] The sequence of networks obtained on successive steps by applying the rules and then removing all nodes not connected to node number 1 is given by NetEvolveList[rule_, init_, t_Integer] := NestList[(RenumberNodes[#, ConnectedNodes[#, 1]] &)[ NetEvolveStep[rule, #]] &, init, t] Note that the nodes in each network are not necessarily numbered in the order that they appear on successive lines in the pictures in the main text.

But then he looked at rules that remove three elements at each step, and he discovered the rule {3, {{0, _, _}  {0, 0}, {1, _, _}  {1, 1, 0, 1}}} . As he noted, the behavior of this rule varies considerably with the initial conditions used. But at least for all the initial conditions up to length 28, the rule eventually just leads to behavior that repeats with a period of 1, 2, 6, 10, 28 or 40.

But from the discoveries in this book we now know that much simpler rules can also yield very complicated behavior. And as the pictures below show, this is true even just for parts of the rules above ( s alone yields outer totalistic code 686 in 2D, and rule 90 in 1D). Ulam also in 1967 considered the pure 2D cellular automaton with outer totalistic code 12 (though he stated its rule in a complicated way).

Additive cellular automata [in finite regions] In the case of additive rules such as rule 90 and rule 60, a mathematical analysis of the repetition periods can be given (as done by Olivier Martin , Andrew Odlyzko and me in 1983). … In the case of rule 90 a similar analysis can be given, with the 1 + x used at each step replaced by 1/x + x . … Unlike for the case of rule 60, the period is usually equal to q[n] (and is assumed so for the picture on page 260 ), with the first exception occurring at n=37 .

Symbolic systems [emulating cellular automata] Given the rules for an elementary cellular automaton in the form used on page 867 (with {0, 0, 0}  0 ), the following will construct a symbolic system which emulates it: Flatten[{Array[(p[x_][#1][#2][#3]  p[x[{##} /. rules]][#2][#3]) &, {2, 2, 2}, 0] /. {0  p, 1  q}, {r[x_]  p[r[p][p]][x], p[x_][p][p][r]  x[p][p][r]}}] The initial condition for the symbolic system is given by Fold[#1[#2] &, r[p][p], init /. {0  p, 1  q}][p][p][r] Step t in the cellular automaton corresponds to step t (t + Length[init] + 3) in the symbolic system. Note that the succession of states shown here depends on the detailed order in which rules are applied (see page 898 ). It is also possible to construct symbolic systems with the so-called confluence property, in which results from any fixed number of steps of cellular automaton evolution can be found by applying rules in any possible order (see page 1036 ).

The pictures below show the lowest-numbered cellular automaton rules that manage to generate repetitive sequences containing black cells with successively greater separations s . … (Note that for example in the s = 15 case the lowest-numbered rule exhibits a complex 350-step transient away from the center column.) … Since some different rules generate the same sequences (see page 956 ) one needs to go through somewhat more than 2 n rules to get every sequence of length n .

Mobile automata [from cellular automata] Given a mobile automaton with rules in the form used on page 887 , a cellular automaton which emulates it can be constructed using MAToCA[rules_] := Append[Flatten[Map[g, rules]], {_, _, x_, _, _}  x] g[{a_, b_, c_}  {d_, e_}] := {{_, a, b + 2, c, _}  d, If[e  1, {a, b + 2, c, _, _}  c + 2, {_, _, a, b + 2, c}  a + 2]} This specific definition assumes that the mobile automaton has two possible colors for each cell; it yields a cellular automaton with four possible colors for each cell.

The rule can be given by specifying a list of cases such as {0, 0, 0}  {1, {1, -1}} , where in each case the second sublist specifies the new relative positions of active cells. With this setup successive steps in the evolution of the system can be obtained from GMAStep[rules_, {list_, nlist_}] := Module[{a, na}, {a, na} = Transpose[Map[Replace[Take[list, {# - 1, # + 1}], rules]&, nlist]]; {Fold[ReplacePart[#, Last[#2], First[#2]]&, list, Transpose[{nlist, a}]], Union[Flatten[nlist + na]]}]