(See page 103 for a symbolic system with halting times that grow like Nest[2 # &, 0, n] .)

Non-deterministic Turing machines Generalizing rules from page 888 by making each right-hand side a list of possible outcomes, the list of configurations that can be reached after t steps is given by NTMEvolve[rule_, inits_, t_Integer] := Nest[ Union[Flatten[Map[NTMStep[rule, #]&, #], 1]]&, inits, t] NTMStep[rule_List, {s_, a_, n_}] /; 1 ≤ n ≤ Length[a] := Apply[{#1, ReplacePart[a, #2, n], n + #3}&, Replace[{s, a 〚 n 〛 }, rule], {1}]

The fact that the odd binomial coefficients form a nested geometrical pattern had apparently not been widely noticed before I emphasized it in 1982.

Applying BitReverseOrder to this matrix yields a matrix which has an essentially nested form, and for size n = 2 s can be obtained from Nest[With[{c = BitReverseOrder[Range[0, Length[#] - 1]/ Length[#]]}, Flatten2D[MapIndexed[#1 {{1, 1}, {1, -1} (-1)^c 〚 Last[#2] 〛 } &, #, {2}]]] &, {{1}}, s] Using this structure, one obtains the so-called fast Fourier transform which operates in n Log[n] steps and is given by With[{n = Length[data]}, Fold[Flatten[Map[With[ {k = Length[#]/2}, {{1, 1}, {1, -1}} .

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.

In the first 200 billion digits, the frequencies of 0 through 9 differ from 20 billion by {30841, -85289, 136978, 69393, -78309, -82947, -118485, -32406, 291044, -130820} An early approximation to π was 4 Sum[(-1) k /(2k + 1), {k, 0, m}] 30 digits were obtained with 2 Apply[Times, 2/Rest[NestList[Sqrt[2 + #]&, 0, m]]] An efficient way to compute π to n digits of precision is (# 〚 2 〛 2 /# 〚 3 〛 )& [NestWhile[Apply[Function[{a, b, c, d}, {(a + b)/2, Sqrt[a b], c - d (a - b) 2 , 2 d}], #]&, {1, 1/Sqrt[N[2, n]], 1/4, 1/4}, # 〚 2 〛 ≠ # 〚 2 〛 &]] This requires about Log[2, n] steps, or a total of roughly n Log[n] 2 operations (see page 1134 ).

For k > 1 this yields a nested pattern, analogous to those shown on page 871 . If one allows only specific numbers of objects to be taken at each step a nested pattern is again obtained.

.}] = 0 g[{1, s__}] := 1 + g[IntegerDigits[FromDigits[{s}, 2] + 1, 2]] The list of elements in the sequence up to value m is given by Flatten[Table[Table[n, {IntegerExponent[n, 2] + 1}], {n, m}]] The differences between the first 2 (2 k -1) of these elements is Nest[Replace[#, {x___}  {x, 1, x, 0}]&, {}, k] The largest n for which f[n]  m is given by 2m + 1 - DigitCount[m, 2, 1] or IntegerExponent[(2m)!… Hump m in the picture of sequence (c) shown is given by FoldList[Plus, 0, Flatten[Nest[Delete[NestList[Rest, #, Length[#] - 1], 2]&, Append[Table[1, {m}], 0], m]] - 1/2] The first 2 m elements in the sequence can also be generated in terms of reordered base 2 digit sequences by FoldList[Plus, 1, Map[Last[Last[#]]&, Sort[Table[{Length[#], Apply[Plus, #], 1 - #}& [ IntegerDigits[i, 2]], {i, 2 m }]]]] Note that the positive and negative fluctuations in sequence (f) are not completely random: although the probability for individual fluctuations in each direction seems to be the same, the probability for two positive fluctuations in a row is smaller than for two negative fluctuations in a row.

TEST 2 A cellular automaton that produces an intricate nested pattern.

The shell on the bottom right is a slightly rare specimen where something close to an explicit nested pattern can be seen.