Structurally Dynamic Cellular Automata

Stephen M. Majercik

We describe structurally dynamic cellular automata (SDCA), cellular
automata with dynamic cell links first proposed by Ilachinski and Halpern
as a promising model for the simulation and study of naturally occurring
processes.  We introduce three new models of SDCA, defining these models
precisely as models of computation rather than as tools with which to
model physical processes, and we prove some results that begin to
delineate their computational capabilities and their relationship to
conventional cellular automata. We show a partial simulation hierarchy of
SDCA classes and prove that SDCA are faster than conventional cellular
automata.  Finally, we describe a CA-universal SDCA, an SDCA that is
capable of simulating any conventional cellular automaton of the same
dimension.  The speed of our simulator represents a significant
improvement on a previous result which constructed a CA-universal
conventional cellular automaton.