Harold V. Mcintosh
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.
[html] [ pdf (340 KB)]