数理解析研究所講究録1106 巻 1999 年 130-141130Computing Ability of Reversible and Conservative Cellular Automata
可逆的・保存的なセル. オートマトンの計算能力

Kenichi Morita, and Katsunobu Imai

森田憲–, 今井克暢
Faculty of Engineering, Hiroshima University
広島大学工学部{morita,

http:$\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{i}$$//\mathrm{w}\mathrm{W}\mathrm{W}.\mathrm{k}\mathrm{e}$}$\mathrm{Q}\mathrm{k}\mathrm{e}.\mathrm{S}\mathrm{y}\mathrm{S}.\mathrm{h}\mathrm{i}\mathrm{r}\mathrm{o}\mathrm{s}\mathrm{h}\mathrm{i}\mathrm{m}\mathrm{a}-\mathrm{u}.\mathrm{a}\mathrm{C}\cdot \mathrm{j}\mathrm{P}$. sys. hiroshima-u.

$\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/\sim_{\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{i}}\mathrm{t}\mathrm{a}/$Abstract
We introduce a new model of cellular automaton called a one-dimensional numberconserving partitioned cellular automaton (NC-PCA). An NC-PCA is a system such that astate of a cell is represented by a triple of non-negative integers, and the total (i.e., sum) ofintegers 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-countermachine, which has been known to be universal, can be simulated by a reversible NC-PCA.

1Introduction

Recently, various kinds of interesting computing models which directly reflect laws of nature
have been proposed and investigated. Among others, quantum computing, DNA computing,reversible computing, etc. have been extensively studied. A reversible computer is a systemsuch that its transition function of the whole state is a one-to-one mapping (injection), hence,roughly speaking, it is a backward deterministic system. It is a kind of model reflecting physical reversibility, and has been known to be very important when studying inevitable power
dissipation in a computing process [3, 4, 5, 13]. Besides the problem of energy consumption,
they have very richsuch a system is also interesting from a computational viewpoint,
Until now, several
reversibility
constraint.
ability of information processing in spite of theversions of computation-universality of RCAs for one- and two-dimensional cases have beenshown [8, 9, 10, 11, 12, 16, 17, 18, 19]. It is also possible to construct an RCA in which various
objects can self-reproduce $[15, 17]$ .
Conservation of mass or energy is also an important physical law as well as reversibility.
Fredkin and Toffoli [5] proposed Conservative Logic, a kind of logic circuit theory, that models
both reversibility and conservation law of physics, and showed its universality. In this system,
each primitive logic gate must satisfy the constraints of reversibility (i.e., its logical function isan injection), and conservation of bits (i.e., the total number of logical value “ ” is conserved
between its input and output). Also for cellular automata, several universal models that areboth reversible and bit-conserving have been known [8, 9, 11].
called a one-dimensional
In this paper, we define a new model of cellular automaton
number-conserving partitioned cellular automaton (NC-PCA), which generalize the notion of. In an NC-PCA, each cell is partitioned into three parts, i.e., left, center, andbit-conserving
right parts, and the state of each part is represented by a non-negative integer (thus, the state ofa cell is represented by a triple of non-negative integers). The next state of a cell is determinedby the present states of the right part of the left-neighboring cell, the center part of this cell,and the left part of the right-neighboring cell (not depending on the whole state of the threecells). The total number is conserved during the local transition, hence the total number over aconfiguration is also conserved throughout the evolving process.
$\mathrm{b}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{U}8\mathrm{e}$$1$$(\mathrm{C}\mathrm{A})$$\mathrm{C}\mathrm{A}$$\mathrm{s}$131

Figure 1: The local transition function$g$of a PCA$A$.

Related to this model, a few other models in which each cell state is represented by a nonnegative integer have been known: a totalistic CA [1] and a sand pile model $[6, 7]$ . In [1], aCA with a simple totalistic rule (but not necessarily number-conserving) has been shown to beuniversal. In $[6, 7]$ , a kind of an automata system having a specific type of number-conserving
rules are studied.
Here, we investigate the computing ability of an NC-PCA, and its reversible version. We
show that an NP-PCA is computation universal even if it is reversible. This strengthens theprevious result that a one-dimensional reversible CA (not necessarily a number-conserving one)is computation-universal [10]. We prove it by showing that a reversible two-counter machine,which has been known to be universal [14], can be simulated by a reversible NC-PCA.

2

Number-Conserving Partitioned Cellular Automata

In order to define a one-dimensional number-conserving partitioned cellular automaton (NCPCA), we first give a definition of a partitioned cellular automaton (PCA) that has been introduced to design a reversible cellular automaton [10].

Definition 2.1 A deterministic one-dimensional three-neighbor partitioned cellular automaton(PCA) is a system defined by,$A=(\mathrm{z}, (L, c, R),g, (\tilde{q}_{L},\tilde{q}_{C},\tilde{q}_{R}))$

where is the set of all integers at which cells are placed, $L,$ $C$ and $R$ are non-empty finite setsof states of left, center, and right parts of a cell, $g;R\cross C\cross Larrow L\cross C\cross R$ is a local function,andis a quiescent state that satisfies.
A configuration over the set $Q=L\cross C\cross R$ is a mapping. Let Conf $(Q)$ denotethe set of all configurations over , i.e., Conf $(Q)=\{\alpha|\alpha:\mathrm{Z}arrow Q\}$ . A qui.escent configurationis the one such that all the cells are in the quiescent states.
Let pro$L:Qarrow L$ is a projection function such thatfor all $(l, c, r)\in Q$ .
Projection functions: $Qarrow C$ , and pro : $Qarrow R$ are also defined similarly. The globalof is defined as follows.
function$\mathrm{Z}$$(\tilde{q}_{L},\tilde{q}c,\tilde{q}_{R})\in L\cross C\cross R$$g(\tilde{q}R,\tilde{q}_{C},\tilde{q}_{L})=(\tilde{q}_{L},\tilde{q}c,\tilde{q}_{R})$$\alpha:\mathrm{Z}arrow Q$$Q$$(\tilde{q}_{L},\tilde{q}c,\tilde{q}_{R})$$\mathrm{p}\mathrm{r}\mathrm{o}_{L}(l, c, r)=l$$\mathrm{p}\mathrm{r}\mathrm{o}_{C}$

$R$

$A$

$G:\mathrm{C}_{0}\mathrm{n}\mathrm{f}(Q)arrow \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{f}(Q)$$\forall x\in \mathrm{Z}:G(\alpha)(x)=g$($\mathrm{p}\mathrm{r}\mathrm{o}_{R}(\alpha(x-1)),$

Fig. 1 shows how the local function$g$proC $(\alpha(x))$ , pro $L(\alpha(x+1))$ )is applied to each cell. In the following, an equation’$g(r, c, l)=(l’, d, r)$is called a rule of $A$ , and write it by$[r, c, l]arrow[l’,c’, r’]$ .

We regard the local function$g$as the set of such rules for convenience.

Next, we define the notion of reversibility for PCAs.

132

Definition 2.2 Letiff its global function

be a PCA. We say is globally reversible.
, and locally reversible iff its local function is$A$$A=(\mathrm{Z}, (L, C, R),g, (\tilde{q}_{L},\tilde{q}_{C},\tilde{q}_{R}))$

$G$

is

$\mathrm{o}\mathrm{n}\mathrm{e}- \mathrm{t}_{0}-\mathrm{o}\mathrm{n}\mathrm{e}$$g$$\mathrm{o}\mathrm{n}\mathrm{e}-\mathrm{t}_{0}- \mathrm{o}\mathrm{n}\mathrm{e}$It is easy to prove the folowing proposition on PCA, which has been shown in [10].

Proposition 2.1 Let

be a PCA.

$A$

$A$

is globally reversible iff it is locally reversible.

By Proposition 2.1, a globally or locally reversible PCA is called simply “reversible” and, it is sufficient to give adenoted by RPCA. By this, if we want to construct a reversible.
a reversibleeasy
todesign
.
This
makes
it
PCA whose local function is
on
of
only
a
subsetit,
When we design a one-to-one local function it is sufficient to define$R\cross C\cross L$ that are needed to perform a given task. Because, we can always find a-one-one on theextension from a given partial function provided that the latter function issubset. This is assured by the following proposition (its proof is omitted since it is easy).
$\mathrm{C}\mathrm{A}$$\mathrm{C}\mathrm{A}$$g$$\mathrm{o}\mathrm{n}\mathrm{e}- \mathrm{t}_{0}-\mathrm{o}\mathrm{n}\mathrm{e}$$g$$\mathrm{o}\mathrm{n}\mathrm{e}- \mathrm{t}_{0}$$\mathrm{o}\mathrm{n}\mathrm{e}- \mathrm{t}_{0}$and $B$ be finite sets such that $|A|=|B|$ , and let be a mapping
Proposition 2.2 Let$A’arrow B$ for some $A’(\subset A)$ . If-one mapping : $Aarrow B$
is one-to-one, then there is a
$a\in
A’$
.
such that $g’(a)=g(a)$ for all
$A$

$g$

$g’$

$\mathrm{o}\mathrm{n}\mathrm{e}- \mathrm{t}_{\mathrm{O}}$$g$, it isWe now give a definition of a number-conserving PCA. As in the case of a reversible
also convenient to use the framework of a PCA. Because, the the notion of number-conservation
can be expressed by a simple constraint on a local function of a PCA.
$\mathrm{C}\mathrm{A}$denotes the
be a PCA, where
Definition 2.3 Let
is called a oneset of integers $\{0,1, \cdots , m-1,m\}$ , and $k(\leq m)$ is a non-negative integer.
dimensional number-conserving partitioned cellular automaton (NC-PCA), iff it satisfies the, if $g(r,c, l)=(l”,c, r’)$ , then $r+c+l=$
following condition: For$A=(\mathrm{Z}, (\mathrm{N}_{m},\mathrm{N}_{m’ m}\mathrm{N}),g, (0, k,0))$$\mathrm{N}_{m}$$A$$\mathrm{a}11’(r,c, l),$$(l”, C, r’)\in \mathrm{N}_{m}^{3}$$l’+d+r’$ .

A reversible NC-PCA is also defined similarly, and denoted by NC-RPCA.

3

Universality of an NC-RPCA

In this section, we show that for any reversible two-counter machine there is an NC-RPCA
that simulates it. Since a reversible two-counter machines has been known to be computationuniversal [14], we can conclude that an NC-RPCA is also universal.
In [14] a counter machine (CM) is defined as a kind of multi-tape Turing machine whose
heads are read-only ones and whose tapes are all blank except the leftmost squares as shown in). This definition is convenient
giving the notion of reversibility
blankFig. 2 ( $P$
on a CM.

is.a$\mathrm{f}\mathrm{o}\mathrm{r}\backslash$$\mathrm{s}.\mathrm{y}\mathrm{m}\mathrm{b}\mathrm{o}\mathrm{l}$Definition 3.1 A -counter machine (CM $(k)$ ) is a system$k$$M=(k, Q, \delta, q0, qf)$,

where is the number of tapes (or counters), is a nonempty finite set of internal states, $q_{0}\in Q$
is an initial state, and $q_{f}\in Q$ is a final (halting) state. $M$ uses $\{Z, P\}$ as a tape alphabet. is, $k-$
a move relation which is a subset of $(Q\cross\{0,1, \cdots, k-1\}\cross\{Z, P\}\cross Q)\cup(Q\cross\{0,1,$$1\}\cross\{-,0, +\}\cross Q)$(where “-,,, “ ”, and $”+$ ” denote left-shift, no-shift, and right-shift of ahead, respectively). Tapes are one-way (rightward) infinite. The leftmost squares of the tapes
contain the symbol “Z”s, and all the other squares contain “P”s ( and $P$ stand for “zero” and“positive”).
Each element of is called a quadruple, and is either of the form
$k$

$Q$

$\delta$$\cdots$$0$$Z$$\delta$$[q,i, s,q’]$or $[q,i,d, q]’$ ,133Figure 2: A -counter machine (CM $(k)$ ).
$k$where $q’\in Q,$ $i\in\{0,1, \cdots, k-1\},$ $s\in\{Z, P\},$ $d\in$ $\{-, 0, +\}$ . The quadruple $[q, i, S, q’]$ meansthat if $M$ is in the state and the i-th head is reading the symbol then change the state into
. It is used to test whether the contents of a counter are zero or positive. On the other hand,$[q, i, d, q’]$ means that if $M$ is in the statethen shift the i-th head to the direction and change
the state into . It is used to increment or decrement a counter by one (or make no change if
$q,$

$q$

$s$

$q’$

$d$

$q$

$q’$

$d=0)$.

$\mathrm{D}\mathrm{e}\mathrm{f}\mathrm{i}\dot{\mathrm{n}}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}3.2$

