Second-order cellular automata Second-order elementary rules can be implemented using CA2EvolveList[rule_List, {a_List, b_List}, t_Integer] := Map[First, NestList[CA2Step[rule, #]&, {a, b}, t]] CA2Step[rule_List, {a_, b_}] := {b, Mod[a + rule 〚 8 - (RotateLeft[b] + 2 (b + 2 RotateRight[b])) 〛 , 2]} where rule is obtained from the rule number using IntegerDigits[n, 2, 8] . The combination Drop[list, -1] + 2 Drop[list, 1] of the result from CA2EvolveList corresponds to evolution according to a first-order k = 4 , r = 1 rule.

So if they have simple underlying rules, do all cellular automata started from random initial conditions eventually settle down to give stable states that somehow look simple? … The rule in this case was first shown on page 24 , and is number 254 in the scheme described on page 53 . … The rules shown here correspond to numbers 0, 32, 160 and 250.

The first two rules yield simple repetitive computationally reducible behavior in which the outcome after many steps can readily be deduced without tracing each step. The third rule yields behavior that appears to be computationally irreducible, so that its outcome can effectively be found only by explicitly tracing each step. The cellular automata shown here all have 3-color totalistic rules.

Compositions of cellular automata One way to construct more complicated rules is from compositions of simpler rules. … The result is in effect a k = 2 , r = 2 rule. Usually the order in which the two elementary rules are applied will matter, and the overall behavior obtained will have no simple relationship to that of either of the individual rules.

[Cellular automaton state] network properties The number of nodes and connections at step t > 1 are: rule 108: 8 , 13 ; rule 128: 2t , 2t + 2 ; rule 132: 2t + 1 , 3t + 3 ; rule 160: (t + 1) 2 , (t + 1)(t + 3) ; rule 184: 2t , 3t + 1 . … For t = 2 , rule 22 gives the largest network, with 280 nodes and 551 arcs. The k = 2 , r = 2 totalistic rule with code 20 gives a network with 65535 nodes after just 1 step.

But what the discoveries in this book now show is that by using the types of rules embodied in simple programs one can capture many of the essential mechanisms of nature. … Experience with traditional engineering has led to the general assumption that to perform a sophisticated task requires constructing a system whose basic rules are somehow correspondingly complicated. But the discoveries in this book show that this is not the case, and that in fact extremely simple underlying rules—that might for example potentially be implemented directly at the level of atoms—are often all that is needed.

and especially a simple one—then it can be extremely difficult to determine whether or not the rule is universal. As we discussed in the previous chapter , the usual way to demonstrate that a rule is universal is to find a scheme for setting up initial conditions and for decoding output that makes the rule emulate some other rule that is already known to be universal.

Algebraic forms [for cellular automaton rules] The rules here can be expressed in algebraic terms (see page 869 ) as follows: • Rule 30: Mod[p + q + r + q r, 2] • Rule 45: Mod[1 + p + r + q r, 2] • Rule 73: Mod[1 + p + q + r + p r + p q r, 2]

Inverse [cellular automaton] rules Some reversible rules are self-inverse, so that applying the same rule twice yields the identity. Other rules come in distinct pairs. … In general s ≤ 2 r + 1 , and for a simple identity or shift rule, s = 1 .

[No text on this page] Evolution of cellular automata with a sequence of different possible rules, starting in all cases from a single black cell.