# Number-Conserving Reversible Cellular Automata and Their Computation-Universality

Kenichi Morita; Katsunobu Imai

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 35, Issue: 3, page 239-258
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMorita, Kenichi, and Imai, Katsunobu. "Number-Conserving Reversible Cellular Automata and Their Computation-Universality." RAIRO - Theoretical Informatics and Applications 35.3 (2010): 239-258. <http://eudml.org/doc/222077>.

@article{Morita2010,

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},

keywords = {Cellular automata; reversibility; conservation law; universality.; cellular automaton},

language = {eng},

month = {3},

number = {3},

pages = {239-258},

publisher = {EDP Sciences},

title = {Number-Conserving Reversible Cellular Automata and Their Computation-Universality},

url = {http://eudml.org/doc/222077},

volume = {35},

year = {2010},

}

TY - JOUR

AU - Morita, Kenichi

AU - Imai, Katsunobu

TI - Number-Conserving Reversible Cellular Automata and Their Computation-Universality

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

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/222077

ER -

## References

top- J. Albert and K. Culik II, A simple universal cellular automaton and its one-way and totalistic version. Complex Systems1 (1987) 1-16. Zbl0655.68065
- C.H. Bennett, Logical reversibility of computation. IBM J. Res. Dev.17 (1973) 525-532. Zbl0267.68024
- C.H. Bennett, Notes on the history of reversible computation. IBM J. Res. Dev.32 (1988) 16-23.
- E. Fredkin and T. Toffoli, Conservative logic. Int. J. Theoret. Phys.21 (1982) 219-253. Zbl0496.94015
- E. Goles, Sand pile automata. Ann. Inst. H. Poincaré56 (1992) 75-90. Zbl0791.68118
- E. Goles and M. Margenstern, Sand pile as a universal computer. Int. J. Modern Physics C7 (1996) 113-122. Zbl0940.82509
- K. Imai and K. Morita, A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theoret. Comput. Sci. (in press). Zbl0951.68086
- N. Margolus, Physics-like model of computation. Physica D10 (1984) 81-95. Zbl0563.68051
- K. Morita and M. Harao, Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE JapanE-72 (1989) 758-762.
- K. Morita and S. Ueno, Computation-universal models of two-dimensional 16-state reversible cellular automata. IEICE Trans. Inf. & Syst.E75-D (1992) 141-147.
- K. Morita, Computation-universality of one-dimensional one-way reversible cellular automata. Inform. Process. Lett.42 (1992) 325-329. Zbl0779.68064
- K. Morita, Universality of a reversible two-counter machine. Theoret. Comput. Sci.168 (1996) 303-320. Zbl0874.68108
- T. Toffoli, Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci.15 (1977) 213-231. Zbl0364.94085
- T. Toffoli and N. Margolus, Invertible cellular automata: A review. Physica D45 (1990) 229-253. Zbl0729.68066

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.