Reversible Elementary Triangular Partitioned Cellular Automata and Their Complex Behavior

Abstract

We investigate a special type of cellular automata called elementary triangular partitioned cellular automata (ETPCAs) in which various interesting phenomena emerge. They are quite simple, since each of their local functions is specified by only four local transition rules. There are 256 ETPCAs in total, and 36 among them are reversible. Despite their extreme simplicity, some reversible ETPCAs show quite complex behavior, and they even have universal computing capability. In this survey, based on the author’s past results, we discuss how complex phenomena appear in these ETPCAs, and how high-order functions, such as reversible logic gates, are realized combining useful phenomena.

Currently, Professor Emeritus of Hiroshima University.

1 Introduction

Complex phenomena can emerge even in a system composed of very simple elements. This fact also holds when we further add the “reversibility constraint” to the elements. In this survey, we discuss how complex phenomena emerge from a simple reversible microscopic law, and how these phenomena are utilized to obtain higher-order functions such as computing. Since reversibility is one of the fundamental laws of nature, it is important to study this problem. Here, we investigate it using the framework of reversible elementary triangular partitioned cellular automata.

A three-neighbor triangular cellular automaton (TCA) is one whose cell is triangular and communicates with its three edge-adjacent cells. So far, there have been several studies on TCAs, though they are not so many. Bays [2] studied a kind of TCAs with a similar type of local functions as that of Game-of-Life CA [6, 7]. Gajardo and Goles [5] proposed a three-state TCA, which is defined on a hexagonal lattice, and proved its computational universality. Imai and Morita [8] studied a reversible TCA, and showed that there is an eight-state universal reversible one. An advantage of using TCAs is that their local function can be simpler than those of CAs on a square lattice, since each cell has only three neighbor cells. Hence, it is suited for studying how complex phenomena emerge from a simple local function.

A three-neighbor triangular partitioned cellular automaton (TPCA) is a CA where cells are triangular, and each cell has three parts. A TPCA is called an elementary TPCA (ETPCA), if it is rotation-symmetric, and each part of a cell has only two states 0 and 1 (the state 1 is also called a particle). The class of ETPCAs is one of the simplest subclasses of two-dimensional CAs. This is because the local function of each ETPCA is described by only four local transition rules. There are 256 ETPCAs in total as in the case of one-dimensional elementary CAs (ECAs) [16]. It is known that there are 36 reversible ETPCAs among them. Among 36 reversible ones, there are nine conservative ETPCAs in which the total number of symbol 1’s in a configuration is conserved throughout its evolution process. This property is a similar notion to that of the conservation law of mass or energy in physics.

A particular conservative ETPCA No. 0157, where 0157 is an identification number in the class of ETPCAs, was first investigated in [8], and its computational universality was shown. In [9], it was shown that conservative ETPCA 0137 is also computationally universal. In [13], a nonconservative reversible ETPCA 0347 is studied. We think ETPCA 0347 is the most interesting one in the class of 256 ETPCAs, though not all ETPCAs have been fully investigated yet. In spite of its simplicity the local function, ETPCA 0347 shows quite interesting behavior like the Game-of-Life CA. In particular, a glider, which is a space-moving pattern, and glider guns exist in ETPCA 0347. Using gliders to represent signals, computational universality of ETPCA 0347 was also proved.

In this chapter, we discuss how interesting phenomena emerge in reversible ETPCAs 0347, 0157 and 0137, how such phenomena are utilized to realize higher-order functions such as reversible logic elements, and how reversible computers can be built from these logic elements. In Sect. 2, after giving definitions on ETPCAs, we classify 256 ETPCAs by introducing three kinds of dualities. In Sect. 3, a nonconservative reversible ETPCA No. 0347 is investigated. In this ETPCA, three kinds of patterns exist. They are periodic patterns, a space-moving pattern, and expanding patterns. Among them, a space-moving pattern called a glider is interesting and useful. Here, how to control its flight is explained. By this, a glider can be used as a signal for composing a reversible computer. In Sect. 4, conservative ETPCAs 0157 and 0137 are investigated. There are many space-moving patterns in both of these ETPCAs. Though behavior of these patterns is complex and seems interesting, their periods are vary large. Therefore, it is difficult to control the flying directions and the timings of the space-moving patterns. Instead, a one-particle pattern, which can move along a transmission line, is used to represent a signal for computing. Since a universal reversible logic gate is realizable, computational universality of ETPCAs 0157 and 0137 is derived.