tuple

An instantaneous description$(\mathrm{I}\mathrm{D})$of a CM $(k)M=(k,$ $Q,$$(q,n_{0}, n_{1}, \cdots, n_{k1}-)\in Q\chi \mathrm{N}^{k}$$\delta,$$q0,$ $qf^{)}$,

where $\mathrm{N}=\{0,1, \cdots \}$ . It represents that $M$ is in the state and the counterassume the position of the leftmost square of a tape is ). The transition
of $M$ is defined as follows:
$q$

$0$

( no,
$q,$

$\cdots,$$n_{i-}1,n_{i},$ $ni+1,$

is a $(k+1)-$

$i$

keeps

$\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}\vdash_{M}$$\cdots,$$n_{k}-1$$n_{i}$(weover IDs)$\vdash_{M}(q’, n_{0}, \cdots , n_{i-1},n_{i}’, n_{i+1}, \cdots, n_{k-1})$

holds iff one of the following conditions (1) $-(5)$ is satisfied.
(1) $[q,i, Z,q’]\in\delta$ and $n_{i}=n_{i}’=0$ .
(2) $[q, i,P, q]’\in\delta$ and $n_{i}=n_{i}’>0$ .
$(4)(3)$and $n_{i}+1=n_{i}’$ .
We denote reflexive and transitive closure(5)$0,1,$ $\cdots)$$[q,i, +, q’]\in\delta$$\mathrm{o}\mathrm{f}\vdash_{M}$.

