Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T18:50:19.007Z Has data issue: false hasContentIssue false
  • English
  • Français

Universality of Reversible Hexagonal Cellular Automata

Published online by Cambridge University Press:  15 August 2002

Kenichi Morita ,
Maurice Margenstern  and
Katsunobu Imai
Kenichi Morita
Affiliation:
Hiroshima University, Faculty of Engineering, Higashi-Hiroshima 739-8527, Japan
Maurice Margenstern
Affiliation:
G.I.F.M., Université de Metz, I.U.T. de Metz, Départment d'Informatique, Île du Saulcy, 57045 Metz Cedex 1, France
Katsunobu Imai
Affiliation:
Hiroshima University, Faculty of Engineering, Higashi-Hiroshima 739-8527, Japan
Get access

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.

Keywords

Cellular automatareversibilityuniversality.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 33 , Issue 6 , November 1999 , pp. 535 - 550
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bennett, C.H., Logical reversibility of computation. IBM J. Res. Develop. 17 (1973) 525-532. CrossRef
Bennett, C.H., Notes on the history of reversible computation. IBM J. Res. Develop. 32 (1988) 16-23. CrossRef
Fredkin, E. and Toffoli, T., Conservative logic, Internat. J. Theoret. Phys. 21 (1982) 219-253. CrossRef
K. Imai and K. Morita, A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theoret. Comput. Sci., to appear.
N. Margolus, Physics-like model of computation. Physica D 10 (1984) 81-95.
K. Morita and M. Harao, Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE Japan E-72 (1989) 758-762.
K. Morita, A simple construction method of a reversible finite automaton out of Fredkin gates, and its related problem. Trans. IEICE Japan E-73 (1990) 978-984.
K. Morita and S. Ueno, Computation-universal models of two-dimensional 16-state reversible cellular automata. IEICE Trans. Inf. Syst. E75-D (1992) 141-147.
Toffoli, T., Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15 (1977) 213-231. CrossRef
Toffoli, T. and Margolus, N., Invertible cellular automata: A Review. Physica D 45 (1990) 229-253. CrossRef