Geodesic
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 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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.

Classification : 68Q80, 68Q05
Keywords: 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},
     year = {2001},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {3},
     mrnumber = {1869216},
     zbl = {1014.68102},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/item/ITA_2001__35_3_239_0/