Universality of Reversible Hexagonal Cellular Automata

¹ Hiroshima University, Faculty of Engineering, Higashi-Hiroshima 739-8527, Japan
² G.I.F.M., Université de Metz, I.U.T. de Metz, Départment d'Informatique, Île du Saulcy, 57045 Metz Cedex 1, France

Received: 18 March 1999
Accepted: 12 November 1999

Abstract

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 H₁, 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 H₁ is concluded. Although the number of states of H₁ 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.