2 Elementary Triangular Partitioned Cellular Automata

We give several definitions on elementary triangular partitioned cellular automata (ETPCAs). We also define three kinds of duality among them, by which 256 ETPCAs are classified into 82 equivalence classes.

2.1 Triangular Partitioned Cellular Automata (TPCAs)

A three-neighbor triangular partitioned cellular automaton    (TPCA) is a CA defined on the cellular space shown in Fig. 1. In a TPCA, each cell has three parts, and the next state of a cell is determined by the states of the adjacent parts of the three neighbor cells as shown in Fig. 2.

Fig. 1

Cellular space of a three-neighbor TPCA

Fig. 2

Pictorial representations of the local transition rule $f(l,d,r)=(l',d',r')$, where (l, d, r),  $(l',d',r') \in L\!\times \!D\!\times \!R$. They are a for up-triangle cells, and b for down-triangle cells

All the cells of a TPCA are identical copies of a finite state machine, and each cell has three parts, i.e., the left, downward, and right parts, whose state sets are L, D and R, respectively. However, the directions of the cells are not the same, i.e., there are up-triangle cells, and down-triangle cells.

We now place cells of a TPCA on $\mathbb {Z}^2$ as shown in Fig. 3. We assume that if the coordinates of an up-triangle cell is (x, y), then $x+y$ must be even. It should be noted, if we define an TPCA on $\mathbb {Z}^2$, there arises a problem that the neighborhood is slightly non-uniform. Namely, for an up-triangle cell, its neighbors are the west, south and east adjacent cells (Fig. 2a), while for a down-triangle cell, its neighbors are the east, north and west adjacent cells (Fig. 2b). Though such non-uniformity is dissolved by defining a TPCA on a Cayley graph, here we define a TPCA on $\mathbb {Z}^2$.

Fig. 3

The x-y coordinates in the cellular space of TPCA

Definition 1

A deterministic triangular partitioned cellular automaton (TPCA) is a system defined by

