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.