Number-conserving reversible cellular automata and their computation-universality

Kenichi Morita; Katsunobu Imai

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

  • 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 - Informatique Théorique et Applications 35.3 (2001): 239-258. <http://eudml.org/doc/92664>.

@article{Morita2001,
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 - Informatique Théorique et Applications},
keywords = {cellular automata; reversibility; conservation law; universality; cellular automaton},
language = {eng},
number = {3},
pages = {239-258},
publisher = {EDP-Sciences},
title = {Number-conserving reversible cellular automata and their computation-universality},
url = {http://eudml.org/doc/92664},
volume = {35},
year = {2001},
}

TY - JOUR
AU - Morita, Kenichi
AU - Imai, Katsunobu
TI - Number-conserving reversible cellular automata and their computation-universality
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2001
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/92664
ER -

References

top
  1. [1] J. Albert and K. Culik II, A simple universal cellular automaton and its one-way and totalistic version. Complex Systems 1 (1987) 1-16. Zbl0655.68065MR891509
  2. [2] C.H. Bennett, Logical reversibility of computation. IBM J. Res. Dev. 17 (1973) 525-532. Zbl0267.68024MR449020
  3. [3] C.H. Bennett, Notes on the history of reversible computation. IBM J. Res. Dev. 32 (1988) 16-23. MR949739
  4. [4] E. Fredkin and T. Toffoli, Conservative logic. Int. J. Theoret. Phys. 21 (1982) 219-253. Zbl0496.94015MR657156
  5. [5] E. Goles, Sand pile automata. Ann. Inst. H. Poincaré 56 (1992) 75-90. Zbl0791.68118MR1149869
  6. [6] E. Goles and M. Margenstern, Sand pile as a universal computer. Int. J. Modern Physics C 7 (1996) 113-122. Zbl0940.82509MR1400310
  7. [7] K. Imai and K. Morita, A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theoret. Comput. Sci. (in press). Zbl0951.68086MR1739889
  8. [8] N. Margolus, Physics-like model of computation. Physica D 10 (1984) 81-95. Zbl0563.68051MR762656
  9. [9] K. Morita and M. Harao, Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE Japan E-72 (1989) 758-762. 
  10. [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. [11] K. Morita, Computation-universality of one-dimensional one-way reversible cellular automata. Inform. Process. Lett. 42 (1992) 325-329. Zbl0779.68064MR1178211
  12. [12] K. Morita, Universality of a reversible two-counter machine. Theoret. Comput. Sci. 168 (1996) 303-320. Zbl0874.68108MR1422960
  13. [13] T. Toffoli, Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15 (1977) 213-231. Zbl0364.94085MR462816
  14. [14] T. Toffoli and N. Margolus, Invertible cellular automata: A review. Physica D 45 (1990) 229-253. Zbl0729.68066MR1094877

NotesEmbed ?

top

You must be logged in to post comments.