数理解析研究所講究録1093 巻 1999 年 206-211

206

3 次元可逆自己増殖セルオートマトンについて
堀貴博 , 今井克暢, 森田憲– f$\dagger$\dagger NEC アイシーマイコンシステム
thori@nims.nec.co.jp\d ag er 広島大学工学部{imai,

1$\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{a}$}$@\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}.\mathrm{i}\mathrm{p}$Introduction, self-reproduction can be performed withIn
out garbage in two-dimensional reversible cellular$SR_{8}$A reversible cellular automaton (RCA) is one of
the reversible computing models. Its global function is injective and every configuration has at
most one predecessor. Intuitively, it “remembers”
the initial configuration and one can reconstruct
its initial configuration from a configuration of
any time. So reversible property is a strong constraint and one cannot generate nor extinct signals
freely. Toffoli showed that there exist computationand the BBM cellular automauniversal. It(BBMCA),ton
was introduced byrelationadirectcomputation-universal
and
it
has
is
with a physical reversible and conservative comput) . The Billiard
ing model (the Billiard Ball
Ball Model (BBM) has an important aspect that it
is possible to compute any function without dissipation of balls as garbage. Once von Neumann conjectured that computing without erasing information
is impossible and erasing one-bit information must
dissipate at least $ln2kT$ joules of energy. But the
BBM is a conservative model and it is possible toconstruct a computer that can computes with noenergy dissipation in principle.
This fact means garbage collection can be performed with reversed sub-computations and suchgarbage collector can be constructed with reversible
manner. This technique is first introduced by Bennett. He showed that his reversible Turing machineis computation-universal and garbage collection can. But thebe implemented in reversible
fact does not mean any computing process can be. Especially,
simulated effectively in
it is very difficult to place a preferred initial configuration and start computing on reversible computing
models. This problem is described as a restrictionof generation and extinction of signals in RCAs, andsynchronizing signals and distributing specific patterns on RCAs are also quite difficult.
So we proposed a simple self-reproducing RCA.
based on a shape-encoding mechanism$\mathrm{R}\mathrm{C}\mathrm{A}\mathrm{s}[13]$$\mathrm{M}\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{s}[7]$$\mathrm{M}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{l}$$[3]$$\mathrm{m}\mathrm{a}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}[1,2]$$\mathrm{r}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}[10,4]$$(SR_{8})1^{1}1]$

space.
into threeIn this paper, we extend
dimensional reversible cellular sp\‘ace. Even if its cellular space is reversible, it can self-reproduce various three-dimensional patterns wi.thout garbage dissipation. In order to design an RCA we use a framework of partitioned cellular automaton (PCA). In
the next section, first we define PCA.
$SR_{8}$

Definitions

2