by$\vdash^{*}M$, and -step transition$n$$\mathrm{b}\mathrm{y}\vdash_{M}^{n}$$(n=$

Definition 3.3 Let $M=(k, Q, \delta, q0, qf)$ be a CM $(k)$ , and$\alpha_{1}=[p_{1},i_{1,1,p_{1}’}X]$

be two distinct quadruples inwhere $D=$ $\{-, 0, +\}$ .
$p_{1}=p_{2}$$\delta$A. We say$\alpha_{1}$

and
and

$\alpha_{2}=[p_{2},i_{2}, x2,p_{2}’]$$\alpha_{2}$overlap in domain iff the following holds,$[i_{1}\neq i_{2}\vee x_{1}=x_{2}x_{1}\in Dx_{2}\in D]$

134

We sayand$\alpha_{1}$$\alpha_{2}$overlap in range iff the following holds.
$p_{1}’=p_{2}’$A [$i_{1}\neq i_{2}$V $x_{1}=x_{2}$ V $x_{1}\in D$ V $x_{2}\in D$]

A quadruple is called deterministic (reversible, respectively) iff there is no other quadruple inwhich overlaps in domain (range) with . $M$ is called deterministic (reversible, respectively).
iff every quadruple in is deterministic (reversible). A reversible CM $(k)$ is denoted by$\alpha$$\delta$$\alpha$$\mathrm{R}\mathrm{C}\mathrm{M}(k)$$\delta$

For example, the following pair$[q_{1},2, P,q_{3}]$and$[q_{4},2, +,q_{3}]$$[q_{1},2, Z, q3]$

and$[q_{4},2, P, q_{3}]$overlaps in range, while the pairdoes not. As seen from this definition, every ID of a deterministic (reversible, respectively)
CM $(k)$ has at most one ID that immediately follows (precedes) it. Hereafter, we consider only.
deterministic reversible and deterministic irreversible CM$(k)\mathrm{S}$It has been known that an RCM(2) is computation-universal [14].
Proposition 3.1 [14] For any Turing machine
simulates .

$T$, there is a deterministic RCM(2) $M$ that$T$

We need the following Lemma to prove Theorem 3.1, there is a deterministic CM $(2)$Lemma 3.1 For any deterministic CM(2) $M=(2,$ $Q,$ $q0,$$M’=(2,$ $Q’,$
ing the following conditions: (i) The initial statethat simulates
never appears as the fourth element of a quadruple in (hence it appears only at time ).
(ii) If $M$ is reversible then $M’$ is also reversible.
$qf^{)}$$\delta,$$\delta,$$q_{0}’’,$$q_{f^{)}}$$M\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{S}}6^{r}$$0$$\delta’$$q_{0}’$

Proof. In the case $M$ is irreversible, it is very easy to construct such $M’$ by adding a new initialstate to . So, we consider the reversible case. In [14], a construction method of a reversible
CM(2)that simulates a given CM $(k)M_{1}(k=1,2, \cdots)$ (that is not necessarily reversible)
has been shown. By checking the construction method shown in [14], we can verify that
also satisfies it. Hence the Lemma holds.
satisfies the above condition (i), provided that$Q$

$M_{2}$$M_{2}$$\square$$M_{1}$

Theorem 3.1 For any deterministic CM(2) $M$ , there is a deterministic NC-PCA that simulates $M$ satisfying the following condition: If $M$ is reversible then is also reversible.
$A$

$A$

Proof. Without loss of generality, we assume that the state set of $M$ is $Q=\{q_{0}, q_{1}, \cdots, qm-1\}$ ,and the initial and final states are , and $q_{m-1}$ , respectively. Hence,$q_{0}$$M=(2, \{.q0, q1, \cdots, qm-1\}, \delta, q0, q_{m-1})$.

Further assume that never appears as the fourth element of a quadruple in (by Lemma 3.1).
, Nop, andbe the sets of states defined as follows $(j\in\{0,1\})$ .
Let$\delta$$q_{0}$$\mathrm{I}\mathrm{n}\mathrm{c}_{j},$$\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}_{j}$$\mathrm{D}\mathrm{e}\mathrm{c}_{j}$

Incj

$=$

$\mathrm{D}\mathrm{e}\mathrm{c}_{j}$

$=$

Nop

$=$

Testj

$=$

