Voir la notice de l'article provenant de la source Numdam
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.
@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://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/