(Note that if an axiom system does manage to reproduce logic in full then as indicated on page 814 its consequences can always be derived by proofs of limited length, if nothing else by using truth tables.)

The following generates explicit lists of n -input Boolean functions requiring successively larger numbers of Nand operations: Map[FromDigits[#, 2] &, NestWhile[Append[#, Complement[Flatten[Table[Outer[1 - Times[##] &, # 〚 i 〛 , # 〚 -i 〛 , 1], {i, Length[#]}], 2], Flatten[#, 1]]] &, {1 - Transpose[IntegerDigits[Range[2 n ] - 1, 2, n]]}, Length[Flatten[#, 1]] < 2 2 n &], {2}] The results for 2-step cellular automaton evolution in the main text were found by a recursive procedure.

In each case, the use of Partition could be replaced by Transpose[Table[RotateLeft[a, i], {i, -r, r}]] .

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 .

In the mid-1800s, for example, following the ideas of Charles Babbage , so-called difference engines were used to automatically compute and print tables of values of polynomials. … The focus of the ENIAC was on numerical computation, originally for creating ballistics tables.

(Such operator representations are a rough analog for multiway systems of truth tables.)

The first n elements can be found efficiently using Module[{a = 1}, Table[First[IntegerDigits[ a, a = BitXor[a, BitOr[2a, 4a]]; 2, i]], {i, n}]] The sequence does not repeat in at least its first million steps, and I would amazed if it ever repeats, but as of now I know of no rigorous proof of this. ( Erica Jen showed in 1986 that no pair of columns can ever repeat, and the arguments on page 1087 suggest that neither can the center column together with occasional neighboring cells.)

Other significant publications of mine providing relevant summaries were (the dates here are for actual publication—sometimes close to writing, but sometimes long delayed): • "Computers in science and mathematics" (September 1984) ( Scientific American article about foundations of the computational approach to science and mathematics) • "Cellular automata as models of complexity" (October 1984) ( Nature article introducing cellular automata) • "Geometry of binomial coefficients" (November 1984) (additive cellular automata and nested patterns) • "Twenty problems in the theory of cellular automata" (1985) (a list of unsolved problems to attack—most now finally resolved in this book) • "Tables of cellular automaton properties" (June 1986) (features of elementary cellular automata) • "Cryptography with cellular automata" (1986) (using rule 30 as a cryptosystem) • "Complex systems theory" (1988) (1984 speech suggesting the research direction for the new Santa Fe Institute)

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 .

And in general, the probabilities for all 8 possible combinations of 3 cells are given by probs = Apply[Times, Table[IntegerDigits[8 - i, 2, 3], {i, 8}] /. {1  p, 0  1 - p}, {1}] In terms of these probabilities the density at the next step in the evolution of cellular automaton with rule number m is then given by Simplify[probs .