And while some generalization has occurred in the types of systems being studied, it has usually been much limited by the desire to maintain the validity of some set of theorems (see page 793 ).

The rule on page 82 can then be given simply as s[1, 0]  s[0, 1, 0] while the rule on page 85 becomes {s[0, 1, 0]  s[0, 0, 1], s[0]  s[0, 1, 0]} The Flat attribute of s makes these rules apply not only for example to the whole sequence s[1, 0, 1, 0] but also to any subsequence such as s[1, 0] .

For 1D elementary rules the list is {{-1}, {0}, {1}} , while for 2D 5-neighbor rules it is {{-1, 0}, {0, -1}, {0, 0}, {0, 1}, {1, 0}} .

In the first case shown, this number varies like (1/a) 1 for small a , while in the last case, it varies like (1/a) 2 .

But while there are a few other initial conditions for which differences can die out after several steps most forms of averaging will say that the majority of initial conditions lead to growing patterns of differences.

If we then assume perfect underlying randomness, the density at a particular position must be given in terms of the densities at neighboring positions on the previous step by f[x, t + dt]  p 1 f[x - dx, t] + p 2 f[x, t] + p 3 f[x + dx, t] Density conservation implies that p 1 + p 2 + p 3  1 , while left-right symmetry implies p 1  p 3 .

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. … But while it is known that in Peano arithmetic κ = ε 0 , quite how to describe the value of κ for, say, set theory remains unknown.

Note that while the complement of a recursive set is always recursive, the complement of a recursively enumerable set may not be recursively enumerable.

For while they make it easy at a formal level to check that certain statements are true, they do little at a more conceptual level to illuminate why this might be so.

In example (e), the frequency of 1's is again about 3/4, but now {0, 0} occurs with frequency 0.05, {1, 1} occurs with frequency 0.55, while {0, 0, 0} and {0, 1, 0} cannot occur.