Classifying Nestedness in Cellular Automata

Eric Rowland

Rutgers University

It is widely known that certain cellular automata produce beautiful, global nested (“fractal”) patterns. For example, the 2-color nearest-neighbor rules 60, 90, 105, and 150 all generate global nested structures when begun from a single black cell. These rules are computationally reducible, in that their regularity allows one to compute their output asymptotically faster than the automata produce it.

Additionally, some cellular automata exhibit local nested structure on one or both sides. These include the right sides of rules 30, 45, and 75. Not surprisingly, local nested structure provides only local computational reducibility.

We would like to classify different types of global and local nested structure. One way to do this might be to determine the “amount” (in running time) of computational reducibility that each affords. In particular, do all global nested structures provide the same amount of computational reducibility? Are there likely to be local nested structures that provide more reducibility than that of rule 30?

Another possible classification system might be based on fractal dimensions. What values can the fractal dimension of a global nested cellular automaton take?

With lots of examples, I will share my thoughts on these and other questions.

[presentation materials]