Reversible Cellular Automata
Harold V. McIntosh
Departamento de Aplicación de Microcomputadoras,
Instituto de Ciencias, Universidad Autónoma de Puebla,
Apartado postal 461, 72000 Puebla, Puebla, México.
E-mail:mcintosh@servidor.unam.mxApril 10, 1991
Abstract:
A reversible cellular automaton is one whose evolution, and therefore the entire past history of any configuration, can be uniquely deciphered. There are degrees of reversibility, depending upon whether the configurations considered are arbitrary, periodic, or quiescent at infinity; which are subsidiary to more general questions of injectivity and surjectivity, within a general perspective of the ancestry of configurations. Reversibility is examined within this general context, expanded to include the frequency distribution of ancestors and its moments. It is argued that the coupling of zero variance (judged from the maximum eigenvalue of the second moment matrix) with zero frequency for zero ancestors (surjectivity) is the fundamental concept. An ideal theoretic property inherent in decompositions of the de Bruijn matrix suffices to prove the coupling for automata. Surjectivity in different contexts, injectivity, and degrees of multiple valuedness all follow from this central result. Although the article is intended as a review, it is far from a complete historical survey; the presentation is uniformized through the use of graphs, de Bruijn diagrams and matrices wherever possible.
- Introduction
- Fredkin's model
- Some relevant diagrams
- Vector subset diagram
- Symbolic de Bruijn matrices
- The statistics of counterimages
- Moments and frequencies
- Some illustrative examples
- A statistical Gerschgorin theorem
- General considerations
- Pairs of states
- The subset matrix
- Reversing a rule
- Conclusions
- References
- About this document ...
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx