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

Abstract

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

How to cite

top

Morita, 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
  1. C.H. Bennett, Logical reversibility of computation. IBM J. Res. Develop.17 (1973) 525-532.  
  2. C.H. Bennett, Notes on the history of reversible computation. IBM J. Res. Develop.32 (1988) 16-23.  
  3. E. Fredkin and T. Toffoli, Conservative logic, Internat. J. Theoret. Phys.21 (1982) 219-253.  
  4. K. Imai and K. Morita, A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theoret. Comput. Sci., to appear.  
  5. N. Margolus, Physics-like model of computation. PhysicaD10 (1984) 81-95.  
  6. K. Morita and M. Harao, Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE JapanE-72 (1989) 758-762.  
  7. 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.  
  8. 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.  
  9. T. Toffoli, Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci.15 (1977) 213-231.  
  10. T. Toffoli and N. Margolus, Invertible cellular automata: A Review. Physica D45 (1990) 229-253.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.