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.
Mots-clés : cellular automata, reversibility, conservation law, universality
@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}, pages = {239--258}, publisher = {EDP-Sciences}, volume = {35}, number = {3}, year = {2001}, mrnumber = {1869216}, zbl = {1014.68102}, language = {en}, url = {http://archive.numdam.org/item/ITA_2001__35_3_239_0/} }
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 SP - 239 EP - 258 VL - 35 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/item/ITA_2001__35_3_239_0/ LA - en ID - ITA_2001__35_3_239_0 ER -
%0 Journal Article %A Morita, Kenichi %A Imai, Katsunobu %T Number-conserving reversible cellular automata and their computation-universality %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2001 %P 239-258 %V 35 %N 3 %I EDP-Sciences %U http://archive.numdam.org/item/ITA_2001__35_3_239_0/ %G en %F 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) no. 3, pp. 239-258. http://archive.numdam.org/item/ITA_2001__35_3_239_0/
[1] A simple universal cellular automaton and its one-way and totalistic version. Complex Systems 1 (1987) 1-16. | MR | Zbl
and ,[2] Logical reversibility of computation. IBM J. Res. Dev. 17 (1973) 525-532. | MR | Zbl
,[3] Notes on the history of reversible computation. IBM J. Res. Dev. 32 (1988) 16-23. | MR
,[4] Conservative logic. Int. J. Theoret. Phys. 21 (1982) 219-253. | MR | Zbl
and ,[5] Sand pile automata. Ann. Inst. H. Poincaré 56 (1992) 75-90. | EuDML | Numdam | MR | Zbl
,[6] Sand pile as a universal computer. Int. J. Modern Physics C 7 (1996) 113-122. | MR | Zbl
and ,[7] A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theoret. Comput. Sci. (in press). | MR | Zbl
and ,[8] Physics-like model of computation. Physica D 10 (1984) 81-95. | MR | Zbl
,[9] Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE Japan E-72 (1989) 758-762.
and ,[10] Computation-universal models of two-dimensional 16-state reversible cellular automata. IEICE Trans. Inf. & Syst. E75-D (1992) 141-147.
and ,[11] Computation-universality of one-dimensional one-way reversible cellular automata. Inform. Process. Lett. 42 (1992) 325-329. | MR | Zbl
,[12] Universality of a reversible two-counter machine. Theoret. Comput. Sci. 168 (1996) 303-320. | MR | Zbl
,[13] Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15 (1977) 213-231. | MR | Zbl
,[14] Invertible cellular automata: A review. Physica D 45 (1990) 229-253. | MR | Zbl
and ,