Two Graphs: Resolving the Periodic Reversibility of One-dimensional Finite Cellular Automata

Finite cellular automaton (FCA) is the most basic and important concept in this paper. It is usually defined by a quintuple: FCA = $\{Z^{d},S,N_{m},f,b\}$

• 1.

  $Z^{d}$ is the dimension of the cellular space. Each point $c\in Z^{d}$ is called a cell. In this paper, the dimension $d=1$. The number of cells in $Z^{1}$ is denoted as $n$ in this paper.

• 2.

  $S=\{0,1,\ldots,s-1\}$ is a finite set of states representing a cell’s state in CA. At any time, the state of each cell is an element in this set. We use $s$ to count the number of elements in this set.

• 3.

  $N_{m}=(\vec{n}_{1},\vec{n}_{2},\ldots,\vec{n}_{m})$ represents neighbor vectors, where $\vec{n}_{i}\in\mathbb{Z}^{d}$, and $\vec{n}_{i}\neq\vec{n}_{j}$ when $i\neq j$ $(i,j=1,2,\ldots,m)$. Thus, the neighbors of the cell $\vec{n}\in\mathbb{Z}^{d}$ are the $m$ cells $\vec{n}+\vec{n}_{i},i=1,2,\cdots,m$. The neighborhood size of this CA is denoted as $m$ in this paper. We use $l+1+r$ to express a function containing $l$ neighbor on the left and $r$ neighbor on the right. For example, the rule of an elementary FCA can be expressed as $1+1+1$.

• 4.

  $f$: $S^{m}\rightarrow S$ is the local rule (or simply the rule). The rule maps the current state of a cell and all its neighbors to this cell’s next state.

• 5.

  $b$ is the type of boundary which includes the null boundary ($b=``n"$) and the periodic boundary ($b=``p"$). The algorithm in this paper is also applicable to the reflective boundary, but it will not be further elaborated upon.

A configuration is a mapping $C$ : $Z^{d}\rightarrow S$ which assigns each cell a state. Function $\tau$ : $C\rightarrow C$ is used to represent the global transformation of $f$.

The Wolfram number is a shorthand for the rule. For instance, for a $FCA=\{Z^{1},\{0,1\},N_{3},f,b\}$ the rule $f$ is shown as follows:

Then, we can use the Wolfram number 11110000 to abbreviate this rule. This FCA can be represented as a quintuple $\{Z^{1},\{0,1\},N_{3},11110000,b\}$. The length of the Wolfram number is $s^{m}$.

There are several different boundaries of one-dimensional FCA. The most important ones studied at present are the null (fixed) boundary and the periodic boundary. Now, we will introduce these boundaries respectively.

Now we suppose the rule of an FCA is $1+1+1$, Then the leftmost cell has no left neighbor, and the rightmost cell has no right neighbor. In this case, the leftmost and rightmost cells in the next transformation will lose their corresponding value. To avoid this, we need to fill their neighbors outside the boundary with certain values. These two boundaries correspond to different values of their neighbors.

The null boundary is also called the zero boundary, which always fills “$0$” in the cell outside the configuration. The example of a null boundary is shown in Fig. 1.

Periodic boundary regards the configuration as a circle, which fills the cells left-outside the configuration according to the rightmost cells. The example of the periodic boundary is also shown in Fig. 2.

Our goal is to quickly determine whether any given FCA is strictly reversible or strictly irreversible. If it is neither, we should obtain its reversibility sequence directly by calculating the period. Specifically, for various widely used boundary conditions, the algorithm should be fully compatible (without significant differences).

Amoroso’s algorithm is used to determine the surjectivity of infinite CA. It can be described in brief step by step.

Step 1

For a CA with neighborhood size $m$ and state set $S=\{0,1,\ldots,p-1\}$, get its local rule $f$.

Step 2

If $f(m)=0$, add $m$ into the root node.

Step 3

For each node $M$ in layer $i$ $(i\geq 0)$, construct its children $M_{0},M_{1},\cdots,M_{p-1}$. For each tuple $a_{1}a_{2}\cdots a_{m}$ in $M$ and all $0\leq j<p$, if $f(a_{2}a_{3}\cdots a_{m}j)=t$, then $a_{2}a_{3}\cdots a_{m}j$ is added to $M_{t}$. If a node is the same as a node that has appeared before, its children will not be constructed. If there are not any m-tuples in a node, then the CA has a Garden-of-Eden which decides the CA is not surjective.

Step 4

If the three steps above are completed and the CA is not decided as non-surjective, then the CA is surjective.

In the previous section, we introduce the construction of the reversibility graph $G_{R}$ and use it to determine if an FCA is strictly reversible. For FCA with a specific number of cells, $G_{R}$ remains available, but the concept of “depth” needs to be introduced.

The aforementioned theorems are still not sufficient. We can find that in Fig. 3 left, 000(01)*10 is also a “Garden-of-Eden” configuration, yet we have not included it in our calculations. To address this issue, we define a new type of graph called the ”circuit graph.”

These two corollaries can help us make reversibility determinations more quickly and directly, sometimes even eliminating the need to construct $G_{C}$. In Example 1, we can determine that the FCA is irreversible when the number of cells is greater than or equal to 2, simply by finding there is a negative vertex in $G_{R}$ with a self-circuit.

Through the aforementioned analysis, we have resolved the most significant issues. Only two minor problems remain to be addressed: one is finding all the circuits in $G_{R}$, and the other is the construction of $G_{C}$.

We can find all the circuits of $G_{R}$ in $O(sVl)$, where the FCA has $s$ states and $G_{R}$ has $V$ vertices and $l$ circuits.

Thus, the reversibility problem of one-dimensional FCA has been efficiently resolved. Actually, determining whether an FCA with $n$ cells is reversible is not straightforward. However, we approach this problem from a novel perspective: we list all the irreversible scenarios, and what remains are naturally reversible, as a substitute for individually determining the reversibility for every cell count. This approach significantly simplifies the complexity of analyzing the entire problem. Next, let’s fully recapitulate our algorithm.

Step 1

Construct $G_{R}$ according to Algorithm 1 with the complexity of $O(s^{m}V)$.

Step 2

Find all circuits using Johnson’s algorithm with the complexity of $O(sVl)$ [10].

Step 3

Construct $G_{C}$ according to Algorithm 2 with the complexity of $O(Vl^{2})$.

Step 4

List all irreversible number polynomials and solve the reversibility sequence.

We list several reversibility sequences for a series of rules in Table 1. Some of the rules in this chapter are linear and can be compared with existing results for linear FCA to verify the correctness of our algorithm. The underlined portions represent a period. $s$ is the number of states; $m$ is the neighborhood size; $b$ is the boundary and $f$ is the rule.

During the experimental process, we found that a large number of nonlinear FCA have a period of 1, meaning that starting from a certain length, configurations of greater lengths are all non-reversible. However, there is still a small portion of nonlinear FCA whose reversibility exhibits periodicity (e.g. the rule 11010010).