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