Universality of Reversible Hexagonal Cellular Automata
Hiroshima University, Faculty of Engineering,
Higashi-Hiroshima 739-8527, Japan
2 G.I.F.M., Université de Metz, I.U.T. de Metz, Départment d'Informatique, Île du Saulcy, 57045 Metz Cedex 1, France
Accepted: 12 November 1999
We define a kind of cellular automaton called a hexagonal partitioned cellular automaton (HPCA), and study logical universality of a reversible HPCA. We give a specific 64-state reversible HPCA H1, and show that a Fredkin gate can be embedded in this cellular space. Since a Fredkin gate is known to be a universal logic element, logical universality of H1 is concluded. Although the number of states of H1 is greater than those of the previous models of reversible CAs having universality, the size of the configuration realizing a Fredkin gate is greatly reduced, and its local transition function is still simple. Comparison with the previous models, and open problems related to these model are also discussed.
Mathematics Subject Classification: 68Q80 / 68Q05
Key words: Cellular automata / reversibility / universality.
© EDP Sciences, 1999