There are some patterns that attain a definite size, then repeat forever, as shown below, others that continue to grow, but have a repetitive form, as at the top of the facing page , and still others that produce nested or fractal patterns, as at the bottom of the page .

For as we discussed on page 83 , neighbor-independent substitution systems can generate only patterns that are either repetitive or nested—so they can never yield the more complicated patterns that are, for example, needed to emulate rule 30.

Starting in the 1960s it began to be realized that fast algorithms could be based on nested or recursive processes, and such algorithms became increasingly popular in the 1980s. … An example is the algorithm of Anatolii Karatsuba from 1961 for finding products of n -digit numbers (with n = 2 s ) by operating on their digits in the nested pattern of page 608 (see also page 1093 ) according to First[f[IntegerDigits[x, 2, n], IntegerDigits[y, 2, n], n/2]] f[x_, y_, n_] := If[n < 1, x y, g[Partition[x, n], Partition[y, n], n]] g[{x1_, x0_}, {y1_, y0_}, n_] := With[{z1 = f[x1, y1, n/2], z0 = f[x0, y0, n/2]}, z1 2 2n + (f[x0 + x1, y0 + y1, n/2] - z1 - z0)2 n + z0] Other examples include the fast Fourier transform (page 1074 ) and related algorithms for ListConvolve , the quicksort algorithm for Sort , and many algorithms in fields such as computational geometry.

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] .

But if the list contains a nested sequence, say generated using a substitution system, then about Log[n] steps should be sufficient.

Generating functions [for nested patterns] A convenient algebraic way to describe a sequence of numbers a[n] is to give a generating function Sum[a[n] x n , {n, 0, ∞ }] . 1/(1 - x) thus corresponds to the constant sequence and 1/(1 - x - x 2 ) to the Fibonacci sequence (see page 890 ).

Both of these sets yield nested patterns.

Diffusion-limited aggregation (DLA) While many 2D cellular automata produce intricate nested shapes, the aggregation models shown here seem to tend to simple limiting shapes.

A common feature of phase transitions is that right at the transition point, there is competition between both phases, and some kind of nested structure is typically formed, as discussed on page 273 and above. The overall form and fractal dimension of this nested structure is typically independent of small-scale features of the system, making it fairly universal, and amenable to analysis using the renormalization group approach (see page 955 ).

For Turing machines with two or three possible states, only repetitive and nested behavior normally seem to occur.