5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal

Abstract

We study two-dimensional rotation-symmetric number-conserving cellular automata working on the von Neumann neighborhood (RNCA). It is known that such automata with 4 states or less are trivial, so we investigate the possible rules with 5 states. We give a full characterization of these automata and show that they cannot be strongly Turing universal. However, we give example of constructions that allow to embed some boolean circuit elements in a 5-states RNCA.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Cellular automata (CA) are widely studied deterministic, discrete and massively parallel dynamical systems. They were introduced by J. von Neumann and S. Ulam in the 1940s (published posthumously in 1966) to study self replicating systems [10].

Von Neumann developped a 29-states CA working on the “4 closest cells” neighborhood (that would later be known as the “von Neumann neighborhood”) capable of replicating patterns, and used it to describe the notion of computational universality. In 1968, E. Codd improved von Neumann’s construction by devising an 8-states universal rotation-symmetric CA working on the same neighborhood [3] and proving that 2-states von Neumann neighborhood CA could not be strongly universal. In 1970, E. Banks proved the existence of a 4-states strongly universal rotation-symmetric CA on von Neumann’s neighborhood and a 2-states weakly universal one [1]. This search for small universal automata was finally completed in 1987 when T. Serizawa published a 3-states strongly universal CA on the von Neumann neighborhood [7].

Since their introduction, cellular automata have been broadly used as a model for biological, chemical and physical processes. In 1969, K. Zuse was the first to propose the theory that physics is computation and that the universe could be seen as a cellular automaton [11]. The notion of number conservation appeared as a result of attempts to implement physical conservation laws (energy, mass, particles, etc.) in cellular automata. It was first defined by K. Nagel and M. Schreckenberg to model road traffic flow [6] and has since become an important subject of research in the cellular automata community as a natural example of global property enforced by local conditions.

In the early 2000s, H. Fuks and N. Boccara [2], B. Durand et al. [4] and A. Moreira [5] independently proved that number-conservation was a decidable property by giving explicit characterizations of local transition rules of number-conserving cellular automata (NCCA).

Imai et al. proved the existence of a weakly universal 29-states von Neumann neighborhood rotation-symmetric NCCA and this result was later improved by N. Tanimoto and K. Imai who managed to reduce the number of required states to 14 by using an exact characterization of von Neumann neighborhood NCCA [8]. From the same characterization, N. Tanimoto et al. proved that von Neumann neighborhood rotation-symmetric NCCA with 4 states or less are all trivial [9].

In this article, we investigate the computational power of 5-states von Neumann neighborhood rotation-symmetric NCCA. We obtain a precise description of the possible transition rules of such automata and prove that none of them can be strongly universal as their evolution from a finite initial configuration must be ultimately periodic. However, we show that they are capable of some computation by exhibiting patterns that simulate the behavior of some boolean circuit elements.

2 Definitions

In this article, we will only consider deterministic 2-dimensional cellular automata working on the von Neumann neighborhood.

Definition 1

(Cellular Automaton). A 2-dimensional von Neumann neighborhood cellular automaton (CA) is a triple $\mathcal {A}= (Q, f, q_0)$ where

• $Q$ is a finite set. The elements of $Q$ are called states;

• $f:Q^5 \rightarrow Q$ is a function called the local transition function of $\mathcal {A}$;

• $q_0\in Q$ is called the quiescent state and $f(q_0,q_0,q_0,q_0,q_0) = q_0$.

A 2-dimensional configuration over $Q$ is a mapping $\mathfrak {C}:\mathbb {Z}^2\rightarrow Q$. The elements of $\mathbb {Z}^2$ are called cells and for a cell $c\in \mathbb {Z}^2$, we say that $\mathfrak {C}(c)$ is the state of $c$ in the configuration $\mathfrak {C}$.

The set of all configurations over $Q$ is denoted by

$$\begin{aligned} {\text {Conf}}(Q)=\{c, c:\mathbb {Z}^2\rightarrow Q\} \end{aligned}$$

From the local transition function $f$, we define a global transition function $F:{\text {Conf}}(Q)\rightarrow {\text {Conf}}(Q)$ obtained by replacing the state of each cell by the result of $f$ applied to the cell’s state and the states of its $4$ closest neighbors¹: $\forall \mathfrak {C}\in {\text {Conf}}(Q),$

