#
The Brain vs. Rule 137: Using Spacetime Patterns to Classify the Complexity of Cellular Automata

##
Averell Sydney Gatton

###
2009

Cellular Automata (CA) are fundamental models of dynamical systems which
can model all types of natural phenomena, perhaps even the fundamental laws
of physics. CA are recursive algorithmic processes that operate in a discrete
cellular array. We study the 88 elementary CA (ECA) defined by a two-state
nearest-neighbor update rule. The 88 ECA display a wide variety of ordered and
disordered, simple and complex evolutions. We define a metric that measures
the complexity of each ECA. To construct this metric, we enumerate all possible shinglings of finite triangular spacetime patterns in past history cones of
the 88 ECA. We then construct a graphical representation of the CA dynamics,
with vertices representing the spacetime patterns and edges representing possible shinglings. We then adapt an algorithm from graph theory to search these
graphs for closed walks that represent quiescent background patterns in the
ECA evolution. We use the histogram of the frequencies of pattern occurrences
in a sample evolution to seed the algorithm. This study defines the complexity,
C , as the fraction of edges beginning on the vertices of the closed walks but not
part of the closed walks themselves.
C estimates the ability of the quiescent
background to support non-trivial long lived structures in the evolution of the
ECA. C is an estimation measure because the forecasting of CA evolution dynamics is undecidable for infinite evolution spaces. We speculate that our graph
representation of pattern shingling is more fundamental than rule tables, and
we apply this principle to a heuristic analysis of the repetitive structures of the
cerebral cortex of the human brain.