To go further one begins by defining an analog to the Ackermann function of page 906 :  [1][n_] = 2n;  [s_][n_] := Nest[  [s - 1], 1, n]  [2][n] is then 2 n ,  [3] is iterated power, and so on. … And in direct analogy to the transfinite numbers discussed above one can then in principle form a hierarchy of functions using operations like  [ ω + s][n_]:=Nest[  [ ω + s - 1], 1, n] together with diagonalization at limit ordinals.

The picture below shows the fraction of 1's that appear on successive rows. The fraction seems to tend to 1/2. … (For multiplier m in base k , the relative frequencies of pairs {i, j} are given by Quotient[a i - j - 1 + m, k] - Quotient[m i - j - 1, k] .)

Thus, for example, the growth rate for {"A"  "AA", "AB"  "BA", "BA"  "AB"} is t n + 1 , where n is the number of initial B 's. … The rule for the system can then be stated in terms of a difference vector—which for {"AB"  "BBB", "ABB"  "AAAB"} is {{-1, 2}, {2, -1}} . Given a list of string specifications, a step in the evolution of the multiway system corresponds to Select[Union[Flatten[Outer[Plus, diff, list, 1], 1]], Abs[#]  # &]

The number of steps before a machine with given rule halts can be computed from (see page 888 ) Module[{s = 1, a, i = 1, d}, a[_] = 0; MapIndexed[a[#2 〚 1 〛 ] = #1 &, Reverse[IntegerDigits[x, 2]]]; Do[{s, a[i], d} = {s, a[i]} /. rule; i -= d; If[i  0, Return[t]], {t, tmax}]] Of the 4096 Turing machines with s = 2 , k = 2 , 748 never halt, 3348 sometimes halt and 1683 always halt. (The most rarely halting are ones like machine 3112 that halt only when x = 4j - 1 .) … Machine 1447 (example (e)) computes the function which takes the digit sequence of x and replaces its first 3 + IntegerExponent[x + 1, 2] 0's by 1's.

These are related to the autocorrelation function according to Fourier[list] 2  Fourier[ListConvolve[list, list, {1, 1}]]/Sqrt[Length[list]] (See also page 1074 .)

Trapezoidal primes If one lays out n objects in an a × b rectangular array, then n is prime if either a or b must be 1 . Following the Pythagorean idea of figurate numbers one can instead consider laying out objects in an array of b rows, containing successively a , a - 1 , ... objects.

Algebraic forms [for cellular automaton rules] The rules here can be expressed in algebraic terms (see page 869 ) as follows: • Rule 30: Mod[p + q + r + q r, 2] • Rule 45: Mod[1 + p + r + q r, 2] • Rule 73: Mod[1 + p + q + r + p r + p q r, 2]

Sequence equations Another way to set up 1D systems based on constraints is by having equations like Flatten[{x, 1, x, 0, y}] === Flatten[{0, y, 0, y, x}] , where each variable stands for a list.

.) • Are there infinitely many primes of the form n 2 + 1 ? … (See page 1162 .) • Are there infinitely many primes of the form 2 2 n + 1 ? (Fermat primes; 1844) • Are there no solutions to x m - y n  1 other than 3 2 - 2 3  1 ?

Evaluation chains The idea of building up computations like 1 + 1 + 1 + … from partial results has existed since Egyptian times.