{
{
{
{

$q_{i}|[q_{i},j,$ $+,$ $q_{k}]\in\delta$$q_{i}|[q_{i},j$, -,$q_{k}]\in\delta$$q_{i}|[q_{i},j,$ $0,$ $qk]\in\delta$$q_{i}|[q_{i},j,$ $s,$ $q_{k}1\in\delta$

for some $q_{k}\in Q$ }for some $q_{k}\in Q$ }for some $j\in\{0,1\}$ , and $q_{k}\in Q$ }for some $s\in\{Z,$ $P\}$ , and $q_{k}\in Q$ }ese sets stand for instructions of “increment the counter ”, “decrement the counter ”, “nooperation”, and “test if the counter is zero or positive”. It is easy to see that Incj, Decj, Nop,
, etc.), since $M$ isand Testj are pairwise disjoint (for example,$\mathrm{T}\dot{\mathrm{h}}$

$j$

$j$

$j$

$\mathrm{I}\mathrm{n}\mathrm{c}_{0}\cap \mathrm{I}\mathrm{n}\mathrm{c}_{1}---\emptyset,$

deterministic.

$\mathrm{D}\mathrm{e}\mathrm{c}_{1}\cap \mathrm{N}\mathrm{o}\mathrm{p}=\emptyset$

135

We now construct an NC-PCA that simulates $M$ . Each part of a cell ofat most $m+18$ , and the quiescent state is. Thus,$A$$A$

keeps a number$(0,0, \mathrm{o})$$A=(\mathrm{Z}, \mathrm{N}^{3}m+18’ g, (0,0,0))$.

Before defining the local function , we fix a coding method of an ID of $M$ by a configuration of. First, we assign an “operation code” to each state of $M$ by the }function : $Qarrow$
$g$

$A$

$\mathrm{f}\mathrm{o}$$\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{g}$$\{0,2,4,6,7\}$$\gamma$

.

2 if
4 if
6 if
7 if

$\gamma(q_{i})=\{$$q_{i}\in \mathrm{I}\mathrm{n}\mathrm{c}_{0}$$q_{i}\in \mathrm{D}\mathrm{e}\mathrm{c}0$$q_{i}\in \mathrm{I}\mathrm{n}\mathrm{c}_{1}$$q_{i}\in \mathrm{D}\mathrm{e}\mathrm{c}\mathrm{l}$otherwise
Note that the states in Nop Testo
and the halting states have the same operation code
. We then define a coding function, which maps each ID of $M$ toa configuration of . Let $I=(q_{i}, n0, n1)$ be an ID of $M$ . A configurationis computed by
the following procedure.
$0$$\mathrm{U}$$\mathrm{U}\mathrm{T}\mathrm{e}\mathrm{S}\mathrm{t}_{1}$$0$$\varphi:Q\cross \mathrm{N}^{2}arrow \mathrm{c}_{\mathrm{o}\mathrm{n}}\mathrm{f}(\mathrm{N}^{3}m+18)$$A$$\varphi(I)$

begin$\alpha:=\mathrm{t}\mathrm{h}\mathrm{e}$quiescent configuration;;$\mathrm{P}^{\mathrm{r}0_{L}}(\alpha(0)):=i+10$$\mathrm{p}\mathrm{r}\mathrm{o}_{C}(\alpha(0)):=(m+16)-(i+10)-\gamma(qi)$$\mathrm{p}\mathrm{r}\mathrm{o}_{R}(\alpha(0)):=\gamma(q_{i})$;for each $j\in\{0,1\}$ do
if $n_{j}=0$ andelse prothen$q_{i}\in \mathrm{I}\mathrm{n}\mathrm{c}_{j}$$\mathrm{p}\mathrm{r}\mathrm{o}_{R}(\alpha(.0))$$c(\alpha(n_{j})):=\mathrm{p}\mathrm{r}\mathrm{o}C(\alpha(nj))+2^{g}$;$:=\mathrm{p}\mathrm{r}\mathrm{o}_{R(}\alpha(0))+2^{j}$;$\varphi(I):=\alpha$end.

For example, the configuration$\varphi(q_{i}, 2,0)$such that

Figure 3: The configuration$q_{i}\in \mathrm{I}\mathrm{n}\mathrm{c}_{1}$$\varphi(q_{i}, 2,0)$is shown in Fig. 3.

such that$q_{i}\in \mathrm{I}\mathrm{n}\mathrm{c}_{1}$.

Each configuration
has the number $m+19$ in total. The number kept by the counter$j(j\in\{0,1\})$ is recorded by putting the number(at theat the center part of the cellright part of the cell , if $n_{j}=0$ and the current state is in Incj). The number
is called
a counter marker. The remaining $m+16$ particles are used to record the state of $M$ , and to
execute operations on counters.
In what follows, each state in $\{1, 2, \cdots, m+9\}$ appearing in the left or the right part (not in
the center part) of a cell is called a signal. Signals in $\{10, 11, \cdots, m+9\}$ are called state signals,
and are used to record the current state of $M$ . State signals are kept by the cells and $-1$
(they go back and forth between these cells). Signals in {2, 4, 6, 7} are called operation signals,
which are used to execute
operations. Each of the four operation signals
sometimes carry a counter marker to move it to the right- or left-neighboring cell. At that time,these signals “2”, “4”, “6”, and “7” temporarily become “3”, “5”, “8”, and “9”, respectively.
The signal “1” is a special one called an $initial/final$ signal (it will be explained later).
We now define the local function of as follows.
$\varphi(I)$$n_{j}$$2^{j}$$n_{j}$$2^{j}$$0$$0$$\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}/\mathrm{d}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}$

$g$

$A$

136

1. Rules for the cases where no signal exists:, include the following rule in
For each$x\in \mathrm{N}_{m+18}$$[ 0, x, 0 ]$$g$.

$[ 0, x, 0 ]$$arrow$

2. Rules for state signals:
For each $x\in\{10,11, \cdots,m+9\}$ , include the following rule in$[ 0, 0, x ]$

$g$

(1)

.

$[ 0, 0, x ]$$arrow$(2)

3. Rules for the increment operation:

