Number-conserving reversible cellular automata and their computation-universality
Morita, Kenichi ; Imai, Katsunobu
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 239-258 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2001-01-01
Classification:  68Q80,  68Q05 
@article{ITA_2001__35_3_239_0,
     author = {Morita, Kenichi and Imai, Katsunobu},
     title = {Number-conserving reversible cellular automata and their computation-universality},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {35},
     year = {2001},
     pages = {239-258},
     mrnumber = {1869216},
     zbl = {1014.68102},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2001__35_3_239_0}
}

Morita, Kenichi; Imai, Katsunobu. Number-conserving reversible cellular automata and their computation-universality. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) pp. 239-258. http://gdmltest.u-ga.fr/item/ITA_2001__35_3_239_0/

[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. | MR 891509 | Zbl 0655.68065

[2] C.H. Bennett, Logical reversibility of computation. IBM J. Res. Dev. 17 (1973) 525-532. | MR 449020 | Zbl 0267.68024

[3] C.H. Bennett, Notes on the history of reversible computation. IBM J. Res. Dev. 32 (1988) 16-23. | MR 949739

[4] E. Fredkin and T. Toffoli, Conservative logic. Int. J. Theoret. Phys. 21 (1982) 219-253. | MR 657156 | Zbl 0496.94015

[5] E. Goles, Sand pile automata. Ann. Inst. H. Poincaré 56 (1992) 75-90. | Numdam | MR 1149869 | Zbl 0791.68118

[6] E. Goles and M. Margenstern, Sand pile as a universal computer. Int. J. Modern Physics C 7 (1996) 113-122. | MR 1400310 | Zbl 0940.82509

[7] K. Imai and K. Morita, A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theoret. Comput. Sci. (in press). | MR 1739889 | Zbl 0951.68086

[8] N. Margolus, Physics-like model of computation. Physica D 10 (1984) 81-95. | MR 762656 | Zbl 0563.68051

[9] K. Morita and M. Harao, Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE Japan E-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. | MR 1178211 | Zbl 0779.68064

[12] K. Morita, Universality of a reversible two-counter machine. Theoret. Comput. Sci. 168 (1996) 303-320. | MR 1422960 | Zbl 0874.68108

[13] T. Toffoli, Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15 (1977) 213-231. | MR 462816 | Zbl 0364.94085

[14] T. Toffoli and N. Margolus, Invertible cellular automata: A review. Physica D 45 (1990) 229-253. | MR 1094877 | Zbl 0729.68066