Search NKS | Online
41 - 50 of 93 for NestList
![](/common/images/search/spacer.gif)
If h is rational, the sequence is repetitive, while if h is a quadratic irrational, it is nested. Given a sequence of length n , an approximation to h can be reconstructed using
Max[MapIndexed[#1/First[#2] &, FoldList[Plus, First[list], Rest[list]]]]
The fractional part of the result obtained is always an element of the Farey sequence
Union[Flatten[Table[a/b, {b, n}, {a, 0, b}]]]
(See also pages 892 , 932 and 1084 .)
To emulate cellular automaton evolution one starts by encoding a list of cell values by the single combinator
p[num[Length[list]]][ Fold[p[Nest[s, k, #2]][#1] &, p[k][k], list]] //. crules
where
num[n_] := Nest[inc, s[k], n]
inc = s[s[k[s]][k]]
One can recover the original list by using
Extract[expr, Map[Reverse[IntegerDigits[#, 2]] &, 3 + 59(16^Range[Depth[expr[s[k]][s][k] //. crules] - 1, 1, -1] - 1)/ 15)]]/. … With this setup t steps of evolution are given simply by Nest[w, init, t] .
Often these can be thought of as one-way versions of axioms for operator systems (see page 1172 ), but applied only once per step (as /. does), rather than in all possible ways (as in a multiway system)—so that the evolution is just given by NestList[#/.rule &, init, t] .
One-element-dependence tag systems [emulating TMs]
Writing the rule {3, {{0, _, _} {0, 0}, {1, _, _} {1, 1, 0, 1}}} from page 895 as {3, {0 {0, 0}, 1 {1, 1, 0, 1}}} the evolution of a tag system that depends only on its first element is obtained from
TS1EvolveList[rule_, init_, t_] := NestList[TS1Step[rule, #] &, init, t]
TS1Step[{n_, subs_}, {}] = {}
TS1Step[{n_, subs_}, list_] := Drop[Join[list, First[list] /. subs], n]
Given a Turing machine in the form used on page 888 the following will construct a tag system that emulates it:
TMToTS1[rules_] := {2, Union[Flatten[rules /.
One can take the original stem to extend from the point -1 to 0; the rule is then specified by the list b of complex numbers corresponding to the positions of the new tip obtained after one step. And after n steps the positions of all tips generated are given simply by
Nest[Flatten[Outer[Times, 1 + #, b]] &, {0}, n]
In general a length n list can require about n steps. But if the list contains a nested sequence, say generated using a substitution system, then about Log[n] steps should be sufficient.
Starting with an ordinary base 2 digit sequence, one prepends a unary specification of its length, then a specification of that length specification, and so on:
(Flatten[{Sign[-Range[1 - Length[#], 0]], #}] &)[ Map[Rest, IntegerDigits[Rest[Reverse[NestWhileList[ Floor[Log[2, #] &, n + 1, # > 1 &]]],2]]]
(d) Binary-coded base 3. … Apply[Take, RealDigits[(N[#, N[Log[10, #] + 3]] &)[ n √ 5 /GoldenRatio 2 + 1/2], GoldenRatio]]
The representations of all the first Fibonacci[n] - 1 numbers can be obtained from (the version in the main text has Rest[RotateLeft[Join[#, {0, 1}]]] & applied)
Apply[Join, Map[Last, NestList[{# 〚 2 〛 ], Join[Map[Join[{1, 0}, Rest[#]] & , # 〚 2 〛 ], Map[Join[{1, 0}, #] &, # 〚 1 〛 ]]} &, {{}, {{1}}}, n-3]]]
Iterated run-length encoding
Starting say with {1} consider repeatedly replacing list by (see page 1070 )
Flatten[Map[{Length[#], First[#]} &, Split[list]]]
The resulting sequences contain only the numbers 1, 2 and 3, but otherwise at first appear fairly random. … The system thus in the end produces patterns that are purely nested, though formed from rather complicated elements.
In general, the pattern produced by evolution for t steps is given by
NestList[ Inner[f, Prepend[#, 0], Append[#, 0], List] &, {a}, t]
so that the first few steps yield
{a},
{f[0, a], f[a, 0]},
{f[0, f[0, a]], f[f[0, a], f[a, 0]], f[f[a, 0], 0]},
{f[0, f[0, f[0, a]]], f[f[0, f[0, a]], f[f[0, a], f[a, 0]]], f[f[f[0, a], f[a, 0]], f[f[a, 0], 0]], f[f[f[a, 0], 0], 0]}
If f is Flat , however, then the last two lines here become
{f[0, 0, a], f[0, a, a, 0], f[a, 0, 0]},
{f[0, 0, 0, a], f[0, 0, a, 0, a, a, 0], f[0, a, a, 0, a, 0, 0], f[a, 0, 0, 0]}
and in general the number of a 's that appear in a particular element is given as in Pascal's triangle by a binomial coefficient. … And from the discussion on page 952 this means that any rule that shows generalized additivity must always yield a nested pattern. But if f is not commutative, then even if it is associative, non-nested patterns can be produced.
With the state of a 2-color tag system encoded as an integer according to FromDigits[Reverse[list] + 1, 3] the following takes the rule for any such tag system (in the first form from page 894 ) and yields a primitive recursive function that emulates a single step in its evolution:
TSToPR[{n_, rule_}] := Fold[Apply[c, Flatten[{#1, Array[p, #
2], c[r[z, c[r[p[1], s], c[r[z, p[2]], c[r[z, r[c[s, z], c[r[c[s,
c[s, z]], z], p[2]]]], p[2]]], p[1]]], p[#2]]}]] & , c[c[r[p[1],
s], p[1], c[r[p[1], r[z, c[s, c[s, s]]]], c[c[r[z, c[r[p[1], s],
c[r[z, c[s, z]], c[r[p[1], r[z, c[r[p[1], s], c[r[z, p[2]], c[
r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[2]]], p[1]]]],
p[2], p[3]]], p[1]]], p[1], p[1]], p[1]], p[2]]], p[n + 1],
MapIndexed[c[r[z, c[r[p[1], p[4]], p[2], p[3], p[4]]], c[r[z,
r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[Length[#2] + 1]], #
1 〚 1 〛 , #1 〚 2 〛 ] & , Nest[Partition[#1, 2] & , Table[Nest[c[s, #] &
z, FromDigits[Reverse[IntegerDigits[i, 2, n] /. rule] + 1, 3]],
{i, 0, 2 n - 1}], n - 1], {0, n - 1}]], Range[n, 1, -1]]
(For tag system (a) from page 94 this yields a primitive recursive function of size 325.) The result of t steps of evolution is in general given in terms of this function f by Nest[f, init, t] , or equivalently r[p[1], f][t, init] . … Note that the same basic approach can be used to emulate Turing machines with recursive functions; the Turing machine configuration {s, list, n} can be encoded by an integer such as
2^FromDigits[Reverse[Take[list, n - 1]]] 3^FromDigits[Take[list, {n + 1, -1}]] 5^list 〚 n 〛 7 s
![](/common/images/search/spacer.gif)