next up previous
Next: De Bruijn diagrams Up: Reversible Cellular Automata Previous: Rules spanning three

Some relevant diagrams

One approach to encountering reversible automata is to scan all the automata of a given order, to find those for which there are unique ancestors, and to work out their rules of inversion. The task is formidable, considering that there are different rules for automata; S. Amoroso and Y. N. Patt [22] reported a survey of automata in 1972, which uncovered eight instances of nontrivial reversible automata, whose principle of operation differed from the later ideas of Fredkin. Previously they had known that or automata lacked nontrivial rules (shift, complement, identity).

Two different algorithms formed the content of their article; one determined the existence of the Garden of Eden (or else concluded that every configuration has ancestors), the other could verify that a configuration had only one ancestor. Formalizing the auxiliary diagrams and tables which were incidental to their presentation would enhance our understanding of the procedures and could facilitate the derivation of additional results.





Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx