Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T22:11:32.401Z Has data issue: false hasContentIssue false

Number-Conserving Reversible Cellular Automata and Their Computation-Universality

Published online by Cambridge University Press:  15 April 2002

Kenichi Morita
Affiliation:
Hiroshima University, Faculty of Engineering, Higashi-Hiroshima 739-8527, Japan; e-mail: morita@iec.hiroshima-u.ac.jp
Katsunobu Imai
Affiliation:
Hiroshima University, Faculty of Engineering, Higashi-Hiroshima 739-8527, Japan; e-mail: imai@iec.hiroshima-u.ac.jp
Get access

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.

Information

Type
Research Article
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable