Pattern (a) on page 213 can be specified as {{2, -1, 2, 3}, {{0, 0, 0, 0}, {1, 1, 0, 0}, {1, 0, 0, 0}}} Given this, a complete nx by ny array filled with this pattern can be constructed from c[{d1_, d2_, d3_, d4_}, {x_, y_}] := With[{d = d1 d2 + d1 d4 + d3 d4}, Mod[{{d2 x + d4 x + d3 y, d4 x - d1 y}}/d, 1]] Fill[{dlist_, data_}, {nx_, ny_}] := Array[c[dlist, {##}] &, {nx, ny}] /. Flatten[MapIndexed[ c[dlist, Reverse[#2]]  #1 &, Reverse[data], {2}], 1]

3D class 4 [cellular automaton] rules With a cubic lattice of the type shown on page 183 , and with updating rules of the form LifeStep3D[{p_, q_, r_}, a_List] := MapThread[If[ #1  1 && p ≤ #2 ≤ q || #2  r, 1, 0]&, {a, Sum[RotateLeft[ a, {i, j, k}], {i, -1, 1}, {j, -1, 1}, {k, -1, 1}] - a}, 3] Carter Bays discovered between 1986 and 1990 the three examples {5, 7, 6} , {4, 5, 5} , and {5, 6, 5} .

Hadamard matrices Hadamard matrices are n × n matrices with elements -1 and +1, whose rows are orthogonal, so that m . … There are thought to be Hadamard matrices with every size n = 4k (and for n > 2 no other sizes are possible); the number of distinct such matrices for each k up to 7 is 1, 1, 1, 5, 3, 60, 487. The so-called Paley family of Hadamard matrices for n = 4k = p + 1 with p prime are given by PadLeft[Array[JacobiSymbol[#2 - #1, n - 1]&, {n, n} - 1] - IdentityMatrix[n - 1], {n, n}, 1] Originally introduced by Jacques Hadamard in 1893 as the matrices with elements Abs[a] ≤ 1 which attain the maximal possible determinant ± n n/2 , Hadamard matrices appear in various combinatorial problems, particularly design of exhaustive combinations of experiments and Reed–Muller error-correcting codes.

Neighbor-dependent [2D] substitution systems Given a list of individual replacement rules such as {{_, 1}, {0, 1}}  {{1, 0}, {1, 1}} , each step in the evolution shown corresponds to Flatten2D[Partition[list, {2, 2}, 1, -1] /. rule] One can consider rules in which some replacements lead to subdivision of elements but others do not. However, unlike for the 1D case, there will in general in 2D be an arbitrarily large set of different possible neighborhood configurations around any given cell.

If the rules for a one-element-dependence tag system are given in the form {2, {{0, 1}, {0, 1, 1}}} (compare page 1114 ), the initial conditions for the Turing machine are TagToMTM[{2, rule_}, init_] := With[{b = FoldList[Plus, 1, Map[Length, rule] + 1]}, Drop[Flatten[{Reverse[Flatten[{1, Map[{Map[ {1, 0, Table[0, {b 〚 # + 1 〛 }]} &, #], 1} &, rule], 1}]], 0, 0, Map[{Table[2, {b 〚 # + 1 〛 }], 3} &, init]}], -1]] surrounded by 0 's, with the head on the leftmost 2 , in state 1 . An element -1 in the tag system corresponds to halting of the Turing machine.

Fourier transforms In a typical Fourier transform, one uses basic forms such as Exp[  π r x/n] with r running from 1 to n . … Applying BitReverseOrder to this matrix yields a matrix which has an essentially nested form, and for size n = 2 s can be obtained from Nest[With[{c = BitReverseOrder[Range[0, Length[#] - 1]/ Length[#]]}, Flatten2D[MapIndexed[#1 {{1, 1}, {1, -1} (-1)^c 〚 Last[#2] 〛 } &, #, {2}]]] &, {{1}}, s] Using this structure, one obtains the so-called fast Fourier transform which operates in n Log[n] steps and is given by With[{n = Length[data]}, Fold[Flatten[Map[With[ {k = Length[#]/2}, {{1, 1}, {1, -1}} . {Take[#, k], Drop[ #, k](-1)^(Range[0, k - 1]/k)}] &, Partition[##]]] &, BitReverseOrder[data], 2^Range[Log[2, n]]]/ √ n ] (See also page 1080 .)

Using the result that (1 + x 2 m )  (1 + x) 2 m modulo 2 for any m , one then finds that the repetition period always divides the quantity p[n]=2^MultiplicativeOrder[2, n] - 1 , which in turn is at most 2 n-1 -1 . … In the case of rule 90 a similar analysis can be given, with the 1 + x used at each step replaced by 1/x + x . And now the repetition period for odd n divides q[n]=2^MultiplicativeOrder[2, n, {1,-1}] - 1 The exponent here always lies between Log[k, n] and (n-1)/2 , with the upper bound being attained only if n is prime.

A sequence of identical digits d then corresponds to the number (1 + Sqrt[4d + 1])/2 . … It appears that digits 0, 1, 2 are sufficient to represent uniquely all numbers between 1 and 2. … For random x , digits 0, 1, 2 appear to occur with limiting frequencies Sqrt[2 + d] - Sqrt[1 + d] .

[No text on this page] Minimal Boolean expression representations for the results of steps 1 through 5 in the evolution of three elementary cellular automata. … (For steps 1 through 6, the expressions involve 3, 7, 17, 41, 102 and 261 terms respectively.)

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.