RAIRO-Theor. Inf. Appl.
Volume 33, Number 6, November December 1999
|Page(s)||535 - 550|
|Published online||15 August 2002|
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.