Universality of Reversible Hexagonal Cellular Automata
Kenichi MoritaHiroshima University, Faculty of Engineering, Higashi-Hiroshima 739-8527, JapanMaurice MargensternKatsunobu ImaiHiroshima University, Faculty of Engineering, Higashi-Hiroshima 739-8527, Japan
1999en
ABI
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.
Identifiers
Citations and references
Cited by 20 references