Classifying Nestedness
in Cellular Automata

Eric Rowland

Rutgers University

Introduction

The human visual system is very good at recognizing global nested structure, but it doesn't really let us understand it.

Let us take a formal approach to studying nested structure in cellular automata, ultimately with the goal of proving theorems.  Since nestedness implies a certain level of computational reducibility, we actually have a hope of succeeding.

Questions:
Where does nested structure arise?
In what ways can we classify types of nested structure?

Global nested structure:

Local nested structure:

There is perhaps a third type of nested structure, in which nestedness is global to the automaton but the automaton grows in size very slowly.  These might be thought of as "class 4" nested structures, and the nestedness is unstable with respect to initial conditions.

The recurring structures in all three types arise because the diagonals are periodic...

...and the diagonals are periodic because each of these rules is additive in some position.

Nestedness implies some computational reducibility.  But I think that determining precisely how much reducibility would be the subject of a large research program.

In 1852, Kummer showed that IntegerExponent[Binomial[t, m], 2] is the number of carries when adding m and t - m in binary.  Since rule 90 is Pascal's triangle modulo 2, this lets one compute a cell on row t of rule 90 in O(log t) time (as opposed to the O((t^2)) time taken by the automaton).

Additivity

An additive cellular automaton has the property that superimposing ("adding") the initial conditions simply produces a superposition of the evaluations.  In rule 150, triples of cells are added modulo 2.

As discussed on page 953 of the NKS book, every k-element commutative monoid gives an additive cellular automaton for each range size.  Moreover, weighting each position by a function that distributes over the monoid operation gives us "generalized additive" cellular automata.

Let's systematically study generalized additive rules, focusing on 2-color rules begun from a single black cell.

There are two inequivalent commutative monoids with 2 elements:

These give eight generalized additive 2-color rules depending on 2 cells:

All of these are global nested, but they aren't all interesting.

