Collisions [in rule 110] A fundamental result is that the sum of the widths of all persistent structures involved in an interaction must be conserved modulo 14.

But for example in the rule (a) picture on page 463 there is in effect a block of solid that persists in the middle—so that no ordinary diffusion behavior is seen. In rule (c) there is considerable apparent randomness, but it turns out that there are also fluctuations that last too long to yield ordinary diffusion.

But the problem is not known to be NP-complete for the specific case of, say, rule 30. Significantly less work has been done on the problem of finding initial conditions for rule 30 than on the problem of factoring integers. But the greater simplicity of rule 30 might make one already have almost as much confidence in the difficulty of solving this problem as of factoring integers.

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] . … These are examples of additive rules, discussed further on page 952 .

The specific form of the continuous generalization of the modulo 2 function used is λ [x_] := Exp[-10 (x - 1) 2 ] + Exp[-10 (x - 3) 2 ] Each cell in the system is then updated according to λ [a + c] for rule 90, and λ [a + b + c + b c] for rule 30.

Network mobile automata The analog of a mobile automaton can be defined for networks by setting up a single active node, then having rules which replace clusters of nodes around this active node, and move its position. … The total number of replacements that can be used in the rules of a network mobile automaton and which involve clusters with up to four nodes and have from 1 to 4 dangling connections is {14, 10, 2727, 781} .

The rule used is of the same kind as on the previous page , but now takes the center cell to become black only if it has exactly 3 black neighbors.

The cellular automaton involves 28 colors and nearest-neighbor rules.

The pictures on the facing page show a few other examples of sequences generated according to simple rules based on properties of numbers. … And indeed the only reasonable conclusion seems to be that just as in so many other systems in this book, such sequences of numbers exhibit complexity that somehow arises as a fundamental consequence of the rules by which the sequences are generated.

In substitution systems with geometrical replacement rules there is slightly more freedom, but still the elements are ultimately constrained to lie in a two-dimensional plane. … A network system is fundamentally just a collection of nodes with various connections between these nodes, and rules that specify how these connections should change from one step to the next.