For each $j\in\{0,1\}$ and $c\in\{0,1\}$ , include the following rules inmod 2).
$[[ 2+2+4j4j,’ 2j+C\cdot 2jC\cdot 2^{i\oplus 1},\oplus 1, 00 ]]$$g(\oplus \mathrm{d}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{S}$the addition in$[[ 00,’ c\cdot 2^{j\oplus 1}c\cdot 2^{j1}\oplus’ 2+4j ]$$arrowarrow$$2+4j+2^{j}]$,$[2+4j,$$[[2+4j,2^{j}0^{+}’ c\cdot 2^{j\oplus 1}c\cdot 2^{j1}\oplus’, 2+4j0] arrow [2+4j, c\cdot 2^{j\oplus 1}, 00 ]]$$(3..1)$(3.2)$2^{j}+c\cdot 2^{j\oplus}’ 1$$arrow$$]$$(3.3)(3.4)$

4. Rules for the decrement operation:
For each $j\in\{0,1\}$ and $c\in\{0,1\}$ , include the following rules in .
$g$[$[[[4+4+,,3j003j,’ 2j+.c \cdot 2j’,’\oplus c.2^{j\oplus 1}c\cdot 2C2^{j1}j\oplus 1\oplus 1, 4+3j00 ]] arrowarrow [[4+3j+,2^{j}4+34+30,jj" 2^{j}+c\cdot.2^{j1}cc\cdot 2^{j1^{\oplus}}C2j.\oplus 1\bigoplus_{\oplus}2j’,, 1, 4+3j000]]]$
$]$

$[$

$4+3j+2^{j}]]$$arrowarrow$$(4^{\cdot}.2)(4(44)1)$

(4.3)

[

operation:
5. Rules for waiting for the completion of thesuch that $d\in\{+$ , , and for each $c\in\{0,1\}$ , include the following
For each$\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}/\mathrm{d}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}$$[q_{i},j, d, q_{k}]\in\delta$

rule in$g$- $\}$.

$[i+10, (m+16)-(i+10)-\gamma(q_{i})+c\cdot 2^{j\oplus 1}, 0]$$arrow$(5)$[i+10, (m+16)-(i+10)-\gamma(q_{i})+c\cdot 2^{j\oplus 1}, 0]$

6. Rules for simulating
For eachstate transition from a state in Incj:, then include the following rule inand $c\in\{0,1\}$ , if

$M’ \mathrm{s}$$[q_{i},j, +, q_{k}]\in\delta$$[i+10, (m+16)-(i[k+1\overline{\mathrm{o}}+10), \gamma(m+16)(qi)+c\cdot 2-j\oplus 1(k’+10)^{)}-\gamma\gamma(q_{i}](q_{k})arrow+c\cdot 2^{j\oplus 1}, \gamma(q_{k}) ]$For each$[q_{i},j, +, q_{k}]\in\delta$

and $c\in\{0,1\}$ , if$q_{k}\in \mathrm{I}\mathrm{n}\mathrm{c}j\oplus 1$

For eachrule in .

.

(6.1)

, then include the following rule in .
$g$$[i+10, (m+16)-(i+[k+1\overline{\mathrm{o},}(m10)\gamma(qi)+c\cdot 2^{j\oplus 1}+16)-(k’+10)\gamma(qi)]-\gamma(q_{k})arrow, \gamma(q_{k})+c\cdot 2^{j\oplus 1} ]$7. Rules for simulating$g$$q_{k}\not\in \mathrm{I}\mathrm{n}\mathrm{c}j\oplus 1$(6.2)

state transition from a state in Decj:, then include the following
and $c’\in\{0,1\}$ , if

$M’ \mathrm{s}$$[q_{i},j, -, q_{k}]\in\delta$$c,$$q_{k}\not\in(\mathrm{I}\mathrm{n}\mathrm{c}_{jj\oplus 1}\mathrm{U}\mathrm{I}\mathrm{n}\mathrm{c})$$g$$[i+10, (m+16)-(i+10)-\gamma(q_{i})+d\cdot 2^{j\oplus 1}, \gamma(q_{i})+c\cdot 2^{j} ]$$arrow$$[ k+10, (m+16)-(k+10)-\gamma(q_{k})+c\cdot 2^{j}+c’\cdot 2^{j\oplus 1}, \gamma(q_{k}) ]$For each$[q_{i},j, -, q_{k}]\in\delta$

and

$c,$

$c’\in\{0,1\}$, if$q_{k}\in \mathrm{I}\mathrm{n}\mathrm{c}_{j}$, then include the following rule in$[ i+10, (m+16)-(i+10)-\gamma(q_{i})+c’\cdot 2j\oplus 1, \gamma(q_{i})+c\cdot 2^{j} ]$$[q_{i},j, -, q_{k}]\in\delta$

and

$c,$

$d\in\{0,1\}$, if$q_{k}\in \mathrm{I}\mathrm{n}\mathrm{c}_{j\oplus 1}$$g$.

$arrow$$[ k+10, (m+16)-(k+10)-\gamma(q_{k})+c’\cdot 2^{j\oplus 1}, \gamma(q_{k})+c\cdot 2^{j} ]$For each

(7.1)

(7.2)

, then include the following rule in$[i+10, (m+16)-(i+10)-\gamma(q_{i})+d\cdot 2^{j\oplus 1}, \gamma(q_{i})+c\cdot 2^{j} ]$$g$$arrow$$[k+10, (m+16)-(k+10)-\gamma(q_{k})+c\cdot 2^{j}, \gamma(q_{k})+d\cdot 2^{j\oplus 1} ]$

(7.3)

.

137

8. Rules for simulating
For eachin .

state transition from a state in Nop:
and $d\in\{0,1\}$ , if
, then include the following rule$M’ \mathrm{s}$$[q_{i},j, 0, qk]\in\delta$$c,$$q_{k}\not\in(\mathrm{I}\mathrm{n}\mathrm{c}0^{\cup}\mathrm{I}\mathrm{n}\mathbb{C}1)$$g$$[ i+10, (m+16)-(i+10)+c\cdot 2^{0}+c’\cdot 2^{1}, 0 ]$$arrow$(8.1)$[ k+10, (m+16)-(k+10)-\gamma(qk)+c\cdot 2^{0}+d\cdot 2^{1}, \gamma(q_{k}) ]$For each $[q_{i},j, 0, qk]\in\delta$ andrule in .

$c,$

, if

$c’\in\{0,1\}$$q_{k}\in \mathrm{I}\mathrm{n}\mathrm{c}_{j}$for some , then include the following
$j$

$g$

$[i+10, (m+16)-(i+10)+c\cdot 2^{jj\oplus}+d\cdot 21, 0]$$arrow$(8.2)$[ k+10, (m+16)-(k+10)+\gamma(qk)+c’\cdot 2^{j\oplus 1}, \gamma(q_{k})+c\cdot 2^{j} ]$9. Rules for simulating
For each [in .

state transition from a state in Testj:
and $c\in\{0,1\}$ , if
, then include the following rule$M’ \mathrm{s}$$q_{i},j,$ $z_{q_{k}]},\in\delta$$qk\not\in(\mathrm{I}\mathrm{n}\mathrm{c}_{j^{\cup}.j\oplus 1}\mathrm{I}\mathrm{n}\mathrm{c})$$g$$[ i+10, (m+16)-(i+10)+2^{j}+c\cdot 2^{j\oplus 1}, 0 ]$$arrow$(9.1)$[ k+10, (m+16)-(k+10)-\gamma(qk)+2j+c\cdot 2j\oplus 1, \gamma(q_{k})]$For each [in .

$q_{i},j,$ $z_{q_{k}]},\in\delta$

such that and $c\in\{0,1\}$ , if$q_{k}\in$

Incj, then include the following rule$g$$[i+10, (m+16)-(i+10)+2^{j}+c\cdot 2^{j\oplus 1}, 0 ]$$arrow$(9.2)$[ k+10, (m+16)-(k+10)-\gamma(qk)+c\cdot 2^{j\oplus 1}, \gamma(q_{k})+2^{j}]$For each [$q_{i},j,$ $z_{q_{k}]},\in\delta$

and $c\in\{0,1\}$ , if$q_{k}\in \mathrm{I}\mathrm{n}\mathrm{c}_{j\oplus 1}$$[i+10, (m+16)-(i+10)+2j+c\cdot 2j\oplus 1, 0]$, then include the following rule in$[q_{i},j, P, q_{k}]\in\delta$

and $c\in\{0,1\}$ , if$q_{k}\not\in \mathrm{I}\mathrm{n}\mathrm{c}_{j\oplus 1}$$[i+10, (m+16)-(i+10)+c\cdot 2^{j\oplus 1}, 0]$$[q_{i},j, P, q_{k}]\in\delta$

and $c\in\{0,1\}$ , if$g$$arrow$$q_{k}\in \mathrm{I}\mathrm{n}\mathrm{c}_{j\oplus 1}$$[i+10, (m+16)-(i+10)+c\cdot 2^{j}\oplus 1, 0]$(9.3), then include the following rule in .

$[ k+10, (m+16)-(k+10)-\gamma(qk)+C\cdot 2^{j\oplus 1}, \gamma(q_{k})]$For each.

$arrow$$[ k+10, (m+16)-(k+10)-\gamma(qk)+2^{j}, \gamma(q_{k})+\mathrm{C}\cdot 2^{j}\oplus 1]$

For each

$g$

(9.4)

, then include the following rule in .
$g$$arrow$$[ k+10, (m+16)-(k+10)-\gamma(qk), \gamma(q_{k})+C\cdot 2^{j}\oplus 1]$(9.5)

10. Rules for thesignal:Include the following rules in .
$\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{a}\mathrm{l}/\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}$$g$$[ 1, 0, 0 ]$$[ 0, 0, 1 ]$For each$c,$$c’\in\{0,1\}$, if$arrow$$arrow$$q_{0}\not\in(\mathrm{I}\mathrm{n}\mathrm{c}0\cup \mathrm{I}\mathrm{n}\mathrm{c}\mathrm{l})$$[ 0, 0, 1 ]$$[ 1, 0, 0 ]$(10.1)(10.2), then include the following rule in .
$g$$[ 1, (m+15)+C\cdot 20_{+}C’\cdot 21, 0]$$arrow$$[ 10, (.m+16)-10-\gamma(q_{0})+c\cdot 2^{0}+c’\cdot 2^{1}, \gamma(q_{0}) ]$For each$c,$$d\in\{0,1\}$, if$q_{0}\in \mathrm{I}\mathrm{n}\mathrm{c}_{j}$for some , then include the following rule in .
$j$$[ 1, (m+15)+C\cdot 2j+c’\cdot 2^{j\oplus}1, 0]$[ 10,

For each$c,$$c’\in\{0,1\}$(10.3)$g$$arrow$$\gamma(q\mathrm{o})+c\cdot 2^{j}\rfloor 1$(10.4)$[ 1, (m+15)+c\cdot 2^{0}+d\cdot 2^{1}, 0]$(10.5)$(m+16)-10-\gamma(q_{0})+c’\cdot 2j\oplus 1,$, include the following rule in .
$g$$[ (m+9), (m+16)-(m+9)+c\cdot 20_{+}2C’\cdot 1, 0]$$arrow$

138

We can see that correctly simulates $M$ step by step. It is easy to verify that each ruleconserves the total number between left- and right-hand sides, and hence is an NC-PCA.
Now, we show that the following statement holds: If $M$ is reversible, so is . Assume $M$
is reversible. It suffices to show that each of the above rules has a different right-hand sidefrom those of the other rules. First, we can easily verify that rules (1), (2), $(3.x),$ $(4.x),$ $(10.1)$ ,(10.2), and (10.5) satisfy this constraint by simply comparing their right-hand sides with otherrules. The rules (10.3), and (10.4) are also so. Because the state does not appear as the forthelement of a quadruple in , hence the right-hand sides of these rules never matches those of$(6.x),$ $(7.x),$ $(8.x)$ , and $(9.x)$ , as well as the others.
Next, we consider the rules (5), which correspond to the quadruple $[q_{i},j, d,qk]\in\delta$ such that$d\in\{+$ ,. The state may appear as the fourth element of the other quadruples. But, since$\gamma(q_{i})>0$ (because), the right-hand sides of the rules (5) neverIncl$(9.x)$$(8.x)$$(7.x),$$(6.x),$
.
,
and
of
those
match
the reversibility constraint.
that rules $(6.x),$ $(7.x),$ $(8.x)$ , andWe finally$M$ defined as follows.
ofofstates
sets
be
the
Nop’,
Dec’,
Test’
Inc’,
and
Let
$A$

$A$

$A$

$q_{0}$$\delta$- $\}$$q_{i}$$\cup \mathrm{D}\mathrm{c}_{0^{\mathrm{U}\mathrm{D}}1}\mathrm{e}\mathrm{e}\mathrm{C})$$q_{i}\in(\mathrm{I}\mathrm{n}\mathrm{C}_{0^{\cup}}$$(9.x)\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{S}}\mathrm{p}$$\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\theta$

Inc’
Dec’

{
{
{
{

$=$
$=$
$=$

$\mathrm{N}\mathrm{o}\mathrm{p}’$

Test’

$=$

$q_{k}|[q_{i},j,$ $+,$ $q_{k}]\in\delta$$q_{k}|[q_{i},j$, -,$q_{k}]\in\delta$$q_{k}|[q_{i},j,$ $0,$ $q_{k}]\in\delta$$q_{k}|[q_{i},j,$ $s,q_{k}]\in\delta$

for some $j\in\{0,1\}$ , andfor some $j\in\{0,1\}$ , andfor some $j\in\{0,1\}$ , andfor some $j\in\{0,1\},$ $s\in\{Z,$}}}$q_{i}\in Q$$q_{i}\in Q$$q_{i}\in Q$
$P\}$

, and

$q_{i}\in Q$}

as the fourth(Inc’ Dec’ Nop’) there is exactly one quadruple containing
For each$[qi,j,d,qk](q_{i}\in
Q,j\in\{0,1\}$ ,$M$
is reversible (thus the quadruple is of the form
element, since$(8.x)$$(7.x)$
quadruple$d\in$ $\{-, 0, +\}))$ .
$(6.x),$
tothiscorresponding, andHence, the rules in
Test’,
at mostare
there
have different right-hand sides from the others. Next, for each$M$
is reversible. They are of the form
as the fourth element since
two quadruples containing$[q_{i},j, s, q_{k}](q_{i}\in Q,j\in\{0,1\}, s\in\{Z, P\})$ . If there is only one, the rules in $(9.x)$ corresponding
to this quadruple satisfy the reversibility constraint as above. In the case there are two, they
, because $M$ is reversible. We can see the rules
andmust be of the forms
in $(9.1)-(9.3)$ , and $(9.4)-(9.5)$ corresponding to the two rules have mutually different right-handsides, because the center part of the cell should be different between two cases of the contentsof the counter . They also differs from the other rules.
By above, each rule in has different right-hand side from the others, and thus weconclude that if $M$ is reversible, is also reversible.
$q_{k}\in$$\cup$$\mathrm{U}$$q_{k}$$q_{k}\in$$q_{k}$$[q_{i}’,j’, P, q_{k}]$$[q_{i},j, Z, q_{k}]$

$0$

$j$

$g$

$\mathrm{c}\mathrm{a}\mathrm{n}\square$$A$

Example 3.1 Consider a deterministic RCM(2) $M_{2}=(2, Q, \{Z, P\}, \delta, q_{0,q6})$ having the followi.ng quadruples as .
$\delta$$[q_{0}, 1, Z, q_{1}]$$[q_{3}, 1, +, q_{4}]$$[q_{1}, 0, Z, q_{6}]$$[q_{4}, 1, +, q_{5}]$$[q_{1}, 0, P, q_{2}]$$[q_{5}, 1, P, q_{1}]$$[q_{2}, 0, -, q_{3}]$for any $n(=0,1, \cdots)$ . An NC-RPCA
performs the computationby the method given in Theorem 3.1 is as follows.
constructed from$M_{2}$$(q_{0}, n, 0)\vdash_{M_{2}}^{*}(q_{6},0,2n)$$A_{2}$$M_{2}$$A_{2}=(\mathrm{Z}, \mathrm{N}_{25}^{3},g_{2}, (0,0,0))$The local function$(q_{0},2,0)\vdash_{M_{2}}^{12}(q_{6},0,4)$

is defined by the following set of rules, and a simulation process of
is shown in Fig. 4.

$g_{2}$

139

Rules by (1) $(x\in\{0,1, \cdots , 25\})$ :$[0, x, 0]$$arrow$$[0, x, 0]$Rules by (2) $(y\in\{10,11, \cdots , 16\})$ :$[0, 0, y]$$arrow$

Rules by (3.1):$[2, 0, 0]$$[2, 2, 0]$$[6, 0, 0]$$[6, 1, 0]$$arrow$$arrow$$arrow$$arrow$

Rules by (3.2):$[2, 1, 0]$$[2, 3, 0]$$[6, 2, 0]$$[6, 3, 0]$$arrow$$arrow$$arrow$$arrow$

Rules by (3.3):$[3[3,’ 20,’ 00]$$[8, 0, 0]$$[8, 1, 0]$Rules by (4.1):
4, ,
]
4, 2,
]
$0$