Let's eliminate uniform regions (lines, triangles, and squares).
(For higher range rules, we'll also eliminate left-right reflections.)

There are five interesting generalized additive 2-color rules depending on 3 cells:

Generalized additive 2-color rules depending on 4 cells:

Let's jump up to rules depending on 6 cells and eliminate duplicate patterns.
Also, let's only take black patterns on white backgrounds.  There are 32.

But some are horizontal shifts of others.  By counting how many black cells appear on each row, we can detect these and eliminate them also.  We are left with 17 distinct patterns.

As we allow larger dependency range, we will get more new nested patterns.
It would be really nice to understand them all.

Fractal Dimensions

It is natural to look at fractal dimensions.

The fractal dimension of a self-similar object is \(TraditionalForm\`d = \(\(log\_f\) 
            c = \(log(number\ of\ copies\ to\ cover)\)\/\(log(linear\ magnification\ factor)\)\)\).

A line segment has (fractal) dimension 1, and a square has (fractal) dimension 2, so fractal dimensions extend the usual notion of dimension.

The Cantor set has fractal dimension (Subscript[log, 3]) 2.

The number of times a given feature appears with size x is asymptotically (x^(-d)) as x -> 0.

What is the fractal dimension of rule 90?

For a cellular automaton, the fractal dimension can be computed in a more systematic way.  Let B(t) be the number of black cells up to row t.  Then B(t)·c = B(f·t).  Therefore B(t) ∼ (t^(-(Subscript[log, f])(1/c))) = 
        (t^d), so d = (lim_(t -> ∞)) (Subscript[log, t]) 
          B(t).

The following is a plot of (Subscript[log, t]) B(t) for rule 90.

Because the convergence is so slow, it is difficult to guess the limiting behavior of this plot.

Let's pick some sample points, say powers of 2, and count B(t) at these points.

Accumulate[
      Total /@ PartitionAt[
          Total /@ CellularAutomaton[{6, 2, (1/2)}, {{1}, 0}, (2^11) - 1], 
          (2^Range)[0, 11 - 1]]]

Limit[Log[(2^n), (3^n)], n -> ∞]

Thus rule 90 has fractal dimension (Subscript[log, 2]) 3 (once we show that the limit exists).

N[Log[2, 3]]

What about rule 150?

Sampling B(t) at powers of 2 gives the following sequence.

If we notice that the terms satisfy a second-order linear recurrence, then we can obtain an explicit formula.

Table[(2^n) Fibonacci[n + 2], {n, 0, 11}]

Taking a limit gives the fractal dimension (again, once we know that it exists).

Limit[
      Log[(2^n), 
        (1/10) ((5 + 3 (Sqrt[5])) (((1 + (Sqrt[5])))^n) + (5 - 
                    3 (Sqrt[5])) (((1 - (Sqrt[5])))^n))], 
      n -> ∞]

Among rules depending on 4 cells, two new patterns appear.

Rule 27030 looks like rule 90, but its scale is different.

Nevertheless, we might expect their fractal dimensions to be the same.

And in fact they are (despite their plots).

Table[
      5 (3^(n - 1)) - 2 (3^((n/2) - 1)) Boole[EvenQ[n]], {n, 0, 
        11}]

{Limit[Log[5 (3^(n - 1))]/Log[(2^n)], n -> ∞], 
      Limit[Log[5 (3^(n - 1)) - 2 (3^((n/2) - 1))]/Log[(2^n)], 
        n -> ∞]}

Rule 39270 is a different story.  Its fractal dimension was not known until quite recently.  Judging by the plot, it is about 1.73.

It can be somewhat difficult to guess an expression for B((2^n)).
The 2-color rule number 7378753924479149670 depending on 6 cells again resembles rule 90.

But B((2^n)) is given by the following.

Table[
        (3^n) 11 ((1/5) + ((((11/(3^4))))^Floor)[(1/4) (n - Range[4])] . {-(1/(3 5 7)), -(1/((3^2) 7)), (1/(5 (3^3))), 
                  (1/((3^2) 5 7))}), {n, 0, 11}]

k-regular sequences

In cases when the resulting sequence B((2^n)) isn't obvious, we may need to take things apart a little more.
Let b(t) be the number of black cells on row t.

It turns out that b(t) is more amenable to systematic study than B(t)=(∑_(i = 0)^t) b(i).
(But this sum isn't always easy to evaluate.)

How many black cells are there in row t of rule 90?

Total /@ CellularAutomaton[{6, 2, (1/2)}, {{1}, 0}, 31]

Total /@ CellularAutomaton[{6, 2, (1/2)}, {{1}, 0}, 31]

Splitting this sequence into its "every other term" halves reveals some structure.

Column[Unriffle[%]]

Writing t in binary helps one guess the closed form.

Total /@ CellularAutomaton[{6, 2, (1/2)}, {{1}, 0}, 31]

Table[(2^DigitCount)[t, 2, 1], {t, 0, 31}]

This is an example of a 2-regular sequence:  Taking every other term produces a sequence which doesn't differ substantially from the first.

Formally, a sequence a(n) of integers is k-regular if the ℤ-module generated by the sequences a((k^e) n + r) for e ≥ 0, 0 ≤ r < e is finitely generated.
The rank (number of generators) of this ℤ-module can be thought of as a measure of the complexity of the sequence.

The rank of b(t) for rule 90 is 1, since the sequence itself generates the ℤ-module.

For rule 150, the sequence obtained is also 2-regular:

Total /@ CellularAutomaton[{150, 2, 1}, {{1}, 0}, 31]

Column[
      Unriffle[Total /@ CellularAutomaton[{150, 2, 1}, {{1}, 0}, 63], 
        4]]

In this case, the structure is somewhat more complex.
The ℤ-module has rank 2, and b(t) is given by a product of 2 × 2 matrices (depending on the binary digits of t).

Table[({0, 1} . 
          Dot @@ ({{0, 1}, {2 #1, 1}} &) /@ 
              Reverse[IntegerDigits[n, 2]] . {1, 1}), {n, 0, 
        31}]

Summing this type of function is not something with which traditional mathematics has typically been concerned.

Returning to rule 39270...

Total /@ 
      CellularAutomaton[{39270, 2, (3/2)}, {{1}, 0}, (2^6) - 1]

Presumably this sequence is given by a product of 3 × 3 matrices, but I have yet to figure out what they are.

Questions for future investigation

Is the function b(t) that counts the number of cells of a certain color on step t of a k-color generalized additive cellular automaton always k-regular?
Are there any other (nontrivial) automata for which b(t) is k-regular?
What are the closed forms of these sequences in general?

What values can the fractal dimension of a k-color global nested cellular automaton take?
In particular, is (k^d) always algebraic?
Can we hope for a closed form for the fractal dimension of a k-color generalized additive cellular automaton?

For k ≥ 3, how do the fractal dimensions of single-colored parts relate to each other?

Can rule 90 be computed any faster than by Kummer's method?
How reducible are other reducible rules?  (That is, how quickly can we compute them?)
Do all generalized additive rules afford the same amount of computational reducibility?  (If not, this would be a fairly fundamental classification scheme.)

References

Jean-Paul Allouche & Jeffrey Shallit, "The ring of k-regular sequences", Theoretical Computer Science 98 (1992) 163–197.

Eric Rowland, "Local nested structure in rule 30", Complex Systems [to appear].

Stephen Wolfram, "Geometry of binomial coefficients", American Mathematical Monthly 91 (1984) 566–571.

Stephen Wolfram, A New Kind of Science (Wolfram Media 2002).