Cellular Automata as a Model of Physical Systems
Donny Cheung and Carlos A. Perez-Delgado
Cellular Automata (CA), as they are presented in the literature, are abstract mathematical models of computation. In this paper we present an alternate approach: using the CA as a model or theory of physical systems and devices. While this approach abstracts away all details of the underlying physical system, it remains faithful to the fact that there is an underlying physical reality which it describes. This imposes certain restrictions on the types of computations a CA can physically carry out, and the resources it needs to do so. In this paper we explore these and other consequences of our reformalization.
Keywords: reversibility, quantum automata, simulation