Non-periodic pattern [forced by 2D constraint] The color at position x, y in the pattern is given by a[x_, y_] := Mod[y + 1, 2] /; x + y > 0 a[x_, y_] := 0 /; Mod[x + y, 2]  1 a[x_, y_] := Mod[Floor[(x - y) 2 (x + y - 6)/4 ], 2] /; Mod[x + y, 4]  2 a[x_, y_] := 1 - Sign[Mod[x - y + 2, 2 (-x - y + 8)/4 ]] The origin of the x, y coordinates is the only freedom in this pattern.

Substitution systems in which all replacements are done that are found to fit in a left-to-right scan can be implemented as follows GSSEvolveList[rule_, s_, n_] := NestList[GSSStep[rule, #] &, s, n] GSSStep[rule_, s_] := g[rule, s, f[StringPosition[s, Map[First, rule]]]] f[{ }] = { }; f[s_] := Fold[If[Last[Last[#1]] ≥ First[#2], #1, Append[#1, #2]]&, {First[s]}, Rest[s]] g[rule_, s_, { }] := s; g[rule_, s_, pos_] := StringReplacePart[ s, Map[StringTake[s, #] &, pos] /. rule, pos] with rules given as {"ABA"  "BAAB", "BBBB"  "AA"} .

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.

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.

But with k = 3 possible elements, there are infinite nested sequences that can, such as the one produced by the substitution system {0  {0, 1, 2}, 1  {0, 2}, 2  {1}} , starting with {0} . One can find the sequences of length n that work by using Nest[DeleteCases[Flatten[Map[Table[Append[#, i - 1], {i, k}] &, #], 1], {___, x__, x__, ___}] &, {{}}, n] and the number of these grows roughly like 3 n/4 .

An example of a generalization is the quantity given for blocks of size n by h[q_, n_]:= Log[k, Sum[p[i] q , {i, k n }]]/(n(q - 1) where q = 0 yields set entropy, the limit q  1 measure entropy, and q = 2 so-called correlation entropy. For any q the maximum h[q, n]  1 occurs when all p[i]  k -n . It is always the case that h[q+1, n] ≤ h[q, n] .

For rule 30, the numbers of steps needed for each block of lengths 1 through 10 to appear at least once is {1, 2, 4, 12, 22, 24, 33, 59, 69, 113} .

This yields a chord such as Play[Evaluate[Apply[Plus, Flatten[Map[Sin[1000 # t] &, N[2 1/12 ]^Position[list, 1]]]]], {t, 0, 0.2}] A sequence of such chords can sometimes provide a useful representation of cellular automaton evolution.

But in the so-called lambda calculus of Alonzo Church from around 1930 what were instead used were pure functions such as s = Function[x, x + 1] and plus = Function[{x, y}, If[x  0, y, s[plus[x - 1, y]]]] —of just the kind now familiar from Mathematica. Note that the explicit names of ("bound") variables in such pure functions are never significant—which is why in Mathematica one can for example use s = (# + 1) & .

Implementation [of operators from axioms] Given an axiom system in the form {f[a, f[a, a]]  a, f[a, b]  f[b, a]} one can find rule numbers for the operators f[x, y] with k values for each variable that are consistent with the axiom system by using Module[{c, v}, c = Apply[Function, {v = Union[Level[axioms, {-1}]], Apply[And, axioms]}]; Select[Range[0, k k 2 - 1], With[{u = IntegerDigits[#, k, k 2 ]}, Block[{f}, f[x_, y_] := u 〚 -1 - k x - y 〛 ; Array[c, Table[k, {Length[v]}], 0, And]]] &]] For k = 4 this involves checking nearly 16 4 or 4 billion cases, though many of these can often be avoided, for example by using analogs of the so-called Davis–Putnam rules.