1D [discrete] transitions [in cellular automata] There are no examples of the phenomenon shown here among the 256 rules with two possible colors and depending only on nearest neighbors. … An example that depends on three neighbors on each side was discovered by Peter Gacs , Georgii Kurdyumov and Leonid Levin in 1978, following work on how reliable electronic circuits can be built from unreliable components by Andrei Toom : {a1_, a2_, a3_, a4_, a5_, a6_, a7_}  If[If[a4  1, a1 + a3 + a4, a4 + a5 + a7] ≥ 2, 1, 0] The 4-color rule shown in the text is probably the clearest example available in one dimension.

Continuous generalizations [of additive rules] Functions such as Binomial[t, n] and GegenbauerC[n, -t, -1/2] can immediately be evaluated for continuous t and n . The pictures on the right below show Sin[1/2 π a[t, n]] 2 for these functions (equivalent to Mod[a[t, n], 2] for integer a[t, n] ). … The presence of poles in quantities such as GegenbauerC[1/2, -t, -1/2] leads to essential singularities in the rightmost picture below.

Difference tables and polynomials A common mathematical approach to analyzing sequences is to form a difference table by repeatedly evaluating d[list_] := Drop[list, 1] - Drop[list, -1] . If the elements of list correspond to values of a polynomial of degree n at successive integers, then Nest[d, list, n + 1] will contain only zeros. … The pictures below show the results with k = 2 (rule 60) for (a) Fibonacci[n] , (b) Thue–Morse sequence, (c) Fibonacci substitution system, (d) (Prime[n] - 1)/2 , (e) digits of π .

The number of sequences s n of length n that can actually occur is given by Apply[Plus, Flatten[MatrixPower[m, n]]] where the adjacency matrix m is given by MapAt[(1 + #) &, Table[0, {Length[net]}, {Length[net]}], Flatten[MapIndexed[{First[#2], Last[#1]} &, net, {2}], 1]] For rule 32, for example, s n turns out to be Fibonacci[n + 3] , so that for large n it is approximately GoldenRatio n . … For rule 126 after 1 step, the characteristic polynomial for m is x 3 - 2 x 2 + x - 1 , giving κ ≃ 1.755 . After 2 steps, the polynomial is x 13 - 4 x 12 + 6 x 11 - 5 x 10 + 3 x 9 - 3 x 8 + 5 x 7 - 3 x 6 - x 5 + 4 x 4 - 2 x 3 + x 2 - x + 1 giving κ ≃ 1.732 .

Simulating mobile automata Given a mobile automaton like the one from page 73 with rules in the form used on page 887 —and behavior of any complexity—the following will yield a causal-invariant substitution system that emulates it: Map[StringJoin, Map[{"AAABB", "ABABB", "ABAABB"} 〚 # + 1 〛 &, Map[Insert[# 〚 1 〛 , 2, 2]  Insert[# 〚 2, 1 〛 , 2, 2 + # 〚 2, 2 〛 ] &, rule], {2}], {2}]

An example with 8 registers and 41 instructions is: or {d[4, 40], i[5], d[3, 9], i[3], d[7, 4], d[5, 14], i[6], d[3, 3], i[7], d[6, 2], i[6], d[5, 11], d[6, 3], d[4, 35], d[6, 15], i[4], d[8, 16], d[5, 21], i[1], d[3, 1], d[5, 25], i[2], d[3, 1], i[6], d[5, 32], d[1, 28], d[3, 1], d[4, 28], i[4], d[6, 29], d[3, 1], d[5, 24], d[2, 28], d[3, 1], i[8], i[6], d[5, 36], i[6], d[3, 3], d[6, 40], d[4, 3]} Given any register machine, one first applies the function RMToRM2 from page 1114 , then takes the resulting program and initial condition and finds an initial condition for the URM using R2ToURM[prog_, init_] := Join[init, With[ {n = Length[prog]}, {1 + LE[Reverse[prog] /. {i[x_]  x, d[x_, y_]  4 + 2 n + x - 2y}], n + 1, 0, 0, 0, 0}]] For the first example on page 98 this gives {0, 0, 1471, 3, 0, 0, 0, 0} .

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}}} . … 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. … An example is {2, {{0, _}  {2, 1}, {1, _}  {0}, {2, _}  {0, 2, 1, 2}}} .

Lengths of [number] representations (a) n , (b) Floor[Log[2, n] + 1] , (c) Tr[FixedPointList[Max[0, Ceiling[Log[2, #]]] &, n + 2]] - n - 3 , (d) 2 Ceiling[Log[3, 2n + 1]] , (e) Floor[Log[GoldenRatio, √ 5 (n + 1/2)]] . … Shown on a logarithmic scale, representations (b) through (e) (given here for numbers 1 through 500) all grow roughly linearly:

Given p = Array[Prime, Length[list], PrimePi[Max[list]] + 1] or any list of integers that are all relatively prime and above Max[list] (the integers in list are assumed positive) CRT[list_, p_] := With[{m = Apply[Times, p]}, Mod[Apply[Plus, MapThread[#1 (m/#2)^EulerPhi[#2] &, {list, p}]], m]] yields a number x such that Mod[x, p]  list . Based on this LE[list_] := Module[{n = Length[list], i = Max[MapIndexed[ #1 - #2 &, PrimePi[list]]] + 1}, CRT[PadRight[ list, n + i], Join[Array[Prime[i + #] &, n], Array[Prime, i]]]] will yield a number x that can be decoded into a list of length n using essentially the so-called Gödel β function Mod[x, Prime[Rest[NestList[NestWhile[# + 1 &, # + 1, Mod[x, Prime[#]]  0 &] &, 0, n]]]]

Given three cells {a 1 , a 2 , a 3 } the rule specifies that the new value of the center cell will be Mod[a 1 + a 3 , 2] . But given {a 1 , 0, a 2 , 0, a 3 , 0} the value after one step is {Mod[a 1 + a 2 , 2], 0, Mod[a 2 + a 3 , 2], 0} and after two steps is again {Mod[a 1 + a 3 , 2], 0} . It turns out that this argument generalizes (by interspersing k - 1 0's and going for k steps) to any additive rule based on reduction modulo k (see page 952 ) so long as k is prime.