Density in rule 90 From the superposition principle above and the number of black cells at step t in a pattern starting from a single black cell (see page 870 ) one can compute the density after t steps in the evolution of rule 90 with initial conditions of density p to be (see also page 602 ) 1/2 (1 - (1 - 2 p)^(2^DigitCount[t,2,1]))

The picture below shows the structures one finds by explicitly testing the first two billion possible initial conditions for the code 357 cellular automaton from page 282 . … Persistent structures in the code 357 cellular automaton from page 282 obtained by testing the first two billion possible initial conditions. This cellular automaton allows three possible colors for each cell; the initial conditions thus correspond to the base 3 digits of the numbers given.

The number of cells that are not white on row t in this case is given by Apply[Times, 1 + IntegerDigits[t, k]] . … A related result is that IntegerExponent[Binomial[t, n], k] is given by the number of borrows in the base k subtraction of n from t . Mod[Binomial[t, n], k] is given for prime k by With[{d = Ceiling[Log[k, Max[t, n] + 1]]}, Mod[Apply[Times, Apply[Binomial, Transpose[ {IntegerDigits[t, k, d] , IntegerDigits[n, k, d] }], {1}]], k]] The patterns obtained for any k are nested.

Lyapunov exponents The number of new digits that are affected at each step by a small change in initial conditions gives the so-called Lyapunov exponent λ for the evolution. After t steps, the difference in size resulting from the change in initial conditions will be multiplied by approximately 2 λ t —at least until this difference is of order 1.

An explicit table of 40,000 random digits was created in 1927 by Leonard Tippett from details of census data. And in 1938 further tables were generated by Ronald Fisher from digits of logarithms. Several tables based on physical processes were produced, with the RAND Corporation in 1955 publishing a table of a million random digits obtained from an electronic roulette wheel.

Implementation [of 2D cellular automata] An n × n array of white squares with a single black square in the middle can be generated by PadLeft[{{1}}, {n, n}, 0, Floor[{n, n}/2]] For the 5-neighbor rules introduced on page 170 each step can be implemented by CAStep[rule_, a_] := Map[rule 〚 10 - # 〛 &, ListConvolve[{{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}, a, 2], {2}] where rule is obtained from the code number by IntegerDigits[code, 2, 10] . For the 9-neighbor rules introduced on page 177 CAStep[rule_, a_] := Map[rule 〚 18 - # 〛 &, ListConvolve[{{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}, a, 2], {2}] where rule is given by IntegerDigits[code, 2, 18] . In d dimensions with k colors, 5-neighbor rules generalize to (2d + 1) -neighbor rules, with CAStep[{rule_, d_}, a_] := Map[rule 〚 -1 - # 〛 &, a + k AxesTotal[a, d], {d}] AxesTotal[a_, d_] := Apply[Plus, Map[RotateLeft[a, #] + RotateRight[a, #]&, IdentityMatrix[d]]] with rule given by IntegerDigits[code, k, k(2d(k - 1) + 1)] . 9-neighbor rules generalize to 3 d -neighbor rules, with CAStep[{rule_, d_}, a_] := Map[rule 〚 -1 - # 〛 &, a + k FullTotal[a, d], {d}] FullTotal[a_, d_] := Array[RotateLeft[a, {##}] &, Table[3, {d}], -1, Plus] - a with rule given by IntegerDigits[code, k, k((3 d - 1)(k - 1) + 1)] .

Sierpiński pattern Other ways to generate step n of the pattern shown here in various orientations include: • Mod[Array[Binomial, {2, 2} n , 0], 2] (see pages 611 and 870 ) • 1 - Sign[Array[BitAnd, {2, 2} n , 0]] (see pages 608 and 871 ) • NestList[Mod[RotateLeft[#] + #, 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • NestList[Mod[ListConvolve[{1, 1}, #, -1], 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • IntegerDigits[NestList[BitXor[2#, #] &, 1, 2 n - 1], 2, 2 n ] (see page 906 ) • NestList[Mod[Rest[FoldList[Plus, 0, #]], 2] &, Table[1, {2 n }], 2 n - 1] (see page 1034 ) • Table[PadRight[ Mod[CoefficientList[(1 + x) t - 1 , x], 2], 2 n - 1], {t, 2 n }] (see pages 870 and 951 ) • Reverse[Mod[CoefficientList[Series[1/(1 - (1 + x)y), {x, 0, 2 n - 1}, {y, 0, 2 n - 1}], {x, y}], 2]] (see page 1091 ) • Nest[Apply[Join, MapThread[ Join, {{#, #}, {0 #, #}}, 2]] &, {{1}}, n] (compare page 1073 ) The positions of black squares can be found from: • Nest[Flatten[2# /. … (OddQ[Length[#]] &), {2}] (see page 358 ) • Flatten[Table[Map[{t, #} &, Fold[Flatten[{#1, #1 + #2}] &, 0, Flatten[2^(Position[ Reverse[IntegerDigits[t, 2]], 1] - 1)]]], {t, 2 n - 1}], 1] (see page 870 ) • Map[Map[FromDigits[#, 2] &, Transpose[Partition[#, 2]]] &, Position[Nest[{{#, #}, {#}} &, 1, n], 1] - 1] (see page 509 ) A formatting hack giving the same visual pattern is DisplayForm[Nest[SubsuperscriptBox[#, #, #] &, "1", n]]

One might imagine that it should be possible to set up a function f[i, n] which if given successive integers i would give the n th base 2 digit in every possible real number. But what about the number whose n th digit is 1 - f[n, n] ? … And the only possible conclusion from this is that f[i, n] cannot in fact be implemented as a program that always halts—thus demonstrating that the computable real numbers cannot explicitly be enumerated.

The question of whether complex behavior could occur in cellular automata was occasionally raised, but on the basis of intuition from engineering it was generally assumed that to get any substantial complexity, one would have to have very complicated underlying rules. … Another early sign of the phenomenon of complexity could have been seen in the digit sequence of a number like π ≃ 3.141592653… (see page 136 ). By the 1700s more than a hundred digits of π had been computed, and they appeared quite random.

Much as for integers, finite lists of real numbers can be encoded as single real numbers—using for example roughly FromDigits[Flatten[Transpose[RealDigits[list]]]] —so that the number of such lists is 2 ℵ 0 . … (The function σ above can for example be used to specify the order in which to sample elements in RealDigits[list] ). … But infinite configurations of cells are like digit sequences of real numbers (as discussed on page 869 they correspond more precisely to elements in a Cantor set), so the number of them is 2 ℵ 0 .