$arrowarrow$$arrow$$arrow$$arrow$$arrow$$arrow$$arrow$$arrow$$0$$arrow$$\{$$arrow$$arrow$

Rules by (4.2):$[4, 1, 0]$$[4, 3, 0]$$[7, 2, 0]$$[7,by3, (4.3):
0]$
Rules
$[0, 0, 5]$$[0, 2, 5]$$[0, 0, 9]$$[0,by1, (4.4):
9]$
Rules
$[0, 0, 4]$$[0,$[0, 2,0, 4]$
7]$$[0, 1, 7]$$[0, 0, 3]$$[0, 2, 3]$$[0, 0, 8]$$[0, 1, 8]$$arrow$$arrow$$[12, 7, 0]$$[12, 9, 0]$Rules by (5) for $[q3,1, +, q4]$ :$[13, 4, 0]$$[13, 5, 0]$$arrow$$arrow$$[13, 4, 0]$$[13, 5, 0]$Rules by (5) for $[q4,1, +, q5]$ :$[14, 3, 0]$$arrow$$[14, 3, 0]$

14, 4, . $0]$$[14, 4, 0]$Rules by (6.1) for $[q3,1, +, q4]$ :[13, 4, 6][14, 3, 6][13, 5, 6][14, 4, 6]
Rules by (6.1) for $[q4,1, +, q5]$ :[14, 3, 6]$[15, 8, 0]$[14, 4, 6]$[15, 9, 0]$$arrow$$[$$arrow$$arrow$$arrow$$[2[2,, 31,, 0]0]$$[6, 2, 0]$$[6, 3, 0]$$[2, 0, 0]$$[2, 2, 0]$$[6, 0, 0]$$[6, 1, 0]$$\mathrm{R}\mathrm{u}1\mathrm{e}[\mathrm{l}2\mathrm{s},,\mathrm{b}\mathrm{y}$$7,4(7.3)\mathrm{f}\mathrm{o}\mathrm{r}$[12, 7, 5][12, 9, 4][12, 9, 5]
Rules by (9.1) for$arrow[13[q2,0,-,’ q3]4, 6]$

5, 6]
4, 8]
5, 8]
:
$[11, 14, 0]$$[10, 15, 0]$$[11, 15, 0]$$[10, 16, 0]$Rules by (9.1) for $[q1,0, Z, q6]$ :$[11, 13, 0]$$[16, 8, 0]$$[16, 10, 0]$$[11, 15, 0]$Rules by (9.4) for $[q1,0, P, q2]$ :[12, 7, 4]$[11, 12, 0]$[12, 9, 4]$[11, 14, 0]$$[q5,1,P, q1]$ :
(9.4)
by
for
Rules
$[11, 12, 0]$$[15, 8, 0]$$[11, 13, 0]$$[15, 9, 0]$Rules by (10.1) and (10.2):$arrow$$arrow$$arrow$