$$ \begin{array}{lll} T=(\mathbb {Z}^2,(L,D,R),((-1,0),(0,-1),(1,0)),((1,0),(0,1),(-1,0)), f,(\#,\#,\#)). \end{array} $$

Here, $\mathbb {Z}^2$ is the set of all two-dimensional points with integer coordinates at which cells are placed. Each cell has three parts, i.e., the left, downward and right parts, where L, D and R are non-empty finite set of states of these parts. The state set Q of each cell is thus given by $Q = L \times D \times R$. The triplet $((-1,0),(0,-1),(1,0))$ is a neighborhood for up-triangle cells, and $((1,0),(0,1),(-1,0))$ is a neighborhood for down-triangle cells. The item $f: Q \rightarrow Q$ is a local function,  and $(\#,\#,\#)\in Q$ is a quiescent state that satisfies $f(\#,\#,\#)=(\#,\#,\#)$. We also allow a TPCA that has no quiescent state. A configuration  of T is a function $\alpha : \mathbb {Z}^2 \rightarrow Q$. If the set $\{(x,y)\ |\ \alpha (x,y) \ne (\#,\#,\#)\}$ is finite, $\alpha$ is called a finite configuration.

If $f(l,d,r)=(l',d',r')$ holds for $(l,d,r),(l',d',r') \in Q$, then this relation is called a local transition rule of the TPCA T (Fig. 2). The global function induced by the local function of a TPCA is defined as below.

Definition 2

Let T be a TPCA. The set of all configurations of T is denoted by $\mathrm{Conf}(T)$, i.e., $\mathrm{Conf}(T)=\{\alpha \,|\, \alpha : \mathbb {Z}^2 \rightarrow Q\}$. Let $\mathrm{pr}_{L}: Q \rightarrow L$ be the projection function such that $\mathrm{pr}_L(l,d,r)=l$ for all $(l,d,r) \in Q$. The projection functions $\mathrm{pr}_{D}: Q \rightarrow D$ and $\mathrm{pr}_{R}: Q \rightarrow R$ are also defined similarly. The global function $F: \mathrm{Conf}(T) \rightarrow \mathrm{Conf}(T)$ of T is defined as the one that satisfies the following condition.

$$ \begin{array}{l} \forall \alpha \in \mathrm{Conf}(T), \forall (x,y) \in \mathbb {Z}^2: \\ F(\alpha )(x,y) = \left\{ \begin{array}{rr} f(\mathrm{pr}_L(\alpha (x-1,y)),\mathrm{pr}_D(\alpha (x,y-1)),\mathrm{pr}_R(\alpha (x+1,y))) \\ \ \ \mathrm{if}\ x+y\ \mathrm{is\ even} \\ f(\mathrm{pr}_L(\alpha (x+1,y)),\mathrm{pr}_D(\alpha (x,y+1)),\mathrm{pr}_R(\alpha (x-1,y))) \\ \ \ \mathrm{if}\ x+y\ \mathrm{is\ odd} \\ \end{array} \right. \end{array} $$

From this definition, we can see that the next state of the up-triangle cell is determined by the present states of the left part of the west neighbor cell, the downward part of the south neighbor cell, and the right part of the east neighbor cell. On the other hand, the next state of the down-triangle cell is determined by the present states of the left part of the east neighbor cell, the downward part of the north neighbor cell, and the right part of the west neighbor cell. Therefore, for a local transition rule $f(l,d,r)=(l',d',r')$, there are two kinds of pictorial representations as shown in Fig. 2a, b. Namely, Fig. 2a is for up-triangle cells, while Fig. 2b is for down-triangle cells.

In [14], it is shown injectivity of the global function is equivalent to that of the local function in one-dimensional PCAs. The following lemma is proved in a similar manner as this.

Lemma 1

([14]) Let T be a TPCA, f be its local function, and F be its global function. Then, F is injective if and only if f is injective.

A reversible TPCA is defined as follows.

Definition 3

Let T be a TPCA. The TPCA T is called reversible    if its local (or equivalently global) function is injective.

We define the notion of rotation-symmetry for a TPCA as follows.

Definition 4

Let

$$ T\ =\ (\mathbb {Z}^2,(L,D,R),((-1,0),(0,-1),(1,0)),((1,0),(0,1),(-1,0)),f,(\#,\#,\#)) $$

be a TPCA. The TPCA T is called rotation-symmetric (or isotropic) if the conditions (1) and (2) holds.

$\begin{array}{ll} (1)\ L = D = R \\ (2)\ \forall \, (l,d,r),(l',d',r')\in L\!\times \!D\!\times R: \ f(l,d,r) = (l',d',r') \Rightarrow f(d,r,l) = (d',r',l') \end{array}$

2.2 Elementary TPCAs (ETPCAs)

Definition 5

Let

$$ T\ =\ (\mathbb {Z}^2,(L,D,R),((-1,0),(0,-1),(1,0)),((1,0),(0,1),(-1,0)),f) $$

be a TPCA. It is called an elementary triangular partitioned cellular automaton (ETPCA),    if $L=D=R=\{0,1\}$, and it is rotation-symmetric.

The set of states of a cell of an ETPCA is $L \times D \times R = \{0,1\}^3$, and thus a cell has eight states. When drawing figures of T’s local transition rules and configurations, we indicate the states 0 and 1 of each part by a blank and a particle (i.e., $\bullet$), respectively.

Since ETPCA is rotation-symmetric, and each part of a cell has the state set $\{0,1\}$, its local function is defined by only four local transition rules. Hence, an ETPCA can be specified by a four-digit number wxyz, as shown in Fig. 4, where $w,z \in \{0,7\}$ and $x,y \in \{0,1,\ldots ,7\}$. Thus, there are 256 ETPCAs. Note that w and z must be 0 or 7 because an ETPCA is deterministic and rotation-symmetric. The ETPCA with the number wxyz is denoted by $T_{wxyz}$.

Fig. 4

Representing an ETPCA by a four-digit number wxyz, where $w,z \in \{0,7\}$ and $x,y \in \{0,1,\ldots ,7\}$. Vertical bars indicate alternatives of a right-hand side of a rule

A reversible ETPCA is an ETPCA whose local function is injective (Definition 3). Thus, it is easy to show the following.

Lemma 2

Let $T_{wxyz}$ be an ETPCA. It is reversible if and only if the following conditions (1) and (2) hold.

$\begin{array}{ll} (1)\ &{} (w,z) \in \{(0,7),(7,0)\} \\ (2)\ &{} (x,y) \in \{1,2,4\}\times \{3,5,6\} \cup \{3,5,6\}\times \{1,2,4\} \\ \end{array}$

A conservative ETPCA is one such that the total number of particles (i.e., $\bullet$’s) is conserved in each local transition rule. Hence, it is defined as follows.

Definition 6

Let $T_{wxyz}$ be an ETPCA. It is called a conservative ETPCA    if the following condition holds.

$$\begin{aligned} w=0\ \wedge \ x \in \{1,2,4\}\ \wedge \ y \in \{3,5,6\}\ \wedge \ z=7 \end{aligned}$$

From Lemma 2 and Definition 6, it is clear the following holds.

Lemma 3

Let T be an ETPCA. If T is conservative, then it is reversible.

We can see that there are 36 reversible ETPCAs (by Lemma 2), and among them there are nine conservative ones (by Definition 6). Hence, in ETPCAs, conservative ones are a subclass of reversible ones.

2.3 Dualities in ETPCAs

As seen above, there are 256 ETPCAs. However, there are some “equivalent” ETPCAs, and thus the number of essentially different ETPCAs is much smaller. Here, we introduce three kinds of dualities, and classify the ETPCAs based on them [12].

2.3.1 Duality Under Reflection

Definition 7

Let T and $\hat{T}$ be ETPCAs, and f and $\hat{f}$ be their local functions. We say T and $\hat{T}$ are dual under reflection,  if the following holds, and it is written as .

$$ \begin{array}{ll} \forall (l,d,r),(l',d',r')\in \{0,1\}^3:\ f(l,d,r)=(l',d',r')\ \Leftrightarrow \ \hat{f}(r,d,l)=(r',d',l') \end{array} $$

By this definition, we can see that the local transition rules of $\hat{T}$ are the mirror images of those of T. Therefore, an evolution process of T’s configurations is simulated in a straightforward manner by the mirror images of the T’s configurations in $\hat{T}$. For example, holds (Fig. 5), and examples of their evolution processes are shown in Fig. 6.

Fig. 5

The local functions of $T_{0137}$ and $T_{0467}$ that are dual under reflection

Fig. 6

Examples of evolution processes in a $T_{0137}$, and b $T_{0467}$

2.3.2 Duality Under Complementation

For $x \in \{0,1\}$, let $\overline{x}$ denote $1-x$, i.e., the complement of x.

Definition 8

Let T and $\overline{T}$ be ETPCAs, and f and $\overline{f}$ be their local functions. We say T and $\overline{T}$ are dual under complementation,  if the following holds, and it is written as .

By this, we can see that the local transition rules of $\overline{T}$ are the 0–1 exchange (i.e., taking their complements) of those of T. Therefore, an evolution process of T’s configurations is simulated in a straightforward manner by the complemented images of the T’s configurations in $\overline{T}$. For example, holds (Fig. 7), and examples of their evolution processes are shown in Fig. 8.

Fig. 7

The local functions of $T_{0157}$ and $T_{0267}$ that are dual under complementation

Fig. 8

Examples of evolution processes in a $T_{0157}$, and b $T_{0267}$

2.3.3 Duality Under Odd-Step Complementation

Definition 9

Let T be an ETPCA such that its local function f satisfies the following.

Let $\tilde{T}$ be another ETPCA, and $\tilde{f}$ be its local function. We say T and $\tilde{T}$ are dual under odd-step complementation,  if the following holds, and it is written as .

$$ \begin{array}{l} \forall (l,d,r),(l',d',r')\in \{0,1\}^3:\ f(l,d,r)=(l',d',r')\ \Leftrightarrow \ \tilde{f}(l,d,r)=(\overline{l'},\overline{d'},\overline{r'}) \end{array} $$

Since the ETPCA T satisfies the condition (1), we see that for each local transition rule $f(l,d,r)=(l',d',r')$ of T, there are two local transition rules $\tilde{f}(l,d,r)=(\overline{l'},\overline{d'},\overline{r'})$ and of $\tilde{T}$ (hence $\tilde{T}$ also satisfies (1)). Let F and $\tilde{F}$ be the global function of T and $\tilde{T}$, respectively. If the initial configuration of T is $\alpha : \mathbb {Z}^2 \rightarrow \{0,1\}^3$, then we assume $\alpha$ is also given to $\tilde{T}$ as its initial configuration. Since there is a local transition rule $\tilde{f}(l,d,r)=(\overline{l'},\overline{d'},\overline{r'})$ for each $f(l,d,r)=(l',d',r')$, the configuration $\tilde{F}(\alpha )$ is the complement of the configuration $F(\alpha )$. Furthermore, since there is a local transition rule for each $f(l,d,r)=(l',d',r')$, the configuration $\tilde{F}^2(\alpha )$ is the same as $F^2(\alpha )$. In this way, at an even step $\tilde{T}$ gives the same configuration as T, while at an odd step $\tilde{T}$ gives the complemented configuration of T. For example, holds (Fig. 9). Figure 10 shows examples of their evolution processes.

Fig. 9

The local functions of $T_{0347}$ and $T_{7430}$, which are dual under odd-step complementation

Fig. 10

Examples of evolution processes in a $T_{0347}$, and b $T_{7430}$

Note that, in Definition 9, the ETPCA T must satisfy the condition (1). Therefore, the relation    is defined on the ETPCAs of the form $T_{wxyz}$ such that $w+z=7$ and $x+y=7$. Hence, only the following 16 ETPCAs have their dual counterparts under odd-step complementation.

2.3.4 Equivalence Classes of ETPCAs

If ETPCAs T and $T'$ are dual under reflection, complementation, or odd-step complementation, then they can be regarded as essentially the same ETPCAs. Here, we classify the 256 ETPCAs into equivalence classes based on the three dualities. We define the relation    as follows: For any ETPCAs T and $T'$,

holds. Now, let    be the reflexive and transitive closure of   . Then,    is an equivalence relation, since    is symmetric. By this, 256 ETPCAs are classified into 82 equivalence classes. Table 1 shows the classification result.

Table 1 Total numbers and numbers of equivalence classes of ETPCAs, reversible ETPCAs and conservative ETPCAs [12]

Wolfram classified 256 one-dimensional elementary cellular automata (ECAs)    into 88 equivalence classes, which is given in the Appendix of [16]. It is based on the two dualities reflection and conjugation that correspond to reflection and complementation in ETPCAs, respectively. If we consider only these two dualities in ETPCAs, the number of equivalence classes is 88, the same as in ECAs. Note that in [16] the duality corresponding to odd-step complementation is implicitly mentioned, and if we also use it, the number of equivalence classes of ECAs becomes 82.

ECAs and ETPCAs have very different features in reversibility. In ECAs, there are six reversible ones: ECAs 15, 51, 85, 170, 204 and 240. They are grouped into two equivalence classes if we use the three dualities. We can see one class contains ECA 204 (identity), and the other contains ECA 170 (left shift). Hence, all the six are trivial ones. On the other hand, there are 36 reversible ETPCAs that are grouped into 12 equivalence classes (Table 1). Many of them are nontrivial, and as we shall see below, at least ten reversible ETPCAs in three classes are computationally universal.

3 Complex Phenomena in Reversible ETPCA $T_{0347}$

 

Here, we focus on a specific nonconservative reversible ETPCA $T_{0347}$ [13]. Its local function is given in Fig. 11. Despite its extreme simplicity of the local function, it exhibits quite interesting behavior similar to the case of the Game-of-Life CA [6, 7].

Though its local function itself is very simple, it is generally hard to follow evolution processes of configurations of $T_{0347}$ by hand. So we created a simulator for it. Simulation movies can be seen in the slide file of [13]. We also created an emulator for $T_{0347}$ on the general purpose CA simulator Golly [15].  The file of the emulator with many examples of configurations is found in [11].

Fig. 11

Local function of the nonconservative reversible ETPCA $T_{0347}$

3.1 Patterns in $T_{0347}$

A pattern is a finite segment of a configuration.  Patterns can be defined in any ETPCA. However, when we consider an evolution process of a finite configuration that contains pattern(s), it is convenient to restrict ETPCAs to those with an identification number of the form 0xyz (i.e., to those with a quiescent state). Otherwise, the initial finite configuration will become an infinite one at the next time step.

In this section, we give various interesting patterns in in $T_{0347}$. In a reversible ETPCA there are only three kinds of patterns. They are periodic patterns, space-moving patterns and expanding patterns. Note that, because of reversibility, there is no pattern that becomes a periodic (or space-moving) pattern after a positive number of transient steps.

A periodic pattern is one that satisfy the following condition:  Starting from the finite configuration that contains one copy of it, only one copy of it appears at the same position after p time steps ($p >0$). The number p is the period of the pattern. If $p=1$, it is called a stable pattern.

A block is a stable pattern in $T_{0347}$ shown in Fig. 12. As we shall see below, combining several blocks, and appropriately colliding a space-moving pattern with them, right-turn, left-turn, backward-turn, and U-turn are realized.

Fig. 12

A block in $T_{0347}$. It is a stable pattern

A fin is a periodic pattern that simply rotates with period 6 (Fig. 13). Note that any pattern appearing at $t=0,\ldots ,5$ of Fig. 13 is a fin. A rotator is a pattern shown in Fig. 14. Like a fin, it rotates around a point, and its period is 42. Though there are many periodic patterns in $T_{0347}$, a block, a fin and a rotator are the most useful ones.

Fig. 13

A fin. It rotates around the point $\circ$ with period 6 in $T_{0347}$

Fig. 14

A rotator. It rotates around the point $\circ$ with period 42 in $T_{0347}$

A space-moving pattern is one that satisfy the following:  Starting from the finite configuration that contains one copy of it, only one copy of it appears at a different position after p time steps ($p >0$). The number p is also called the period of the space-moving pattern. Such a patten is useful for collision-based computing [1].

Fig. 15

A glider. It is a space-moving pattern of period 6 in $T_{0347}$

Figure 15 shows a specific space-moving pattern in $T_{0347}$, which is called a glider.  It is so named after the famous glider in the Game-of-Life [6], but it swims in the cellular space like a fish or an eel. It travels a unit distance, the side-length of a triangular cell, in 6 steps. By rotating it appropriately, it can move in any of the six directions. When constructing a computing machine in $T_{0347}$, it will be used as a signal. So far, it is not known whether there is another space-moving pattern essentially different from a glider (i.e., not composed of two or more gliders).

An expanding pattern  is one whose diameter grows indefinitely as it evolves. Figure 16 is an example of an expanding pattern in $T_{0347}$. By colliding a glider to a fin ($t=0$), we have a glider gun  that generates three gliders every 24 steps [13]. In this case, the total number of particles in a configuration also grows indefinitely.

Fig. 16

A three-way glider gun created by a collision of a glider with a fin in $T_{0347}$ [13]. It is an expanding pattern

Fig. 17

A three-way glider absorber in $T_{0347}$ [13]. It is a glider gun to the negative time direction

We can show that an expanding pattern also expands to the negative time direction because of reversibility [13]. In fact, the distance between the glider and the fin at $t=0$ in Fig. 16 grows larger and larger when we go back to the past (i.e., $t<0$).

It is remarkable that there is a glider gun that generates gliders to the negative time direction (Fig. 17). It is also an expanding pattern. Furthermore, by appropriately combining two configurations at $t=0$ of Fig. 16 and $t=0$ of Fig. 17, it is possible to have a gun that generates gliders in both positive and negative time directions.

Figure 18 gives another example of an expanding pattern. If we start with a one-particle pattern, a chaotic (or disordered) pattern with many gliders is generated, and the whole pattern grows larger and larger. Also in this case, a similar chaotic pattern with gliders appears and grows indefinitely to the negative time direction [13].

Fig. 18

A chaotic pattern that expands indefinitely appears from the one-particle pattern in $T_{0347}$

It should be noted that a chaotic pattern often appears even from a configuration that contains only periodic patterns and gliders. Therefore, if we want to design a large pattern that perform some intended task, we should carefully do it so that the whole pattern never generates a chaotic pattern.

3.2 Interactions of Patterns in $T_{0347}$

It is known that various interesting phenomena emerge by interacting blocks, fins or gliders with another glider [13]. In this section, we observe what happens when we collide a glider to a sequence of blocks.

Fig. 19

Turn modules for a glider in $T_{0347}$ [13]. a Right-turn module composed of two blocks, b backward-turn module, c U-turn module, and d left-turn module

We first collide a glider with two blocks (Fig. 19a). Then, the glider is split into a rotator and a fin ($t=56$). The fin travels around the blocks three times without interacting with the rotator. At the end of the fourth round, they meet to form a glider, which goes to the south-west direction ($t=334$). Hence, two blocks act as a $120^{\circ }$-right-turn module. It is also possible to make a right-turn module with a different delay time using three or five blocks. If we collide a glider with a single block as shown in Fig. 19b, then the glider makes backward turn. Hence, a single block acts as a backward-turn module. Figure 19c is a U-turn module, and Fig. 19d is a left-turn module. By such interactions, the move direction and the timing of a glider is completely controlled [13].

There are still other interesting interactions of patterns in $T_{0347}$, e.g., interactions of a fin and a glider, and those of two or more gliders. See [10,11,12,13] for their details.

3.3 Computational Universality of $T_{0347}$

To prove computational universality of a reversible CA, it is sufficient to show that any reversible logic circuit composed of switch gates (Fig. 20a),  inverse switch gates (Fig. 20b),  and delay elements can be simulated in it (Lemma 8).

Fig. 20

a Switch gate. b Inverse switch gate, where $c=y_1$ and $x=y_2 + y_3$ under the assumption $(y_2 \rightarrow y_1)\wedge (y_3 \rightarrow \overline{y_1})$. c Fredkin gate

Lemma 8 given below can be derived, e.g., in the following way. First, a Fredkin gate (Fig. 20c) can be constructed out of switch gates and inverse switch gates (Lemma 4). Second, any reversible sequential machine (RSM),  in particular, a rotary element (RE), which is a 2-state 4-symbol RSM, is composed only of Fredkin gates and delay elements (Lemma 5). Third, any reversible Turing machine is constructed out of REs (Lemma 6). Finally, any (irreversible) Turing machine is simulated by a reversible one (Lemma 7). Thus, Lemma 8 follows.

Lemma 4

([4]) A Fredkin gate  can be simulated by a circuit composed of switch gates and inverse switch gates, which produces no garbage signals.

Lemma 5

([10]) Any RSM (in particular RE) can be simulated by a circuit composed of Fredkin gates and delay elements, which produces no garbage signals.

Lemma 6

([10]) Any reversible Turing machine  can be simulated by a garbage-less circuit composed only of REs.

Lemma 7

([3]) Any (irreversible) Turing machine can be simulated by a garbage-less reversible Turing machine.

Lemma 8

A reversible CA is computationally universal,  if any circuit composed of switch gates, inverse switch gates, and delay elements is simulated in it.

Fig. 21

Switching operation realized by collision of two gliders in $T_{0347}$ [13]

Fig. 22

Switch gate module implemented in $T_{0347}$, whose input-output delay is 2232 [13]

We now show computational universality of $T_{0347}$. It is possible to implement a switch gate and an inverse switch gate in $T_{0347}$ using gliders as signals. The switching operation $(c,x)\mapsto (c,cx,\overline{c}x)$ is realized by colliding two gliders as shown in Fig. 21. Using many turn modules to adjust the collision timing and the directions of the input gliders, we can construct a switch gate module as shown in Fig. 22. An inverse switch gate can be also realized in a similar manner. By above, and by the dualities among ETPCAs, we have the following.

Theorem 1

([13]) The nonconservative reversible ETPCAs $T_{0347}$, $T_{0617}$, $T_{7430}$ and $T_{7160}$ are computationally universal. 

Fig. 23

Local function of $T_{0157}$ defined by four local transition rules

Fig. 24

A block in $T_{0157}$. It is a stable pattern

Fig. 25

One-particle pattern in $T_{0157}$. It simply rotates with period 6

4 Complex Phenomena in Conservative ETPCAs

 

In this section, we investigate conservative ETPCAs. There are nine such ETPCAs (Definition 6), which are classified into the following four equivalence classes.

$$ \{ T_{0157}, T_{0457}, T_{0237}, T_{0267} \}, \{ T_{0137}, T_{0467} \}, \{ T_{0167}, T_{0437} \}, \{ T_{0257} \} $$

Though the total number of particles in a configuration is conserved in them, the six ETPCAs in the first two classes still show complex behavior. In particular, they were shown to be computationally universal [8, 9]. On the other hand, those in the last two classes are trivial ETPCAs, and thus they are non-universal [9].

4.1 Conservative ETPCA $T_{0157}$

Here we consider the conservative and reversible ETPCA $T_{0157}$ (Fig. 23). It was first studied in [8].

There are many periodic patterns in $T_{0157}$. Among them two are useful. They are a block and a one-particle pattern. A block is a stable pattern shown in Fig. 24. On the other hand, a one-particle pattern (Fig. 25) rotates clockwise with period 6 by the second local transition rule of Fig. 23.

In $T_{0157}$ there exist a large number of space-moving patterns. On this point, $T_{0157}$ is very different from $T_{0347}$. In fact, it is rather easy to find such patterns by watching an evolution process starting from a randomly given finite pattern with many particles. In many cases, some space-moving patterns and some periodic patterns will appear from it. However, periods of space-moving patterns are generally very long. Figure 26 shows an example of a space-moving pattern of period 1016.  Furthermore, it exhibits complex behavior in the period. Since the period is long, it is very difficult to control a space-moving pattern, in particular to adjust its timing. So far, it is not known whether there is a space-moving pattern with a very short period (say 10 or less).

Since there are space-moving patterns in $T_{0157}$, expanding patterns also exist in it. For example, a configuration consisting of two space-moving patterns that go to different directions is an expanding pattern, though the total number of particles in a configuration is always constant.

Fig. 26

A space-moving pattern of period 1016 in $T_{0157}$

Here we use a one-particle pattern, rather than a space-moving pattern, as a signal. A signal transmission wire, on which a signal can move, is obtained by connecting blocks as shown in Fig. 27. Wires can be bent relatively freely, and by this the timing of a signal is adjusted. In [8, 12], a module for crossing two signals in the two-dimensional space is given.

Fig. 27

Transmission of a signal along a wire consisting of blocks in $T_{0157}$ [8, 12]. A small number t ($1 \le t \le 28$) shows the position of the signal at time t

The switch gate operation $(c,x) \mapsto (c,cx,\overline{c}x)$ is realized by one cell of $T_{0157}$ as shown in Fig. 28. Likewise, the inverse switch gate operation is also realized by one cell. Complete patterns of a switch gate module, and an inverse switch gate module are given in [8, 12].

Fig. 28

Switch gate operation realized by one cell of $T_{0157}$

4.2 Conservative ETPCA $T_{0137}$

Next, consider the conservative and reversible ETPCA $T_{0137}$ (Fig. 29).

Fig. 29

Local function of $T_{0137}$ defined by four local transition rules

Among many periodic patterns in $T_{0137}$, a block and a one-particle pattern are useful as in the case of $T_{0157}$. Figure 30 shows a block in $T_{0137}$. Though it is different from Fig. 24, it is stable in $T_{0137}$. The one-particle pattern (Fig. 25) rotates clockwise with period 6 also in $T_{0137}$.

Fig. 30

A block in $T_{0137}$. It is a stable pattern

Similar to the case of $T_{0157}$, there are many space-moving patterns in $T_{0137}$. Again, in this case, their periods are very long. Hence, it is hard to use them as signals in logic circuits. Figure 31 is an example of a space-moving pattern of period 3162. 

Fig. 31

A space-moving pattern of period 3162 in $T_{0137}$

Figure 32 shows a signal transmission wire in $T_{0137}$ composed of blocks, on which a particle travels as a signal. The switch gate operation is realized by one cell of $T_{0137}$ as in Fig. 33. Using these phenomena and operations, a signal crossing module, a switch gate module and an inverse switch gate module can be constructed (see [9, 12] for the details).

Fig. 32

Transmission of a signal along a wire in $T_{0137}$ [9, 12]

Fig. 33

Switch gate operation realized by one cell of $T_{0137}$

4.3 Universality of Reversible and Conservative ETPCAs

As seen in Sects. 4.1 and 4.2, any circuit composed of switch gates, inverse switch gates, and signal delays is embeddable in each of $T_{0157}$ and $T_{0137}$. Hence by Lemma 8, they are computationally universal. Therefore all ETPCAs in the equivalence classes of $\{ T_{0157}, T_{0457}, T_{0237}, T_{0267} \}$ and $\{ T_{0137}, T_{0467} \}$ are also computationally universal.

On the other hand, it is shown that all configurations of $T_{0257}$ are of period 2, and thus it is a trivial ETPCA [12]. In fact, we can interpret the local function of $T_{0257}$ as the one where every particle moves back and forth between two adjacent cells. Likewise in $T_{0167}$ and $T_{0437}$, all configurations are of period 6 [12]. Hence they are non-universal.

By above, we have the following theorem, which clarifies universality of all the nine conservative ETPCAs.

Theorem 2

([8, 9, 12]) The reversible and conservative ETPCAs $T_{0157}$, $T_{0457}$, $T_{0237}$, $T_{0267}$, $T_{0137}$, and $T_{0467}$ are computationally universal.  On the other hand, $T_{0167}$, $T_{0437}$, and $T_{0257}$ are non-universal.

5 Concluding Remarks

In this chapter, we saw even quite simple CAs called reversible ETPCAs exhibit complex behavior. In particular, ten reversible ETPCAs in three equivalence classes were shown to be computationally universal (Theorems 1 and 2) by a tricky use of complex phenomena found in them. A further result is given in [10, 11]: Reversible Turing machines are compactly implemented in the ETPCA 0347 using a special type of reversible logic element with memory, rather than a reversible logic gate. Investigation of other universal or interesting ETPCAs is left for the future study.