RAIRO-Theor. Inf. Appl.
Volume 35, Number 3, May/June 2001
|Page(s)||239 - 258|
|Published online||15 April 2002|
Number-Conserving Reversible Cellular Automata and Their Computation-Universality
Hiroshima University, Faculty of Engineering, Higashi-Hiroshima 739-8527, Japan; e-mail: firstname.lastname@example.org
2 Hiroshima University, Faculty of Engineering, Higashi-Hiroshima 739-8527, Japan; e-mail: email@example.com
Accepted: 21 August 2001
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.
Mathematics Subject Classification: 68Q80 / 68Q05
Key words: Cellular automata / reversibility / conservation law / universality.
© EDP Sciences, 2001
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.