$$\begin{aligned} F(\mathfrak {C}) = \left\{ \begin{array}{rl} \mathbb {Z}^2 &{}\rightarrow Q \\ (x,y) &{}\mapsto f(\mathfrak {C}(x,y), \mathfrak {C}(x, y+1), \mathfrak {C}(x+1, y), \mathfrak {C}(x, y-1), \mathfrak {C}(x-1, y)) \end{array}\right. \end{aligned}$$

As is commonly done in dynamical systems theory, we will use the same notation for the cellular automaton and its global transition function. The image of a configuration $\mathfrak {C}$ by the global transition function of an automaton $\mathcal {A}$ will therefore be denoted $\mathcal {A}(\mathfrak {C})$.

Definition 2

(Finite Configurations). Given a cellular automaton $\mathcal {A}=(Q, f, q_0)$, we say that a configuration $\mathfrak {C}\in {\text {Conf}}(Q)$ is finite if only a finite number of cells are in a state other than $q_0$ in $\mathfrak {C}$.

The rectangular bound of a finite configuration $\mathfrak {C}$ is the smallest rectangle containing all the non-quiescent cells of $\mathfrak {C}$. We call width and height of the configuration $\mathfrak {C}$ the width and height of its rectangular bound.

From the locality of the transition rule of the automaton and the fact that $f(q_0,q_0,q_0,q_0,q_0) = q_0$ it is clear that the image by a CA of a finite configuration $\mathfrak {C}$ of dimensions $(w\times h)$ is also finite and of dimensions $(w'\times h')$ with $w'\le w+2$ and $h'\le h+2$.

Definition 3

(Rotation-Symmetry). A von Neumann neighborhood cellular automaton $\mathcal {A}=(Q,f,q_0)$ is said to be rotation-symmetric if its local transition function $f$ is invariant by rotation of a quarter cycle:

$$\begin{aligned} \forall c, u, r, d, l \in Q,\quad f(c,u,r,d,l) = f(c,r,d,l,u) \end{aligned}$$

If the set of states of the automaton is a subset of $\mathbb {Z}$, it is possible to quantify the variations of state values between a configuration and its image. The notion of number-conservation is inspired from physical conservation laws and states that the total sum of all states on a configuration is conserved by the global transition function.

Definition 4

(Number Conservation). A number-conserving cellular automaton (NCCA) is a cellular automaton $\mathcal {A}= (Q, f, q_0)$ such that $Q\subset \mathbb {Z}$ and for any finite configuration $\mathfrak {C}\in {\text {Conf}}(Q)$,

$$\begin{aligned} \sum _{c\in \mathbb {Z}^2} \mathcal {A}(\mathfrak {C})(c) - \mathfrak {C}(c) = 0 \end{aligned}$$

There are other commonly used definitions of number-conservation, some of which apply to infinite configurations as well, but most of these definitions are known to be equivalent [4].

In this article, we will be studying von Neumann neighborhood rotation-symmetric number-conserving cellular automata. These will be denoted RNCA from now on.

Definition 5

(Trivial Automaton). A cellular automaton $\mathcal {A}=(Q,f,q_0)$ is said to be trivial if for every configuration $\mathfrak {C}\in {\text {Conf}}(Q)$, $\mathcal {A}(\mathfrak {C}) = \mathfrak {C}$.

Definition 6

(Strong Turing Universality). A cellular automaton $\mathcal {A}$ is said to be strongly Turing-universal if it can simulate any deterministic Turing machine from a finite initial configuration.

3 Characterization of 5-States RNCA

In this section, we consider 5-states RNCA. We use the characterization by Tanimoto et al. [8] to show that all RNCA with less than 5 states are trivial and describe precisely the possible local transition functions of 5-states RNCA.

Theorem 1

(Tanimoto et al. [8]). A rotation-symmetric von Neumann neighborhood CA $\mathcal {A}=(Q, f, q_0)$ with $Q\subset \mathbb {Z}$ is number-conserving if and only if $\exists g,h: Q^2 \rightarrow \mathbb {Z},\; \forall c,u,r,d,l \in Q,$

$$\begin{aligned} f(c,u,r,d,l) =&\; c + g(c,u) + g(c,r) + g(c,d) + g(c,l) \\&+ h(u,r) + h(r,d) + h(d,l) + h(l,u) \\ g(c,u) =&-g(u,c),\qquad h(u,r) = -h(r,u) \end{aligned}$$

The function $g$ represents direct transfers of value to the central cell from its neighbors (along the horizontal and vertical directions). The function $h$ corresponds to indirect (diagonal) transfer between the neighbors of the central cell. The functions $g$ and $h$ are called flow functions of the automaton $\mathcal {A}$.

Remark: If $\mathcal {A}=(Q, f, q_0)$ is a RNCA, the function $g$ is uniquely defined by $f$ since for all states $x, y\in Q$,

$$\begin{aligned} f(x, y, y, y, y) = x + 4g(x, y) + 4h(y, y) = x + 4g(x, y) \end{aligned}$$

As for the function $h$, for all states $x, y, z, t\in Q$ the value of $h(x, y) + h(y, z) + h(z, t) + h(t, x)$ is uniquely defined but there are multiple functions matching this condition as discussed in Subsect. 3.2.

3.1 Direct Flow

Lemma 1

For a RNCA $\mathcal {A}=(Q,f,q_0)$ with flow functions $g$ and $h$, if $g\equiv 0$ then $\mathcal {A}$ is trivial.

Proof

We show that if the automaton is not trivial, it must have infinitely many states. According to Theorem 1, if $g\equiv 0$, the local transition function of the automaton is

$$\begin{aligned} f(c,u,r,d,l) = c + h(u, r) + h(r, d) + h(d, l) + h(l, u) \end{aligned}$$

If $\mathcal {A}$ is not trivial, there exist states $c, u, r, d, l\in Q$ and an integer $\delta \ne 0$ such that

$$\begin{aligned} f(c,u,r,d,l) = c + \delta \end{aligned}$$

so $h(u, r) + h(r, d) + h(d, l) + h(l, u)=\delta$ and for any state $q\in Q$,

$$\begin{aligned} f(q,u,r,d,l) = q + h(u, r) + h(r, d) + h(d, l) + h(l, u) = q + \delta \end{aligned}$$

This means that for any $q\in Q$, $(q+\delta )$ is also a state of $\mathcal {A}$ which is not possible if $Q$ is finite.   $\square$

Lemma 2

Let $\mathcal {A}= (Q, f, q_0)$ be a RNCA with flow functions $g$ and $h$. For any two states $a,b\in Q$ if we denote $g(a,b)=\alpha$, then

$$\begin{aligned} \{a, a + \alpha , a + 2\alpha , a + 3\alpha , a + 4\alpha , b, b - \alpha , b - 2\alpha , b - 3\alpha , b - 4\alpha \} \subseteq Q \end{aligned}$$

Proof

We know that

$$\begin{aligned} g(a,b)&= -g(b,a) = \alpha ,&g(a,a)&= g(b,b) = 0,\\ h(a,b)&= -h(b,a),&h(a,a)&= h(b,b) = 0 \end{aligned}$$

By Theorem 1, we have

$$\begin{aligned} f(a,a,a,a,b)&= a + 3g(a,a) + g(a,b) + h(a,b) + h(b,a) + 2h(a,a)\\&= a + g(a,b) = a + \alpha \end{aligned}$$

Similarly, we get

$$\begin{aligned} f(a,a,a,b,b)&= a + 2\alpha ,&f(a,a,b,b,b)&= a + 3\alpha ,&f(a,b,b,b,b)&= a + 4\alpha , \\ f(b,b,b,b,a)&= b - \alpha ,&f(b,b,b,a,a)&= b - 2\alpha ,&f(b,b,a,a,a)&= b - 3\alpha , \\ f(b,a,a,a,a)&= b - 4\alpha \end{aligned}$$

   $\square$

As a consequence of Lemmas 1 and 2, if a RNCA $\mathcal {A}=(Q, f, q_0)$ with flow functions $g$ and $h$ is not trivial, there exist two states $a,b\in Q$ such that $g(a, b) = \alpha > 0$ and the set of states of the automaton contains 5 elements in arithmetic progression from $a$ of difference $\alpha$. Since the 5 first elements of the arithmetic progression from $b$ of difference $-\alpha$ are also in $Q$, the only way for the CA to have only 5 states is that

$$\begin{aligned} \begin{array}{l} b = a + 4\alpha \\ \text {and}\quad \left\{ \begin{array}{rl} g(a, b) &{}= \alpha \\ g(b, a) &{}= -\alpha \\ g(x, y) &{}= 0 \quad \text {otherwise}\\ \end{array}\right. \end{array} \end{aligned}$$

3.2 Indirect Flow

Let us now consider the possibilities for $h$. The function $h$ is slightly more complex than $g$ because it is only properly characterized on cycles: the exact value of $h(a,b)$ for two states has no meaning in terms of CA dynamics, the real constraints are on the sums $h(a,b)+h(b,c)+h(c,d)+h(d,a)$ for states $a,b,c,d$.

Definition 7

Given a finite set $Q\subseteq \mathbb {Z}$ and a function $h:Q^2\rightarrow \mathbb {Z}$ such that for all $a,b\in Q$, $h(a,b)=-h(b,a)$, we define the cyclic extension $\widetilde{h}$ of $h$ as

$$\begin{aligned} \widetilde{h} : \left\{ \begin{array}{rcl} Q^* &{} \rightarrow &{} \mathbb {Z}\\ (q_1,q_2,\ldots , q_n) &{} \mapsto &{} h(q_1,q_2)+h(q_2,q_3)+\ldots +h(q_{n-1}, q_n) + h(q_n, q_1) \end{array}\right. \end{aligned}$$

Note that although $\widetilde{h}$ is entirely defined by $h$, different functions can have the same cyclic extension. For instance if $h'(x,y) = y-x+h(x,y)$ then $\widetilde{h} = \widetilde{h'}$. However, in Theorem 1 only the cyclic extension of $h$ is actually used to define the behavior of the automaton.

The function $\widetilde{h}$ is entirely defined by its values on triples:

$\forall q_1, q_2, \ldots , q_n \in Q,$

$$\begin{aligned} \widetilde{h}(q_1, q_2, \ldots , q_n) =\;&h(q_1, q_2)+\ldots +h(q_n, q_1) \\ =\;&h(q_1,q_2) + h(q_2,q_3) + h(q_3,q_1) \\&+ h(q_1,q_3) + h(q_3,q_4) + h(q_4,q_1) \\&+ \ldots \\&+ h(q_1,q_{n-1}) + h(q_{n-1},q_n) + h(q_n, 1) \\ =\;&\widetilde{h}(q_1,q_2,q_3) + \widetilde{h}(q_1,q_3,q_4) + \ldots + \widetilde{h}(q_1,q_{n-1},q_n) \end{aligned}$$

Moreover, it is easy to check from the definition that $\widetilde{h}$ is

• null on pairs: $\widetilde{h}(a,b) = 0$;

• invariant by repetition of a state: $\widetilde{h}(a,a,q_1,q_2,\ldots , q_n) = \widetilde{h}(a,q_1,q_2,\ldots , q_n)$;

• invariant by rotation: $\widetilde{h}(q_1,q_2,\ldots , q_n) = \widetilde{h}(q_2,q_3,\ldots , q_n,q_1)$;

• anti-symmetric: $\widetilde{h}(q_1,q_2,\ldots , q_n)=-\widetilde{h}(q_n,q_{n-1},\ldots , q_1)$.

Let us now consider a 5-states non trivial RNCA $\mathcal {A}= (Q, f, q_0)$ with flow functions $g$ and $h$. We have already shown that the states of the automaton are $Q=\{a+i\alpha \ |\ 0\le i\le 4\}$. Without loss of generality we can renormalize the states to $Q=\{0,1,2,3,4\}$ (substracting a constant to all states and dividing by a common factor does not affect the number conservation of the CA). We also know that $g(0,4)=1$, $g(4, 0)=-1$ and for all other $x,y\in Q$, $g(x,y)=0$.

First, let us consider $x,y,z\in Q\setminus \{0\}$. From Theorem 1, we have

$$\begin{aligned} f(4,x,x,y,z)&= 4 + 2g(4,x) + g(4,y) + g(4,z) + \widetilde{h}(x,x,y,z)\\&= 4 + \widetilde{h}(x,y,z) \end{aligned}$$

This means that $(4 + \widetilde{h}(x,y,z))\in Q$ and since $4$ is the largest element of $Q$, we have $\widetilde{h}(x,y,z)\le 0$. Because $x$, $y$ and $z$ could be any state other than 0, the same reasoning gives $\widetilde{h}(z,y,x) = -\widetilde{h}(x,y,z) \le 0$ which implies $\widetilde{h}(x,y,z) = 0$.

Similarly, for states $x,y,z\in Q\setminus \{4\}$, by considering $f(0,x,x,y,z)$ we get $\widetilde{h}(x,y,z)=0$.

So the only possible non-zero triples of $\widetilde{h}$ are triples containing both $0$ and $4$. Because $\widetilde{h}(0,0,4) = \widetilde{h}(0,4) = 0$, and $\widetilde{h}(4,4,0) = \widetilde{h}(4,0) = 0$, the only possible non-zero triples of $\widetilde{h}$ are those including $0$, $4$ and a third different state.

Moreover, for $x,y\in Q\setminus \{0,4\}$, we have

$$\begin{aligned} \widetilde{h}(0,4,x,y)&= h(0,4) + h(4,x) + h(x,y) + h(y,0)\\&= h(0,4) + h(4,x) + h(x, 0) + h(0,x) + h(x,y) + h(y,0)\\&= \widetilde{h}(0,4,x) + \widetilde{h}(0,x,y) \\&= \widetilde{h}(0,4,x) \end{aligned}$$

but also

$$\begin{aligned} \widetilde{h}(0,4,x,y)&= \widetilde{h}(4,x,y,0) \\&= h(4,x) + h(x,y) + h(y,0) + h(0,4)\\&= h(4,x) + h(x,y) + h(y,4) + h(4,y) + h(y,0) + h(0,4)\\&= \widetilde{h}(4,x,y) + \widetilde{h}(4,y,0) \\&= \widetilde{h}(4,y,0) = \widetilde{h}(0,4,y) \end{aligned}$$

So for $x,y\in Q\setminus \{0,4\}$, $\widetilde{h}(0,4,x) = \widetilde{h}(0,4,y)$. All that remains to do now is consider what are the possible values for $\widetilde{h}(0,4,1)$. By considering

$$\begin{aligned} f(0,0,0,4,1)&= 0 + g(0,4) + \widetilde{h}(0,0,4,1) \\&= 1 + \widetilde{h}(0,4,1) \end{aligned}$$

we get that $(1+\widetilde{h}(0,4,1))\in Q$ so $\widetilde{h}(0,4,1) \ge -1$. Similarly, by considering $f(4,0,4,4,1)$ we get $\widetilde{h}(0,4,1) \le 1$.

The value of $\widetilde{h}(0,4,1)$ fully defines $\widetilde{h}$, as we know that the function is zero-valued on all triples not containing $0$ and $4$ and all values on triples containing $0$ and $4$ can be obtained from $\widetilde{h}(0,4,1)$ by cycle, symmetry and replacing 1 with any other state in $Q\setminus \{0,4\}$. A possible function $h$ that would correspond to such an $\widetilde{h}$ would be defined by

$$\begin{aligned} h(0,4)&= \widetilde{h}(0,4,1)\\ h(4,0)&= -\widetilde{h}(0,4,1)\\ h(x,y)&= 0 \quad \text {otherwise} \end{aligned}$$

We have therefore proved the following result

Lemma 3

If $\mathcal {A}$ is a 5-states non-trivial RNCA, there exists a constant $\beta \in \{-1,0,1\}$ such that $\mathcal {A}$ is equivalent (up to state renaming) to an RNCA with states $Q = \{0,1,2,3,4\}$ and flow functions $g$ and $h$ such that:

Remark: Choosing $\beta = 0$ corresponds to $h\equiv 0$, which leads to a very simple CA for which states 1, 2 and 3 are permanent (a cell in one of these states can never change) and the state of a cell in state 0 (resp. 4) increases (resp. decreases) by the number of its neighbors in state 4 (resp. 0).

Choosing $\beta = 1$ or $\beta = -1$ leads to two different RNCA that are mirror images of each other.

4 The Power of 5-States RNCA

In this section we use the characterization of 5-states RNCA from Lemma 3 to investigate the computational power of such automata. We show that although they cannot be strongly Turing universal, they can simulate some logical circuit elements, indicating that they can perform some sorts of computations.

4.1 Strong Universality

Theorem 2

The evolution of a 5-states RNCA $\mathcal {A}$ from a finite configuration $\mathfrak {C}$ is ultimately periodic:

$$\begin{aligned} \exists i, j\in \mathbb {N}, \quad i<j, \quad \mathcal {A}^i(\mathfrak {C}) = \mathcal {A}^j(\mathfrak {C}) \end{aligned}$$

Proof

Consider a non-trivial 5-states RNCA $\mathcal {A}$. From Lemma 3 we can assume that $\mathcal {A}= (Q, f, q_0)$ with $Q=\{0,1,2,3,4\}$ and consider that its flow functions $g$ and $h$ satisfy the descriptions of the lemma. We show that starting from a finite configuration $\mathfrak {C}_0$, non-quiescent states cannot appear arbitrarily far in any direction.

There are two cases to consider, depending on the choice of the quiescent state $q_0$. First if $q_0\in Q\setminus \{0,4\}$, we show that non-quiescent states cannot appear outside of the bounding rectangle of the starting configuration $\mathfrak {C}_0$ (see Fig. 1).

Fig. 1.

If $q_0\in Q\setminus \{0 ,4\}$, cells outside of the rectangular bounds of the initial configuration (represented in blue) remain in state $q_0$ at all times (Color figure online).

By induction, if at time $t$ all cells outside of the rectangular bounds of $\mathfrak {C}_0$ are quiescent, then each of these cells has at least 3 neighbors in state $q_0$. Since $q_0\ne 0$ and $q_0\ne 4$, for all $x\in Q$, $g(q_0,x) = \widetilde{h}(q_0,q_0,q_0,x) = 0$, so $f(q_0, q_0, q_0, q_0, x) = q_0$ and all cells outside of the rectangular bound of $\mathfrak {C}_0$ remain in state $q_0$ at time $(t+1)$.

The second case is when $q_0\in \{0,4\}$. Assume that $q_0=0$ and let $N_0$ be the total sum of all the states in $\mathfrak {C}_0$ (the argument for $q_0=4$ is similar but we consider the sum of $(q_0-q)$ for all states $q$ in $\mathfrak {C}_0$). Since $\mathcal {A}$ is number conserving, the total sum of all states in subsequent configurations of the automaton remains equal to $N_0$. Moreover, because all non-quiescent states are positive, the total number of non-quiescent states on any configuration generated from $\mathfrak {C}_0$ cannot exceed $N_0$.

If quiescent states appear arbitrarily far in one direction in the evolution of $\mathcal {A}$ from $\mathfrak {C}_0$, some cells must go from a non-quiescent state back to the quiescent state $0$ in order to keep the total number of non-quiescent states bounded. We will now assume that the direction in which the non-quiescent states appear arbitrarily far is left (it is enough to consider one direction since the automaton is rotation-symmetric).

Assume that $h(0,4)\ge 0$ and consider the situation illustrated by part (a) of Fig. 2: a cell in a non-quiescent state $x$ with 4 cells in state 0 around it, 3 on its right side and one under (for the case $h(0,4)\le 0$ we would consider the symmetric situation with a quiescent cell on top of the cell in state $x$ instead of under it). Let us see how such a cell can change to state $0$. There are two possibilities, represented by parts (b) and (c) in Fig. 2. Either $x=4$ and we can use the function $g$ to lower the state of the cell to $0$ or the contribution of $g$ on the cell is 0 and only $\widetilde{h}$ can lower the state of the cell, in which case only state 1 can be lowered to $0$.

Fig. 2.

Case study. If a cell is in the situation (a) where $x$ is a non-quiescent state, in order to change to state 0 one of the 3 cells on the right must change from state 0 to a non-quiescent state.

(b) If $x=4$, then the cell on the right of the cell in state $4$ will necessarily change to a positive state. For this cell, the contribution from $g$ will be positive (at least 1 from the central cell) and the contribution from $h$ will be 0 since $\widetilde{h}(0,4,0,y)=0$ for all states $y$.

(c) If $x=1$, then in order to change the state to $0$, the contribution from $\widetilde{h}$ must be -1 since $g(1,y)=0$ for all states $y$. We have previously chosen to consider the case $h(0,4)\ge 0$. If $h(0,4)=0$, then the contribution from $h$ is 0 and the state of the cell cannot change to 0. However if $h(0,4)=1$, then the contribution from $\widetilde{h}$ can be $-1$ only if the top neighbor is in state 4 and the left neighbor is in a state $y\in Q\setminus \{0,4\}$ (as illustrated by Fig. 2). In that case, $\widetilde{h}(4,0,0,y)=-1$ and the cell changes to state $0$. However, the cell on the top-right now has a neighbor in state 4, which means that for this cell the contribution from $g$ is at least 1. Moreover, the contribution from $\widetilde{h}$ is at least 0, since $h(0,4)=1$ and so $\widetilde{h}(0,4,x,y)\ge 0$ for all states $x,y$. This means that the cell on the top-right of the considered cell changes to a positive state.

We have shown that if a cell in the situation illustrated by part (a) of Fig. 2 changes its state to 0, then at least one of the cells from the column right of the considered cell changes from state 0 to a non-quiescent state. This means that as new non-quiescent states appear towards the left, previous non-quiescent states cannot be properly removed: in order to remove all non-quiescent states from a given column, it is necessary to create new ones on the column at its right, so as the non-quiescent states move towards the left, new ones appear towards the right. Eventually, the total number of non-quiescent states will be greater than $N_0$ which contradicts number-conservation.

So we know that the evolution $(\mathcal {A}^i(\mathfrak {C}_0))_{i\in \mathbb {N}}$ of a 5-states RNCA $\mathcal {A}$ from a finite configuration $\mathfrak {C}_0$ can only have non-quiescent states inside of a bounded area. Because there are only finitely many such bounded configurations, eventually the automaton must re-enter a previous configuration.   $\square$

Corollary 1

There are no 5-states strongly Turing universal RNCA.

Proof

The evolution of a 5-states RNCA from a finite starting configuration is ultimately periodic (Theorem 2) and therefore decidable. If such CA could simulate a Turing machine then the halting problem and all other behavioral problems on Turing machines would be decidable.   $\square$

4.2 Simulation of Logical Circuits

Although the evolution of a 5-states RNCA from a finite configuration is ultimately periodic, some non-trivial behaviors can still be observed. In particular, it is possible to simulate some key elements of boolean circuits. In this section, we consider the 5-states RNCA obtained by choosing $\beta =1$ in the characterization from Lemma 3.

Figures 3, 4 and 5 illustrate how to create a simple wire along which a signal can travel. The wire is made of two layers of state 2 (red), and the signal is represented by two cells in state 4 (yellow) that are “pushed” forward by a cell in state 1 (blue). As the signal traverses the wire, the top layer of red states is changed into blue and green states. These wires can therefore be traversed only once, which is enough for simple boolean circuit simulation but not for being used as a control circuit for a universal machine.

Fig. 3.

A signal moving through a simple wire (Color figure online).

Fig. 4.

A branching wire (Color figure online).

Fig. 5.

By using state $3$ (green) instead of state $2$ (red) on some portions of the wire, the signal moves at speed $1$ instead of speed $\frac{1}{2}$ (Color figure online).

The wires can be split in two to duplicate a signal (Fig. 4). By changing the second row of red cell into green states, the signal can be accelerated to move by one cell at each time step (Fig. 5) which can be a convenient way to synchronize signals.

As for logical gates, Figs. 6 and 7 illustrate how to implement an AND and a $\overline{A}$ AND B gate. It is known that the $\overline{A}$ AND B gate alone is sufficient to simulate a NOT and an OR gate so these elements would be sufficient for boolean operations [1].

Fig. 6.

Logical ${\text {AND}}$ gate (Color figure online).

Fig. 7.

$\overline{A}\,{\text {AND}}\,B$ gate (Color figure online).

Note that the boolean value for 0 is simply represented by the absence of a signal. Therefore, careful synchronisation is required when implementing multiple input logical gates as the possible input signals must arrive at the same time (but this can be done either by using the variable speed wires from Fig. 5 or by artificially increasing the length of a wire with a detour).

However, until now we have been unable to devise a wire crossing pattern which is required for a full simulation of boolean circuits. Because of the destructive nature of signal propagation along a wire, wire crossing might prove impossible to implement.