any proof—regardless of length—exists for a specific result in a mathematical system with particular axioms.

Picture (c) has a black square wherever the maximum run of either identical or different digits has a length which is an odd number.

x_  {0, x, 0}, And[x__]  {0, 0, 1, 0, x, 1, 3, 0, 0}, Or[x__]  {0, 0, 1, 0, x, 0, 1, 3, 0}}]] and in terms of these initial conditions the cellular automaton must be run for Length[list //. {0, x__}  {x}] - 1 steps in order to find the result.

In analogy with page 796 the picture below shows when different strings with lengths up to 10 are reached in the evolution of the system.

Probably the simplest is a statement shown to be unprovable in Peano arithmetic by Laurence Kirby and Jeff Paris in 1982: that certain sequences g[n] defined by Reuben Goodstein in 1944 are of limited length for all n , where g[n_] := Map[First, NestWhileList[ {f[#] - 1, Last[#] + 1} &, {n, 3}, First[#] > 0 &]] f[{0, _}] = 0; f[{n_, k_}] := Apply[Plus, MapIndexed[#1 k^f[{#2 〚 1 〛 - 1, k}] &, Reverse[IntegerDigits[n, k - 1]]]] As in the pictures below, g[1] is {1, 0} , g[2] is {2, 2, 1, 0} and g[3] is {3, 3, 3, 2, 1, 0} . g[4] increases quadratically for a long time, with only element 3 × 2 402653211 - 2 finally being 0. And the point is that in a sense Length[g[n]] grows too quickly for its finiteness to be provable in general in Peano arithmetic. … That this sequence terminates for all n is then provable in set theory, but not Peano arithmetic—and in effect Length[g[n]] must grow like  [ ε 0 ][n] .)

But as we discussed, there is in most practical situations a limit on the lengths of sequences whose randomness can realistically be attributed to such a mechanism.

The pictures at the top of the next page show the results of computing the frequencies of different blocks in various sequences, and in each case each successive row shows results for all possible blocks of a given length.

Symbolic systems [emulating cellular automata] Given the rules for an elementary cellular automaton in the form used on page 867 (with {0, 0, 0}  0 ), the following will construct a symbolic system which emulates it: Flatten[{Array[(p[x_][#1][#2][#3]  p[x[{##} /. rules]][#2][#3]) &, {2, 2, 2}, 0] /. {0  p, 1  q}, {r[x_]  p[r[p][p]][x], p[x_][p][p][r]  x[p][p][r]}}] The initial condition for the symbolic system is given by Fold[#1[#2] &, r[p][p], init /. {0  p, 1  q}][p][p][r] Step t in the cellular automaton corresponds to step t (t + Length[init] + 3) in the symbolic system.

Starting at n = 44 , there is also a length 12 cycle.

With this setup, each step then corresponds to LifeStep[list_] := With[{p=Flatten[Array[List, {3, 3}, -1], 1]}, With[{u = Split[Sort[Flatten[Outer[Plus, list, p, 1], 1]]]}, Union[Cases[u, {x_, _, _}  x], Intersection[Cases[u, {x_, _, _, _}  x], list]]]] (A still more efficient implementation is based on finding runs of length 3 and 4 in Sort[u] .)