[Universality for] classes of systems This chapter has shown that various individual systems with fixed rules exhibit universality when suitable initial conditions are chosen. One can also consider whole classes of systems in which rules as well as initial conditions can be chosen.

Background [in rule 110] At every step the background pattern in rule 110 consists of repetitions of the block b = {1,0,0,1,1,0,1,1,1,1,1,0,0,0} , as shown in the picture below.

Mobile automata [emulating cellular automata] Given the rules for an elementary cellular automaton in the form used on page 867 , the following will construct a mobile automaton which emulates it: vals = {x, p[0], q[0, 0], q[0, 1], q[1, 0], q[1, 1], p[1]} CAToMA[rules_] := Table[(#  Replace[#, {{q[a_, b_], p[c_], p[d_]}  {q[c, {a, c, d} /. rules], 1}, {q[a_, b_], p[c_], x}  {q[c, {a, c, 0} /. rules], 1}, {q[_, _], x, x}  {p[0], -1}, {q[_, _], q[_, a_], p[_]}  {p[a], -1}, {x, q[_, a_], p[_]}  {p[a], -1}, {x, x, p[_]}  {q[0, 0], 1}, {_, _, _}  {x, 0}}]) &[vals 〚 IntegerDigits[i, 7, 3] + 1 〛 ], {i, 0, 7 3 - 1}] The ordering in vals defines a mapping of symbolic cell values onto colors.

But for multiway systems where each rule p  q is accompanied by its reverse q  p , and such pairs are represented say by "AAB" ↔ "BBAA" , an equivalent operator system can immediately be obtained either from Apply[Equal, Map[Fold[#2[#1] &, x, Characters[#]] &, rules, {2}], {1}] or from (compare page 1172 ) Append[Apply[Equal, Map[(Fold[f, First[#], Rest[#]] &)[Characters[#]] &, rules, {2}], {1}], f[f[a, b], c]  f[a, f[b, c]]] where now objects like "A" and "B" are treated as constants—essentially functions with zero arguments. With slightly more effort multiway systems with ordinary one-way rules can also be converted to operator systems.

In the usual case, u ⊕ v is just Mod[u+v, k] , yielding say for rule 90 the results below. … An example as shown below is rule 250 with u ⊕ v taken as Max[u, v] ( Or ). … The basic examples are then rules of the form RotateLeft[a] ⊕ RotateRight[a] —analogs of rule 90, but with other addition operations (compare page 886 ).

Symmetric 5-neighbor [2D cellular automaton] rules Among the 32 possible 5-cell neighborhoods shown for example on page 941 there are 12 classes related by symmetries, given by s = {{1}, {2, 3, 9, 17}, {4, 10, 19, 25}, {5}, {6, 7, 13, 21}, {8, 14, 23, 29}, {11, 18}, {12, 20, 26, 27}, {15, 22}, {16, 24, 30, 31}, {28}, {32}} Completely symmetric 5-neighbor rules can be numbered from 0 to 4095, with each digit specifying the new color of the cell for each of these symmetry classes of neighborhoods. Such rule numbers can be converted to general form using FromDigits[Map[Last, Sort[Flatten[Map[Thread, Thread[{s, IntegerDigits[n, 2, 12]}]], 1]]], 2]

The evolution of the system for t steps can be obtained from SSEvolve[rule_, init_, t_, d_Integer] := Nest[FlattenArray[# /. rule, d] &, init, t] FlattenArray[list_, d_] := Fold[Function[{a, n}, Map[MapThread[Join, #, n] &, a, -{d + 2}]], list, Reverse[Range[d] - 1]] The analog in 3D of the 2D rule on page 187 is {1  Array[If[LessEqual[##], 0, 1] &, {2, 2, 2}], 0  Array[0 &, {2, 2, 2}]} Note that in d dimensions, each black cell must be replaced by at least d + 1 black cells at each step in order to obtain an object that is not restricted to a dimension d - 1 hyperplane.

Ultimately what one wants to do is to find what possible types of forms for local regions are inequivalent under the application of the underlying rules. But in general it may be undecidable even whether two such forms are actually equivalent (compare the notes below and on page 1051 )—since to tell this one might need to be able to apply the rules infinitely many times. … And a first step may be to look at small closed networks and try to determine which of these can be transformed into each other by a given set of rules.

In the examples on page 248 , however, such behavior always seems to occur superimposed on some kind of repetitive background—much as in the case of the rule 110 one-dimensional cellular automaton on page 229 . … Much as in one dimension this does not seem to happen with the very simplest possible kinds of rules. But as soon as one goes to slightly more complicated rules—though still very simple—one can find examples.

And so, for example, in looking at the pictures below it would normally seem much more plausible that rule 254 might have been set up for the purpose of generating a uniformly expanding pattern than that rule 30 might have been. For while rule 30 does generate such a pattern, it also does a lot else that appears irrelevant to this purpose.