is rePartitioned cellular automaton
automacellulargarded as the subclass of standard
ton. Each cell is partitioned into the equal numberof parts to the neighborhood size and the information stored in each part is sent to only one of theneighboring cells (Fig. 1). In PCA, injectivity of
global function is equivalent to injectivity of local
function, thus a PCA is reversible if its local function is injective. Using PCA, we can construct areversible CA with ease.
two-dimensional partitioned celA
lular automaton (PCA) $P$ is defined by$(\mathrm{P}\mathrm{C}\mathrm{A})[8]$$dete\Gamma min\dot{i}sti_{C}$$P=(\mathrm{Z}^{2}, (C, U,R, D, L), \varphi, (\#, \#, \#, \#, \#))$

whereis the set of all integers, $C,$ $U,$ $R,$ $D,$ are
non-empty finite sets of center, up, right, down, leftparts of each cell,: $C\cross D\cross L\mathrm{x}U\cross Rarrow$$C\cross U\mathrm{x}R\cross D\mathrm{x}L$is a local function (Fig.2),
$(\#,
\#,
\#,
\#,
\neq)\inC\mathrm{x}U\mathrm{x}R\crossD\cross L$ is aandquiescent state which satisfies $\varphi(\#, \#, \#, \#. ’\#)=$$L$$\mathrm{Z}$$\varphi$$(\#, \#, \#, \#, \neq)$.

is a
A configuration over
Conf
. Let
mapping$U\cross R\cross D\cross L)$ denote the set of all configurations$C\cross U\mathrm{x}R\mathrm{x}D\cross L$$c:\mathrm{Z}^{2}arrow C\cross U\cross R\cross D\cross L$

over$C\cross U\mathrm{x}R\mathrm{x}D\cross L$.

Conf $(C\cross U\cross R\cross D\cross L)=$$\{c|c :\mathrm{Z}^{2}arrow C\cross U\cross R\cross D\cross L\}$$(C\cross$207

Globa! function$\Phi_{A}$Let Confof all cnfigurations over$(C\cross U\cross R\cross D\cross L\mathrm{X}p_{\mathrm{X}}B)$: Conf $(C\cross U\cross R\cross D\mathrm{x}L)$

denote the set$C\cross U\cross R\cross D\cross L\cross F\cross B$.

Conf $(C\cross U\cross R\cross D\cross L\cross F\cross B)=$$arrow \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{f}(C\cross U\cross R\cross D\cross L)$$\{c|c:\mathrm{Z}^{3}arrow C\cross U\cross R\cross D\cross L\cross F\cross B\}$is defined by$\Phi_{A}(c)(X)=\varphi(\mathrm{C}\mathrm{E}\mathrm{N}\mathrm{T}\mathrm{E}\mathrm{R}(c(x,y))$Global function is also defined in the same way asin the two-dimensional case.

,

DOWN$(C(x, y+1))$ ,LEFT $(c(x+1,y))$ ,UP $(c(_{X},y-1))$ ,RIGHT $(c(x-1,y)))$where CENTER (UP, RIGHT, DOWN, LEFT, respectively) is the projection function which picks
out the center (up, right, down, left) element of aquintuple in. It has been provedthat $P$ is reversible iff is.
$P$ iscalled a rotation-symmetric (or isotropic)
PCA iff (i) and (ii) hold.
(i) $U=R=D=L$ .

Figure 3: Domain and rage of local function in-neighbor PCA.

$3\mathrm{D}$$7$$C\cross U\cross R\cross D\cross L$$\mathrm{o}\mathrm{n}\triangleright \mathrm{t}_{0}-o\mathrm{n}\mathrm{e}[8]$$\varphi$(ii) $\forall(c, u, r, d, l),$ $(c’,urd^{;}’,’,, l’)\in C\cross U^{4}$ :if $g(c, d, l,u, r)$$(c’,urd”,’,, l’)$$=$$g(c, r, d, l, u)=(c’, l’,du’,r’,’)$ .

then

3

Self-reproduction in a twodimensional RPCA

3.1

Definition of$SR_{8}$In this section, we construct non-trivial selfreproducing structures can be constructible in areversible cellular space. The idea of our modelis based on Langton’s sheathed, andto achieve more flexibility we introduced a selfinspection method.
In the cellular space of $SR_{8}[11]$ , encoding theshape of an object into a “gene” represented by acommand sequence, copying the gene, and interpreting the gene to create an object, are all performed reversibly. By using these operations, various objects called Worms and Loops can reproduce
themselves in a very simple manner.
”
The RPCA
is defined by$\mathrm{L}\mathrm{o}\mathrm{o}\mathrm{p}[6]$Figure 1: Cellular space of PCA.
$\copyright_{u}r$$rua_{1\cdot \mathrm{b}-)}e\iotaarrow ld\mathrm{E}$(Figure 2: A representation of a rule.

$‘ SR_{8}$$SR_{8}=(\mathrm{Z}, (C, U, R, D, L),g, (\#, \#, \#, \#, \#))$,$C=U=R=D=L=\{\#, *, +, -, \mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D}\}$A deterministic three-dimensional partitioned cellular automaton (PCA)
is also defined by$P_{3}$

Hence, each of five parts of a cell has 8 states. The
statesandmainly act as signals thatare used to compose “commands”. The,
and –are used to control these signals. The local
function contains 765 rules. It
a one-to-one
mapping and.
$\mathrm{A},$$\mathrm{B},$$\mathrm{C}$$\mathrm{D}$$\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{s}*,$$P_{3}=(\mathrm{Z}^{3},$$(C, U, R, D, L, F, B),$$\varphi 3$,$(\#, \#, \#, \#, \#, \neq, \#))$

.

$+$

is.

$g$

$\mathrm{r}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}arrow \mathrm{s}\mathrm{y}\mathrm{m}\mathrm{m}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{c}$where is the set of all integers, $C,$ $R,$ $D,L,$ $F,$ $B$
are non-empty finite sets of center, up, right,
down, left, forward, back parts of each cell,:$U,$$\mathrm{Z}$Signal transmission on a Wire

3.2$\varphi_{3}$$C\cross D\cross L\mathrm{x}U\cross R\cross B\cross Farrow C\cross U\cross$$R\mathrm{x}D\cross L\cross F\cross B$

is a local function (Fig.3),

and $(\#, \#, \#, \#, \#, \#, \#)\in C\cross U\cross R\cross D\cross$$L\mathrm{x}F\cross B$
is a quiescent state which satisfies.

$\varphi_{3}(\#, \#, \#, \#, \neq, \#, \#)=(\#, \#, \neq, \#, \#, \#, \#)$A configuration overis a mapping$C\mathrm{x}U\cross R\cross D\cross L\cross F\cross B$$c:\mathrm{Z}^{3}arrow C\cross U\cross R\cross D\cross L\cross F\cross B$.

A wire is a configuration to transmit signals,
and C. Fig. 4 shows an example of a part of a simple(i.e., non-branching) wire.
A command is a signal sequence composed of two
signals. There are six commands consisting of signals
and as shown in Table 1. These commands are used for extending or branching a wire.
$\mathrm{A},$$\mathrm{A},$$\mathrm{B}$$\mathrm{C}$$\mathrm{B}$208

Figure 4: Signal transmission on a part of a simple.
wire$(x_{i},y_{i}\in\{\mathrm{A},\mathrm{B},\mathrm{C}\})$

Table 1: Six commands composed of

3.3$\mathrm{A},$$\mathrm{B}$, and C.

A WormA Worm is a simple wire with open ends that are
called a head and a tail. It crawls in the reversible
cellular space as shown in Fig. 5.
Commands in Table 1 are decoded and executedat the head of a Worm. That is, the command
AA extends the head straight, while the command, respectively) extends it leftward (rightAB (orward). On the other hand, at the tail cell, the shapeof the Worm is “encoded” into an advance command. That is, if the tail of the Worm is straight (orleft-turning, right-turning, respectively) in its form,) is generated. The tailthe command AA (AB,.
then retracts by one

Figure 5: Behavior of a Worm.

$\mathrm{A}\mathrm{C}$$\mathrm{A}\mathrm{C}$$\mathrm{c}\mathrm{e}\mathrm{U}$Self-reproduction of a Worm
By giving a branch command, any Worm can self-

3.4

reproduce indefinitely provided that it neither cycles nor touches itself in the branching process.

Self-reproduction of a Loop
A Loop is a simple closed wire, thus has neither ahead nor a tail as shown in Fig. 6.
If a Loop contains only advance or branch com-

3.5

mands, they simply rotate in the Loop and self-

Figure 6: An example of a Loop.

209$\ovalbox{\tt\small REJECT}_{\mathrm{D}\mathrm{c}\mathrm{E}\mathrm{C}}^{\mathrm{D}\mathrm{B}}\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{a}\circ \mathrm{n}\mathrm{t}\mathrm{e}\mathrm{a}\mathrm{n}_{\mathrm{h}\mathrm{h}\mathrm{a}\mathrm{p}\mathrm{e}}\mathrm{d}\mathrm{e}\mathrm{t}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{m}\mathrm{s}\mathrm{o}\mathrm{f}$aLoop

Table 2: Commands DB and$\mathrm{D}\mathrm{C}$.

reproduction does not occur. In order to make a
Loop self-reproduce, commands in Table 2 are used.
By putting a command DB at an appropriate position, every Loop having only AA commands in all
the other cells can self-reproduce in this way. WhenDB reaches the bottom right corner, it starts making an “arm” and this corner become a transmitter of commands. First, all AA commands in themother Loop are transmitted through the arm andgenerated DC commands encode whole shape of themother Loop into command sequences simultaneously and these commands are transmitted after all
static AA commands are transmitted. Finally DC
commands reaches the bottom rightand thearm is split from the mother Loop.

corne.r

3.6

Controlling the position
daughter Loops inof$SR_{8}$One of our main motivations is to place preferredinitial patterns to a reversible cellular space. As
mentioned above, a closed Loop has only AA commands. If AB or AC commands are placed in theLoop, generated position of the daughter Loop canbe changed.
But DB (create an arm command) advances thebottom side of a loop and the length of the Loop
does not equal to the running length of the wholecommands. Thus the embedded position of turning commands in the daughter Loop differ from themother Loop.
Although such a shifting of reading-frames of its
command sequence is interesting phenomenon, it isdifficult to control. So we modify
solving.
this timing problem.
Fig.7 is the process of modified version of.
DB signal is notbottom side and the reproducing process starts from the bottom right corneras soon as the Worm reaches at this position. So
created daughter Loop is rotated in 90 degrees. Because of this rotation, Loops make collision after 4
generations. But this collision can be avoidable byinserting direction commands into the mother Loop
(Fig.8) and this modification acts importantinto three-dimensional one in the next
extendingsection.
$SR_{8}\mathrm{f}\dot{\mathrm{o}}\mathrm{r}$$SR_{8}$$\mathrm{a}\mathrm{d}\dot{\mathrm{v}}\mathrm{a}\mathrm{n}\mathrm{C}\mathrm{e}$$\mathrm{r}\mathrm{o}\mathrm{U}$$SR_{8}$Figure 7: Self-reproducing process of a Loop of.
modified$SR_{8}$4

Self-reproduction in a threedimensional RPCA

4.1

Three-dimensional
reproducing RPCA $(SR_{9})$self-

In this section, we extend
into a threedimensional RPCA.
A two-dimensional 5-neighbor PCA can be embedded directly into a three-dimensional 7-neighbor
PCA. But due to the rotation-symmetric condi, the Worm cannot know the directions
tion ofof right, left, up and down. In three-dimensional, up to 24 rotated rules arerotation-symmetricregarded as the same rule. So we introduce another glue state $‘=$ ’ forand combine two
Worms whose command sequences are complementaly placed as presented in table 3.
The three-dimensional self-reproducing RPCA
$SR_{8}$$SR_{8}$$\mathrm{C}\mathrm{A}$$SR_{8}$210

Figure 9: Four kind of turns in$SR_{9}$.

width 2 ladder approach in the previous section is
impossible. So we add a center wire and Fig.10 is a
simple Worm in.
$SR_{9}$Figure 10: A simple Worm in$SR_{9}$.

Figure 8: Self-reproducing process of a Loop ofmodified.
$SR_{8}$“ $SR_{9}$ ”

When both wires of a three-dimensional Worm’(or ‘AC AA
have the same sequence ‘AB AA
AB’), its head is twisted leftward (rightward). Using twisting commands, complex three-dimensional
Worms and Loops such as Fig.11 are constructible.
Although the existence of twisting commands in, its self-reproducing mechanism is completely.
the same as that ofis defined by$\mathrm{A}\mathrm{C}$$SR_{9}=(\mathrm{Z}^{3},$$(C, U, R, D, L, F, B),$$g$$(\#, \#, \#, \#, \#, \#, \#))$,,$C=U=R=D=L=F=B=$$\{\#, *, +, -, =, A,B, C, D\}$.

$SR_{9}$. Local rules are available via WWW.
http:$//\mathrm{k}\mathrm{e}\mathrm{l}\mathrm{p}.\mathrm{k}\mathrm{e}$. sys. hiroshima-u.

$SR_{8}$$\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/$4.2$\mathrm{P}^{\mathrm{r}\mathrm{o}}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{s}/\mathrm{r}\mathrm{c}\mathrm{a}/\mathrm{s}\mathrm{r}3\mathrm{d}/$Althoughhas 6886 rules, if rotated rules are
regarded as equivalent, it become only 338.
To construct ‘true’ three-dimensional structures,
can twist its head indegreesa Worm in(Fig.9). This can be possible by employing ribbonof width 3 shaped Worms. As far as usingcommand sequences in rotation-symmetric spaces,
the length of the path should be kept equal and the$SR_{9}$$\mathrm{r}\mathrm{u}\mathrm{l}\mathrm{e}\mathrm{s}[5]$$SR_{9}$$\pm 90$$SR_{8}$Controlling the position
daughter Loops inof$SR_{9}$, we use the modiWhen extending
todiscussed in section 3.6. So
fied version ofLoop positioning commands can also be inserted
freely in. And this modification has an important meaning in the three-dimensional case because
it makes possible to generate different topologicalshapes. Fig.12 is a chain formed from a single Loop.
$SR_{8}$$SR_{8}$$SR_{9}$$SR_{9}$211[3] Redkin, E., Toffoli, T.: Conservative logic, Int.
J. Theoretical Physics, 21, 3/4, (1982), 219-

253.

Figure 11: Complex Worm and Loop in$SR_{9}$.

This shape-construction technique can be possibleby the positioning a daughter Loop with a specificcommand sequences in the mother Loop.

[4] Hertling, P., Embedding cellular automata into
reversible ones, Unconventional Models of $C_{om}-$
putation, (eds., C.S.Claude, J. Casti, and M.J.
Dinneen), Springer-Verlag, (1998), 243-256.

[5] Hori, T., Expanding the self-reproduction
in a 2-dimensional reversible PCA
model
into 3-dimensional one, Master thesis, Hiroshima University, (1998).
$SR_{8}$[6] Langton, C, G.: Self-Reproduction in Cellular
Automata, Physica, 10D, $1/2$ , (1984), 135-144.

[7] Margolus, N.: Physics-like models of computation, Physica, 10D, $1/2$ , (1984), 81-95.

Figure 12: A chain formed from a single Loop in$SR_{9}$.

[8] Morita, K., and Harao, M.: Computation universality of one-dimensional reversible (injective) cellular automata, Trans. IEICE Japan,
E72, 6, (1989) 758-762.
[9] Morita, K., Ueno, S: Computation-Universal

5Models of Two-Dimensional 16-state Reversible
Cellular Automata, IEICE hans. Inf. &Syst.,
E75-D, 1, (1992), 141-147.

Conclusion[10] Morita, K.:

In this paper, we extend our two-dimensional
self-reproducing reversible PCA
into a threedimensional reversible PCA and show its various
behaviors. The features of this three-dimensional
reversible “turtle graphics” are d.erived from its selfinspective mechanism. The data as shapes and programs as command sequences are represented in the$SR_{8}$same manner.

$arrow\backslash \backslash$$\mathrm{k}$The self-reproducing processes are hard to describe on a paper. They can be seen as QuickTime
Movies at the following addresses via WWW.
: http:. sys. hiroshima-u.
$SR_{9}$$//\mathrm{k}\mathrm{e}1_{\mathrm{P}}.\mathrm{k}\mathrm{e}$$\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/$$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}\mathrm{e}\mathrm{C}\mathrm{t}\mathrm{S}/\mathrm{r}\mathrm{c}\mathrm{a}/\mathrm{s}\mathrm{r}3\mathrm{d}/$Ackowledgements: The authors thank Yukio
Matsuda of Hiroshma University and Hiroyuki Aga
of SONY Co,Ltd. for their support and comments.

References[1] Bennett, C.H.: Logical reversibility of computation, IBM J. Res. Dev., 17, 6, (1973), 525-532.
[2] Bennett, C.H.: The thermodynamics of computation, Int. J. Theoretical Physics, 21, 12,(1982), 905-940.

Reversible Simulation of Onedimensional Irreversible Cellular Automata,
Theoretical Computer Science, 148, (1995),

157-163.

[11] Morita, K., and Imai, K., Self-reproduction ina reversible cellular space, Theoret. Comput. Sci.,
168, 337-366 (1996).
[12] von Neumann, J.: Theory of Self-reproducing
Automata (ed. A.W.Burks), The University of
Illinois Press, Urbana, (1966).
[13] Toffoli, T.: Computation and Construction
Universality of Reversible Cellular Automata,
Journal of Computer and System Sc iences, 15,(1977), 213-231.