[13,
[13,
[13,

$[q\mathrm{O}, 1, Z, q1]$

$arrow$$arrow$$arrow$$0$$[7, 0, 0]$$[7, 1, 0]$$[0, 0, 2]$$[0, 2, 2]$$[0, 0, 6]$$[0, 1, 6]$$[12, 7, 0]$$[12, 9, 0]$$arrow$

Rules by (3.4):$[0, 0, 2]$$[0, 2, 2]$$[0, 0, 6]$$[0, 1, 6]$$[0, 0, y]$Rules by (5) for $[q2,0, -, q3]$ :$arrow$$arrow$$arrow$$arrow$$arrow$$arrow$$arrow$$arrow$$arrow$$arrow$$arrow$$arrow$$[0, 0, 4]$$[0, 2, 4]$$[0, 0, 7]$$[0, 1, 7]$$[5, 0, 0]$$[5, 2, 0]$$[9, 0, 0]$$[9, 1, 0]$$[4, 1, 0]$$[4, 3, 0]$$[7, 2, 0]$$[7, 3, 0]$$[4, 0, 0]$$[4,$[7, 2,0, 0]$
0]$$[7, 1, 0]$$arrow$$arrow$$arrow$$arrow$$arrow$$[0[1,’ 0, 0]$]
.

$0,$

$1$

$arrow$$[0,$$arrow$[1,

Rules by (10.3):$[1, 22, 0]$$[1, 23, 0]$’$|11,$’$2524,$$00]$$arrow$$arrow$$arrowarrow$

$00,$

,

$01|$

$[10, 13, 0]$$[10, 14, 0]$$[10[10,, 1615,, 0]0]$

Rules by (10.4):$[16,$[16, 7,8, 0]$
0]$$[16, 9, 0]$$[16, 10, 0]$$arrow$$arrow$$arrow$$arrow$$[1, 2223,’ 0]0]$[1,$[1, 24, 0]$

I 1,

25,

$0$

]

140

Figure 4: A simulation process of an RCM(2)$M_{2}$

by an NC-RPCA$A_{2}$.

141

From Lemma 3.1 and Proposition 3.1, universality of an NC-RPCA is concluded.
Corollary 3.1 An NC-RPCA is computation-universal.

4

Concluding Remarks

In this paper, we proved that an NC-RPCA can simulate a reversible two-counter machine,
hence it is computation-universal. In [10], universality of an RCA (not necessarily numberconserving) has been shown by simulating a one-tape reversible Turing machine by an RCA.
It is also possible to simulate a one-tape reversible Turing machine by an NC-RPCA. But, if
we employ a simulation method in which the contents of each tape square are stored in eachcell, then the quiescent state of the NC-RPCA should be $(0, m, 0)$ for some $m>0$ rather than$(0,0,\mathrm{o})$.

References[1] Albert, J., and Culik II, K., A simple universal cellular automaton and its one-way and totalistic
version, Complex Systems, 1, 1-16 (1987).

[2] Bennett, C.H., Logical reversibility of computation, IBM J. Res. Dev., 17, 525-532 (1973).
[3] Bennett, C.H., Notes on the history of reversible computation, IBM J. Res. Dev., 32, 16-23 (1988).
[4]”$\mathrm{a}\mathrm{S}\mathrm{n}_{\mathrm{M}}\mathrm{R}\mathrm{P}\mathrm{s}$$\mathrm{R}\mathrm{e}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{F}\mathrm{e}\mathrm{y}\mathrm{n}\mathrm{m}\mathrm{a}\mathrm{n}\mathrm{g},$’$FeynmanL(1996).$($\text{邦邦訳訳^{}t}\text{フファ}eurn\text{ァ}$イインンママンン計計算算機機科科学学 A」」.J,. 岩岩波波 He 書書 y, 店店 and19R99))$))\mathrm{A}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{n})$, Perseus Books,[5] Fredkin, E., and Toffoli, T., Conservative logic, Int. J. Theoret. Phys., 21, 219-253 (1982).

