Issue Theoret. Informatics Appl. Volume 35, Number 3, May-June 2001 Page(s) 239 - 258 DOI 10.1051/ita:2001118

DOI: 10.1051/ita:2001118


Theoret. Informatics Appl. 35, 239-258 (2001)

Number-Conserving Reversible Cellular Automata and Their Computation-Universality

Kenichi Morita and Katsunobu Imai

Hiroshima University, Faculty of Engineering, Higashi-Hiroshima 739-8527, Japan; (morita@iec.hiroshima-u.ac.jp, imai@iec.hiroshima-u.ac.jp)

(Received August 27, 1999. Accepted August 21, 2001.)

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.

AMS Subject: 68Q80, 68Q05.

Key words: Cellular automata -- reversibility -- conservation law -- universality.


© EDP Sciences 2001

What is OpenURL?