Number-Conserving Reversible Cellular Automata and Their Computation-Universality
- 1 May 2001
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 35 (3) , 239-258
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.Keywords
This publication has 10 references indexed in Scilit:
- A computation-universal two-dimensional 8-state triangular reversible cellular automatonTheoretical Computer Science, 2000
- Universality of a reversible two-counter machineTheoretical Computer Science, 1996
- SAND PILE AS A UNIVERSAL COMPUTERInternational Journal of Modern Physics C, 1996
- Computation-universality of one-dimensional one-way reversible cellular automataInformation Processing Letters, 1992
- Invertible cellular automata: A reviewPhysica D: Nonlinear Phenomena, 1990
- Notes on the history of reversible computationIBM Journal of Research and Development, 1988
- Physics-like models of computationPhysica D: Nonlinear Phenomena, 1984
- Conservative logicInternational Journal of Theoretical Physics, 1982
- Computation and construction universality of reversible cellular automataJournal of Computer and System Sciences, 1977
- Logical Reversibility of ComputationIBM Journal of Research and Development, 1973