Number-conserving reversible cellular automata and their computation-universality

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 -