A Simple Computer Embedded in a Reversible and Number-Conserving Two-Dimensional Cellular Space

In this paper, we introduce a 4 4 -state two-dimensional reversible cellular automaton called P 4 having very simple state-transition rules. We show that any reversible two-counter machine can be embedded in a finite configuration of P 4 very concisely. Since a reversible two-counter machine is known to be universal, P 4 has thus universal computing ability. It is a four-neighbor partitioned cellular automaton (PCA) where each cell is divided into four parts. Each part has the state set f0; 1; 2; 3g, hence a cell has 4 4 states. Besides reversibility, P 4 also satisfies the constraint of a number-conservation property, i.e., the total of the integers, which represent cells' states, over the configuration is conserved throughout its evolving process. Reversibility and number-conservation in CA can be regarded as properties that reflect reversibility and conservation of mass or energy in physics. In order to embed a reversible counter machine in P 4 space, we first design six kinds ..