[6] Goles, E., Sand pile automata,nn. Inst. Henri Poincar\’e, 56, 75-90 (1992).
[7] Goles, E., and Margenstern, M., Sand pile as a universal computer, Int. J. Modern Physics C, 7,
113-122 (1996).
$\dot{A}$[8] Imai, K., and Morita, K., A
two-dimensional 8-state triangular reversible cellular automaton, Proc. of the Second Colloquium on Universal Machines and Computations, Volume
II (Metz), 90-99 (1998). (to appear in Theoret. Comput. Sci.)[9] Margolus, N., Physics-like model of computation, Physica, 10D, 81-95 (1984).
[10] Morita, K., and Harao, M., Computation universality of one-dimensional reversible (injective) cellular automata, Rans. IEICE Japan, E-72, 758-762 (1989).
[11] Morita, K., and Ueno, S., Computation-universal models of two-dimensional 16-state reversible
cellular automata, IEICE $\pi ans$ . Inf. Syst., E75-D, 141-147 (1992).
[12] Morita, K., Computation-universality of one-dimensional one-way reversible cellular automata, Inform. Process. Lett., 42, 325-329 (1992).
[13] Morita, K., Reversible cellular automata (in Japanese), J. Information Processing Society Japan,of35, 315-321 (1994).
$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}-\mathrm{u}\mathrm{n}\mathrm{i}_{\mathrm{V}\mathrm{e}}\mathrm{r}\mathrm{s}\mathrm{a}1$$\xi j$[14] Morita, K., Universality of a reversible two-counter machine, Theoret. Comput. Sci., 168, 303-320(1996).
[15] Morita, K., and Imai, K., Self-reproduction in a reversible cellular space, Theoret. Comput. Sci.,
168, 337-366 (1996).

[16] Morita, K., Margenstern, M., and Imai, K., Universality of reversible hexagonal cellular automata,
MFCS’98 Workshop on Rontiers between Decidability and Undecidability, Bmo (1998).
[17] Morita, K., Cellular automata and artificial life-Computation and life in reversible cellular automata-, Proc. of the 6th Summer School on Complex Systems, Santiago, 1-40 (1998).
[18] Toffoli, J., Computation and construction universality of reversible cellular automata, J. Comput.
Syst. Sci., 15, 213-231 (1977).

[19] Toffoli, T., and Margolus, N., Invertible cellular automata: a review, Physica D, 45, 229-253 (1990).