Universality of Reversible Hexagonal Cellular Automata

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 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.