Nested initial conditions [in cellular automata] The pictures below show patterns generated by rule 90 starting from the nested sequences on page 83 .

The most common of these are nested patterns, like those on the next page . And it turns out that although 24 rules in all yield such nested patterns, there are only three fundamentally different forms that occur. … But as the pictures on the next page show, other nested forms are also possible.

Ackermann functions A convenient example is f[1, n_] := n; f[m_, 1] := f[m - 1, 2] f[m_, n_] := f[m - 1, f[m, n - 1] + 1] The original function constructed by Wilhelm Ackermann around 1926 is essentially f[1, x_, y_] := x + y; f[m_, x_, y_] := Nest[f[m - 1, x, #] &, x, y - 1] or f[m_, x_, y_]:= Nest[Function[z, Nest[#, x, z - 1]] &, x + # &, m - 1][y] For successive m (following the so-called Grzegorczyk hierarchy) this is x + y , x y , x y , Nest[x # &, 1, y] , .... f[4, x, y] can also be written Array[x &, y, 1, Power] and is sometimes called tetration and denoted x ↑ ↑ y .

Indeed, just like patterns produced by one-dimensional substitution systems on page 83 , all the patterns shown here ultimately have a simple nested structure. … The pattern generated has a nested form.

for the substitution system that generates a particular nested pattern, and from these construct a procedure for finding the color of a square in the pattern given its position. … Procedures for determining the color of a square at a given position in various nested patterns.

Repetitive patterns are common and some nested patterns are seen, but the more complicated kinds of patterns discussed in this chapter do not ever appear to have been used.

Properties [of example symbolic system] All initial conditions eventually evolve to expressions of the form Nest[ ℯ , ℯ , m] , which then remain fixed. … The maximum is Nest[2 # &, 0, n] (compare page 906 ), achieved for initial conditions of the form Nest[#[ ℯ ]&, ℯ , n] . … For initial conditions of size n , this occurs after at most Sum[Nest[2 # &, 0, i] - 1, {i, n}] + 1 steps.

The pictures below show an example in which random class 3 behavior is obtained when the initial conditions are random, but where the pattern produced by starting with a single black cell has just a simple nested form. … But with the specific initial condition shown on the right, a simple nested pattern is produced.

And indeed in Examples of nested patterns created by following the two-dimensional substitution rules shown. Except for the last examples on each row, it is remarkably difficult to recognize the nested structure in these patterns by eye, even with quite careful scrutiny.

But even in this example, there is still a highly regular nested structure. … A register machine that shows nested rather than strictly repetitive behavior.