Number-Conserving Reversible Cellular Automata and Their Computation-Universality

Kenichi Morita; Katsunobu Imai

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 35, Issue: 3, page 239-258
  • ISSN: 0988-3754

Abstract

top
We introduce a new model of cellular automaton called a one-dimensional number-conserving partitioned cellular automaton (NC-PCA). An NC-PCA is a system such that a state of a cell is represented by a triple of non-negative integers, and the total (i.e., sum) of integers over the configuration is conserved throughout its evolving (computing) process. It can be thought as a kind of modelization of the physical conservation law of mass (particles) or energy. We also define a reversible version of NC-PCA, and prove that a reversible NC-PCA is computation-universal. It is proved by showing that a reversible two-counter machine, which has been known to be universal, can be simulated by a reversible NC-PCA.

How to cite

top

Morita, Kenichi, and Imai, Katsunobu. "Number-Conserving Reversible Cellular Automata and Their Computation-Universality." RAIRO - Theoretical Informatics and Applications 35.3 (2010): 239-258. <http://eudml.org/doc/222077>.

@article{Morita2010,
abstract = { We introduce a new model of cellular automaton called a one-dimensional number-conserving partitioned cellular automaton (NC-PCA). An NC-PCA is a system such that a state of a cell is represented by a triple of non-negative integers, and the total (i.e., sum) of integers over the configuration is conserved throughout its evolving (computing) process. It can be thought as a kind of modelization of the physical conservation law of mass (particles) or energy. We also define a reversible version of NC-PCA, and prove that a reversible NC-PCA is computation-universal. It is proved by showing that a reversible two-counter machine, which has been known to be universal, can be simulated by a reversible NC-PCA. },
author = {Morita, Kenichi, Imai, Katsunobu},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Cellular automata; reversibility; conservation law; universality.; cellular automaton},
language = {eng},
month = {3},
number = {3},
pages = {239-258},
publisher = {EDP Sciences},
title = {Number-Conserving Reversible Cellular Automata and Their Computation-Universality},
url = {http://eudml.org/doc/222077},
volume = {35},
year = {2010},
}

TY - JOUR
AU - Morita, Kenichi
AU - Imai, Katsunobu
TI - Number-Conserving Reversible Cellular Automata and Their Computation-Universality
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 3
SP - 239
EP - 258
AB - We introduce a new model of cellular automaton called a one-dimensional number-conserving partitioned cellular automaton (NC-PCA). An NC-PCA is a system such that a state of a cell is represented by a triple of non-negative integers, and the total (i.e., sum) of integers over the configuration is conserved throughout its evolving (computing) process. It can be thought as a kind of modelization of the physical conservation law of mass (particles) or energy. We also define a reversible version of NC-PCA, and prove that a reversible NC-PCA is computation-universal. It is proved by showing that a reversible two-counter machine, which has been known to be universal, can be simulated by a reversible NC-PCA.
LA - eng
KW - Cellular automata; reversibility; conservation law; universality.; cellular automaton
UR - http://eudml.org/doc/222077
ER -

References

top
  1. J. Albert and K. Culik II, A simple universal cellular automaton and its one-way and totalistic version. Complex Systems1 (1987) 1-16.  
  2. C.H. Bennett, Logical reversibility of computation. IBM J. Res. Dev.17 (1973) 525-532.  
  3. C.H. Bennett, Notes on the history of reversible computation. IBM J. Res. Dev.32 (1988) 16-23.  
  4. E. Fredkin and T. Toffoli, Conservative logic. Int. J. Theoret. Phys.21 (1982) 219-253.  
  5. E. Goles, Sand pile automata. Ann. Inst. H. Poincaré56 (1992) 75-90.  
  6. E. Goles and M. Margenstern, Sand pile as a universal computer. Int. J. Modern Physics C7 (1996) 113-122.  
  7. K. Imai and K. Morita, A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theoret. Comput. Sci. (in press).  
  8. N. Margolus, Physics-like model of computation. Physica D10 (1984) 81-95.  
  9. K. Morita and M. Harao, Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE JapanE-72 (1989) 758-762.  
  10. 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.  
  11. K. Morita, Computation-universality of one-dimensional one-way reversible cellular automata. Inform. Process. Lett.42 (1992) 325-329.  
  12. K. Morita, Universality of a reversible two-counter machine. Theoret. Comput. Sci.168 (1996) 303-320.  
  13. T. Toffoli, Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci.15 (1977) 213-231.  
  14. 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.