Search NKS | Online
141 - 150 of 310 for Nest
![](/common/images/search/spacer.gif)
(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.
![](/common/images/search/spacer.gif)