# Universality of Reversible Hexagonal Cellular Automata

Kenichi Morita; Maurice Margenstern; Katsunobu Imai

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 33, Issue: 6, page 535-550
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMorita, Kenichi, Margenstern, Maurice, and Imai, Katsunobu. "Universality of Reversible Hexagonal Cellular Automata." RAIRO - Theoretical Informatics and Applications 33.6 (2010): 535-550. <http://eudml.org/doc/222072>.

@article{Morita2010,

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

author = {Morita, Kenichi, Margenstern, Maurice, Imai, Katsunobu},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Cellular automata; reversibility; universality.; hexagonal partitioned cellular automaton; cellular automaton},

language = {eng},

month = {3},

number = {6},

pages = {535-550},

publisher = {EDP Sciences},

title = {Universality of Reversible Hexagonal Cellular Automata},

url = {http://eudml.org/doc/222072},

volume = {33},

year = {2010},

}

TY - JOUR

AU - Morita, Kenichi

AU - Margenstern, Maurice

AU - Imai, Katsunobu

TI - Universality of Reversible Hexagonal Cellular Automata

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 33

IS - 6

SP - 535

EP - 550

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

LA - eng

KW - Cellular automata; reversibility; universality.; hexagonal partitioned cellular automaton; cellular automaton

UR - http://eudml.org/doc/222072

ER -

## References

top- C.H. Bennett, Logical reversibility of computation. IBM J. Res. Develop.17 (1973) 525-532.
- C.H. Bennett, Notes on the history of reversible computation. IBM J. Res. Develop.32 (1988) 16-23.
- E. Fredkin and T. Toffoli, Conservative logic, Internat. J. Theoret. Phys.21 (1982) 219-253.
- 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. PhysicaD10 (1984) 81-95.
- K. Morita and M. Harao, Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE JapanE-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 JapanE-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.
- T. Toffoli, Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci.15 (1977) 213-231.
- T. Toffoli and N. Margolus, Invertible cellular automata: A Review. Physica D45 (1990) 229-253.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.