Structurally Dynamic Cellular Automata

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. v Contents 1 Introduction 1 1.1 Cellular Automata : : : : : ..