[Construction of] universal objects A more direct way to create a universal object is to set up, say, a 4D array in which two of the dimensions range respectively over possible 1D cellular automaton rules and over possible initial conditions, while the other two dimensions correspond to space and time in the evolution of each cellular automaton from each initial condition.

If the underlying cellular automaton rule exhibits an invariance—say under reflection in space or permutation of colors—this will also often lead to the presence of identical pieces in the final network, corresponding to cosets of the symmetry transformation.

Nonlinear feedback shift registers Linear feedback shift registers of the kind discussed on page 974 can be generalized to allow any function f (note the slight analogy with cyclic tag systems): NLFSRStep[f_, taps_, list_] := Append[Rest[list], f[list 〚 taps 〛 ]] With the choice f=IntegerDigits[s, 2, 8] 〚 8 - # . {4, 2, 1} 〛 & and taps = {1, 2, 3} this is essentially a rule s elementary cellular automaton. … The case analogous to rule 30 yields some of the longest repetition periods—usually remarkably close to the absolute maximum of 2 n - 1 (for n = 21 the result is 1999864, 95% of the maximum). … Tap positions {1, 2, 3, 4} were among those studied, but nothing like the pictures below were apparently ever explicitly generated—and nearly three decades passed before I noticed the remarkable behavior of the rule 30 cellular automaton.

My own work on cellular automata in 1981 emerged in part from thinking about self-gravitating systems (see page 880 ) where it seemed conceivable that there might be very basic rules quite different from those usually studied in statistical mechanics. And when I first generated pictures of the behavior of arbitrary cellular automaton rules, what struck me most was the order that emerged even from random initial conditions. But while it was immediately clear that most cellular automata do not have the kind of reversible underlying rules assumed in traditional statistical mechanics, it still seemed initially very surprising that their overall behavior could be so elaborate—and so far from the complete orderlessness one might expect on the basis of traditional ideas of entropy maximization.

Fractal dimensions [of additive cellular automata] The total number of nonzero cells in the first t rows of the pattern generated by the evolution of an additive cellular automaton with k colors and weights w (see page 952 ) from a single initial 1 can be found using g[w_, k_, t_] := Apply[Plus, Sign[NestList[Mod[ ListCorrelate[w, #, {-1, 1}, 0], k] &, {1}, t - 1]], {0, 1}] The fractal dimension of this pattern is then given by the large m limit of Log[k,g[w, k,k m + 1 ]/g[w, k, k m ]] When k is prime it turns out that this can be computed as d[w_, k_:2] := Log[k,Max[Abs[Eigenvalues[With[ {s = Length[w] - 1}, Map[Function[u, Map[Count[u, #] &, #1]], Map[Flatten[Map[Partition[Take[#, k + s - 1], s, 1] &, NestList[Mod[ListConvolve[w, #], k] &, #, k - 1]], 1] &, Map[Flatten[Map[{Table[0, {k - 1}], #} &, Append[#, 0]]] &, #]]] &[Array[IntegerDigits[#, k, s] &, k s - 1]]]]]]] For rule 90 one gets d[{1, 0, 1}] = Log[2, 3] ≃ 1.58 . For rule 150 d[{1, 1, 1}] = Log[2, 1 + √ 5 ] ≃ 1.69 . … For the other rules on page 952 : d[{1, 1, 0, 1, 0}] = Log[2, Root[4 + 2 # - 2 # 2 - 3 # 3 + # 4 &, 2]] ≃ 1.72 d[{1, 1, 0, 1, 1}] = Log[2, Root[-4 + 4 # + # 2 - 4 # 3 + # 4 &, 2]] ≃ 1.80 Other cases include (see page 870 ): d[{1, 0, 1}, k] = 1 + Log[k, (k + 1)/2] d[{1, 1, 1}, 3] = Log[3, 6] ≃ 1.63 d[{1, 1, 1}, 5] = Log[5, 19] ≃ 1.83 d[{1, 1, 1}, 7] = Log[7, Root[-27136 + 23280 # - 7288 # 2 + 1008 # 3 - 59 # 4 + # 5 & , 1]] ≃ 1.85

But an important difference is that while in the many-worlds approach, branchings are associated with possible observation or measurement events, what I suggest here is that they could be an intrinsic feature of even the very lowest-level rules for the universe.

Typically the rules imagined for each element of such systems are however immensely more complicated than for any of the simple cellular automata I consider. … These systems turn out to be essentially 1D additive cellular automata (like rule 90) with a limited number of cells (compare page 259 ). … General 1D cellular automata are related to nonlinear feedback shift registers, and some explorations of these—including ones surprisingly close to rule 30 (see page 1088 )—were made usin

Numbering scheme [for Turing machines] One can number Turing machines and get their rules using Flatten[MapIndexed[{1, -1} #2 + {0, k}  {1, 1, 2} Mod[Quotient[#1, {2k, 2, 1}], {s, k, 2}] + {1, 0, -1} &, Partition[IntegerDigits[n, 2 s k, s k], k], {2}]] The examples on page 79 have numbers 3024, 982, 925, 1971, 2506 and 1953.

The general idea of a non-deterministic system is to have rules with several possible outcomes, and then to allow each of these outcomes to be followed.

Uniqueness of patterns [in cellular automata] Starting from a particular initial condition, different rules can often yield the same pattern.