Universality of Reversible Hexagonal Cellular Automata
Kenichi Morita, Maurice Margenstern, Katsunobu Imai (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
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 , 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 is concluded. Although the number of states of is greater than those of the previous...