Sequentializing Cellular Automata

Abstract

We study the problem of sequentializing a cellular automaton without introducing any intermediate states, and only performing reversible permutations on the tape. We give a decidable characterization of cellular automata which can be written as a single left-to-right sweep of a bijective rule from left to right over an infinite tape.

J. Kari—Research supported by the Academy of Finland grant 296018.

1 Introduction

Cellular automata (CA) are models of parallel computation, so when implementing them on a sequential architecture, one cannot simply update the cells one by one – some cells would see already updated states and the resulting configuration would be incorrect. The simplest-to-implement solution is to hold two copies of the current configuration in memory, and map $(x,x) \mapsto (x,G(x)) \mapsto (G(x),G(x))$. This is wasteful in terms of memory, and one can, with a bit of thinking, reduce the memory usage to a constant by simply remembering a ‘wave’ containing the previous values of the r cells to the left of the current cell, where r is the radius of the CA.

Here, we study the situation where the additional memory usage can be, in a sense, dropped to zero – more precisely we remember only the current configuration $x \in S^\mathbb {Z}$, and to apply the cellular automaton we sweep a permutation $\chi : S^m \rightarrow S^m$ from left to right over x (applying it consecutively to all length-m subwords of x). The positions where the sweep starts may get incorrect values, but after a bounded number of steps, the rule should start writing the image of the cellular automaton. We formalize this in two ways, with ‘sliders’ and ‘sweepers’, which are two ways of formally dealing with the problem that sweeps ‘start from infinity’.

It turns out that the cellular automata that admit a sliding rule are precisely the ones that are left-closing (Definition 11), and whose number of right stairs (see Definition 14) of length 3m divides $|S|^{3m}$ for large enough m. This can be interpreted as saying that the average movement ‘with respect to any prime number’ is not to the right. See Theorem 19 and Theorem 25 for the precise statements, and Sect. 4 for decidability results.

We introduce the sweeping hierarchy where left-to-right sweeps and right-to-left sweeps alternate, and the closing hierarchy where left-closing and right-closing CA alternate. We show that the two hierarchies coincide starting from the second step. We do not know if the hierarchies collapse on a finite level.

1.1 Preliminaries

We denote the set of integers by $\mathbb {Z}$. For integers $i\le j$ we write [i, j) for $\{ x\in \mathbb {Z}\mid i\le x < j\}$ and [i, j] for $[i,j)\cup \{j\}$; furthermore $[i,\infty )=\{ x\in \mathbb {Z}\mid i\le x\}$ and $(-\infty ,i)=\{ x\in \mathbb {Z}\mid x< i\}$ have the obvious meaning. Thus $[0,\infty )$ is the set of non-negative integers which is also denoted by $\mathbb {N}_0$.

Occasionally we use notation for a set M of integers in a place where a list of integers is required. If no order is specified we assume the natural increasing order. If the reversed order is required we will write $M^R$.

For sets A and B the set of all functions $f:A\rightarrow B$ is denoted $B^A$. For $f\in B^A$ and $M\subseteq A$ the restriction of f to M is written as $f|_M$ or sometimes even $f_M$. Finite words $w\in S^n$ are lists of symbols, e.g. mappings $w:[0,n) \rightarrow S$. Number n is the length of the word. The set of all finite words is denoted by $S^*$.

Configurations of one-dimensional CA are biinfinite words $x:\mathbb {Z}\rightarrow S$. Instead of x(i) we often write $x_i$. We define the left shift $\sigma : S^\mathbb {Z} \rightarrow S^\mathbb {Z}$ by $\sigma (x)_i = x_{i+1}$. The restriction of x to a subset $(-\infty ,i)$ gives a left-infinite word for which we write $x_{(-\infty ,i)}$; for a right-infinite word we write $x_{[i,\infty )}$. These are called half-infinite words. Half-infinite words can also be shifted by $\sigma$, and this is defined using the same formula. The domain is shifted accordingly so for $x\in S^{[i,\infty )}$ we have $\sigma (x)\in S^{[i-1,\infty )}$.

We use a special convention for concatenating words: Finite words ‘float’, in the sense that they live in $S^n$ for some n, without a fixed position, and $u \cdot v$ denotes the concatenation of u and v as an element of $S^{|u| + |v|}$. Half-infinite configurations have a fixed domain $(-\infty ,i]$ or $[i,\infty )$ for some i, which does not change when they are concatenated with finite words or other half-infinite configurations, while finite words are shifted suitably so that they fill the gaps exactly (and whenever we concatenate, we make sure this makes sense).

More precisely, for $w \in S^*$ and $y \in S^{(-\infty , i]}$, we have $y \cdot w \in S^{(-\infty ,i+|w|]}$ and for $w \in S^*$ and $z \in S^{[i,\infty )}$ we have $w \cdot z \in S^{[i-|w|,\infty )}$ (defined in the obvious way). For a word $w \in S^*$ and half-infinite words $y \in S^{(-\infty ,i)}$ and $z \in S^{[i+n,\infty )}$ we write $y \cdot w \cdot z$ for the obvious configuration in $S^\mathbb {Z}$, and this is defined if and only if $|w| = n$.

The set $S^\mathbb {Z}$ of configurations is assigned the usual product topology generated by cylinders. A cylinder defined by word $w\in S^n$ at position $i\in \mathbb {Z}$ is the set

$$ [w]_{[i,i+n)} = \{x\in S^\mathbb {Z}\ |\ x_{[i,i+n)}=w\} $$

of configurations that contain word w in position $[i,i+n)$. Cylinders are open and closed, and the open sets in $S^\mathbb {Z}$ are precisely the unions of cylinders. We extend the notation also to half-infinite configurations, and define

$$ [y]_{D} = \{x\in S^\mathbb {Z}\ |\ x_{D}=y\}. $$

for $D = [i,\infty )$ and $D = (\infty , i]$, and any $y \in S^D$. These sets are closed in the topology.

Because of a page limit for the submissions only some proofs are included in the version for the conference proceedings. An extended version with all proofs can be found on arXiv.org [1].

2 Sliders and Sweepers

A block rule is a function $\chi : S^m \rightarrow S^m$. Given a block rule $\chi$ we want to define what it means to “apply $\chi$ from left to right once at every position”. We provide two alternatives, compare them and characterize which cellular automata can be obtained by them. The first alternative, called a slider, assumes a bijective block rule $\chi$ that one can slide along a configuration left-to-right or right-to-left to transition between a configuration y and its image f(y). The second alternative, called a sweeper, must consistently provide values of the image f(y) when sweeping left-to-right across y starting sufficiently far on the left.

We first define what it means to apply a block rule on a configuration.

Definition 1

Let $\chi : S^m \rightarrow S^m$ be a block rule and $i\in \mathbb {Z}$. The application of $\chi$ at coordinate i is the function $\chi ^i:S^\mathbb {Z}\longrightarrow S^\mathbb {Z}$ given by $\chi ^i(x)_{[i,i+m)} = \chi (x_{[i,i+m)})$ and $\chi ^i(x)_j=x_j$ for all $j\not \in [i,i+n)$. More generally, for $i_1,\ldots ,i_k \in \mathbb {Z}$ we write

$$ \chi ^{i_1,\ldots ,i_k} = \chi ^{i_k} \circ \cdots \circ \chi ^{i_2} \circ \chi ^{i_1}. $$

When $m > 1$, it is meaningless to speak about “applying $\chi$ to each cell simultaneously”: An application of $\chi$ changes the states of several cells at once. Applying it slightly shifted could change a certain cell again, but in a different way.

We next define finite and infinite sweeps of block rule applications with a fixed start position.

Definition 2

Given a block rule $\chi$ for $i,j\in \mathbb {Z}$, $i\le j$, define $\chi ^{[i,j]}=\chi ^j\circ \cdots \circ \chi ^i$; analogously let $\chi ^{[i,j)}=\chi ^{j-1}\circ \cdots \circ \chi ^i$. For any configuration $x\in S^{\mathbb {Z}}$ and fixed $i\in \mathbb {Z}$ the sequence of configurations $x^{(j)}=\chi ^{[i,j]}(x)$ for $j\in [i,\infty )$ has a limit (point in the topological space $S^{\mathbb {Z}}$) for which we write ${\chi }^{i+}(x)$.

Analogously, for a block rule $\xi$ the sequence of configurations $x^{(j)} = \xi ^{[j,i)^R}(x)$ for $j\in (-\infty ,i)$ has a limit for which we write ${\xi }^{i-}(x)$.

It should be observed that in the definition of ${\chi }^{i+}(x)$ one has $i<j$ and the block rule is applied at successive positions from left to right. On the other hand $j<i$ is assumed in the definition of ${\xi }^{i-}(x)$ and since the ${}^{{}^R}$ in $\xi ^{[j,i)^R}$ indicates application of $\xi$ at the positions in the reverse order, i.e. $i-1, i-2, \dots , j$, the block rule is applied from right to left.

The reason the limits always exist in the definition is that the value of $x^{(j)}_i$ changes at most m times, on the steps where the sweep passes over the cell i.

Example 3

Let $S=\{0,1\}$ and consider the block rule $\chi :S^{[0,2)}\rightarrow S^{[0,2)}: (a,b)\mapsto (b,a)$. For consistency with the above definition denote by $\xi$ the inverse of $\chi$ (which in this case happens to be $\chi$ again). Let $s\in S$ and $y\in S^{\mathbb {Z}}$. We will look at the configuration $x\in S^{\mathbb {Z}}$ with

$$ x_i = {\left\{ \begin{array}{ll} y_{i+1}, &{}\text { if } i<0 \\ s, &{}\text { if } i=0 \\ y_{i}, &{}\text { if } i>0 \end{array}\right. } $$

The application of $\chi$ successively at positions $0, 1, 2, \dots$ always swaps state s with its right neighbor. Since cell j can only possibly change when $\chi ^{j-1}$ or $\chi ^j$ is applied, each cell enters a fixed state after a finite number of steps; see also the lower part of Fig. 1 starting at the row with configuration x.

Fig. 1.

A sequence of configurations with the center cell at position 0. Starting with configuration x in the middle when going downward the swapping rule $\chi$ is applied to blocks [0, 1], [1, 2], etc., and going from x upward rule $\xi =\chi$ is applied to blocks $[-1,0]$, $[-2,-1]$ and so on.

Example 4

Let $S=\{0,1\}$ and consider the block rule $\chi :S^{[0,2)}\rightarrow S^{[0,2)}: (a,b)\mapsto (a+b,b)$. Then sliding this rule over a configuration $x \in \{0,1\}^\mathbb {Z}$ produces the image of x in the familiar exclusive-or cellular automaton with neighborhood $\{0,1\}$ (elementary CA 102). We will see in Example 21 that the exclusive-or CA with neighborhood $\{-1,0\}$ can not be defined this way.

2.1 Definition of Sliders

Definition 5

A bijective block rule $\chi$ with inverse $\xi$ defines a slider relation $F \subset S^\mathbb {Z}\times S^\mathbb {Z}$ by $(y, z) \in F$ iff for some $x \in S^\mathbb {Z}$ and some $i\in \mathbb {Z}$ we have $\xi ^{i-}(x) = y$ and $\chi ^{i+}(x) = z$. We call the pair (x, i) a representation of $(y, z)\in F$.

Note that every $(x,i)\in S^\mathbb {Z}\times \mathbb {Z}$ is a representation of exactly one pair, namely $(\xi ^{i-}(x),\chi ^{i+}(x))\in F$.

Lemma 6

Let (x, i) be a representation of $(y, z)\in F$ under a bijective block rule $\chi$ of block length n. Then $x_{(-\infty ,i)} = z_{(-\infty ,i)}$ and $x_{[i+n,\infty )} = y_{[i+n,\infty )}$.

Proof

Applying block rule $\chi$ at positions $j\ge i$ in x never changes cells at positions $k<i$. Therefore $x_k = ({\chi }^{i+}(x))_k = z_k$ proving the first part. The second part follows analogously.    $\square$

Lemma 7

Let $(y,z)\in F$ be fixed. For all $i\in \mathbb {Z}$ denote

$$ R_i=\{x\in S^\mathbb {Z}\ |\ (x,i) \text{ is } \text{ a } \text{ representation } \text{ of } (y, z)\}. $$

For $i<j$ the function $\chi ^{[i,j)}: R_i\longrightarrow R_j$ is a bijection, with inverse $\xi ^{[i,j)^R}$. All $R_i$ have the same finite cardinality.

Proof

The claim follows directly from the definition and the facts that

$$\begin{aligned} \chi ^{j+}\circ \chi ^{[i,j)}=\chi ^{i+} \text{ and } \xi ^{j-}\circ \chi ^{[i,j)} =\xi ^{i-}, \end{aligned}$$

(1)

and that $\chi ^{[i,j)}$ and $\xi ^{[i,j)^R}$ are inverses of each other.

More precisely, if $x\in R_i$ then $z=\chi ^{i+}(x)=\chi ^{j+}(\chi ^{[i,j)}(x))$ and $y=\xi ^{i-}(x)=\xi ^{j-}(\chi ^{[i,j)}(x))$ so $\chi ^{[i,j)}(x)\in R_j$. This proves that $\chi ^{[i,j)}$ maps $R_i$ into $R_j$. This map is injective. To prove surjectivity, we show that for any $x'\in R_j$ its pre-image $\xi ^{[i,j)^R}(x')$ is in $R_i$. Composing the formulas in (1) with $\xi ^{[i,j)^R}$ from the right gives $\chi ^{j+}=\chi ^{i+} \circ \xi ^{[i,j)^R}$ and $\xi ^{j-} =\xi ^{i-}\circ \xi ^{[i,j)^R}$, so as above we get $z=\chi ^{j+}(x')=\chi ^{i+}(\xi ^{[i,j)^R}(x'))$ and $y=\xi ^{j-}(x')=\xi ^{i-}(\xi ^{[i,j)^R}(x'))$, as required.

The fact that the cardinalities are finite follows from Lemma 6: there are at most $|S|^n$ choices of $x_{[i,i+n)}$ in $x\in R_i$.    $\square$

Lemma 8

A slider relation $F \subset S^\mathbb {Z}\times S^\mathbb {Z}$ defined by a bijective block rule $\chi$ is closed and shift-invariant, and the projections $(y,z)\mapsto y$ and $(y,z)\mapsto z$ map F surjectively onto $S^\mathbb {Z}$.

Proof

By Lemma 7 every $(y,z)\in F$ has a representation (x, 0) at position 0. Therefore, the relation F is closed as the image of $S^\mathbb {Z}$ in the continuous map $x \mapsto (\xi ^{0-}(x), \chi ^{0+}(x))$.

Clearly (x, i) is a representation of (y, z) if and only if $(\sigma (x),i-1)$ is a representation of $(\sigma (y),\sigma (z))$. Hence the relation F is shift-invariant.

The image of F under the projection $(y,z)\mapsto z$ is dense. To see this, consider any finite word w and a configuration x with $x_{[-|w|,0)}=w$. The pair (x, 0) represents some $(y,z)\in F$, and because $z=\chi ^{0+}(x)$ we have $z_{[-|w|,0)}=w$. The denseness follows now from shift invariance and the fact that w was arbitrary. The image of F under the projection is closed so the image is the whole $S^\mathbb {Z}$.

The proof for the other projection is analogous.    $\square$

Corollary 9

If $F \subset S^\mathbb {Z}\times S^\mathbb {Z}$ defined by a bijective block rule $\chi$ is a function (that is, if for all $y\in S^\mathbb {Z}$ there is at most one $z\in S^\mathbb {Z}$ such that $(y,z)\in F$) then this function $f:y\mapsto z$ is a surjective cellular automaton.

Proof

Because the projections $(y,z)\mapsto y$ and $(y,z)\mapsto z$ are onto, the function f is full and surjective. Because the relation $F \subset S^\mathbb {Z}\times S^\mathbb {Z}$ is closed, the function f is continuous. As it is continuous and shift-invariant, it is a cellular automaton.    $\square$

Definition 10

Let $\chi$ be a bijective block rule such that the slider relation it defines is a function $f:S^\mathbb {Z}\longrightarrow S^\mathbb {Z}$. The surjective cellular automaton f is called the slider defined by $\chi$.

Example 3 indicates that the slider for the block rule swapping two states is the left shift. By Corollary 9 every slider is a surjective CA. But not every surjective CA is a slider. This will follow from an exact characterization of which cellular automata are sliders below.

2.2 Characterization of Sliders

We start by improving Corollary 9, by showing that sliders are left-closing cellular automata.

Definition 11

Two configurations y and $y'$ are right-asymptotic if there is an index $i\in \mathbb {Z}$ such that $y_{[i,\infty )}=y'_{[i,\infty )}$. They are called left-asymptotic if there is an index $i\in \mathbb {Z}$ such that $y_{(-\infty ,i)} = y'_{(-\infty ,i)}$. A CA f is left-closing if for any two different right-asymptotic configurations y and $y'$ we have $f(y)\not = f(y')$. Right-closing CA are defined symmetrically using left-asymptotic configurations.

Lemma 12

A slider is a left-closing cellular automaton.

Proof

Let slider f be defined by a bijective block rule $\chi : S^m \rightarrow S^m$, so that f is a surjective cellular automaton. Let $\xi$ be the inverse of $\chi$.

Suppose f is not left-closing, so that there exist two distinct right-asymptotic configurations y and $y'$ such that $f(y) = f(y')$. We may suppose the rightmost difference in y and $y'$ is at the origin. Let r be a radius for the local rule of f, where we may suppose $r \ge m$, and let $y_{[-2r, 2r]} = w_0 v, y'_{[-2r, 2r]} = w_1 v$ where $|w_1| = |w_2| = 2r+1$. We can apply the local rule of f to words, shrinking them by r symbols on each side, and write $F : S^* \rightarrow S^*$ for this map. Since y and $y'$ have the same f-image, we have $F(w_0 v) = F(w_1 v)$.

Let n be such that $2^n > |S|^m$ and for each $k \in \{0,1\}^n$, define the configuration

$$ y_k = ...0000 w_{k_1} v w_{k_2} v \cdots v w_{k_n} v . 0000... $$

where the right tail of 0s begins at the origin. For each $y_k$, pick a point $x_k$ representing $(y_k, f(y_k))$ at the origin. By the pigeon hole principle, there exist $k \ne k'$ such that $(x_k)_{[0,m)} = (x_{k'})_{[0,m)}$. Let j be the maximal coordinate where k and $k'$ differ.

Now, the rightmost difference in $y_k$ and $y_{k'}$ is in coordinate $R = -2r-1 - (4r+1)(n-j)$ (the last coordinate of the word $w_{k_j}$). We have $f(y_k)_{[R-r, \infty )} = f(y_{k'})_{[R-r, \infty )}$ by the assumption that j is the rightmost coordinate where k and $k'$ differ, and by $F(w_0 v) = F(w_1 v)$. Thus we also have $(x_k)_{[R-r, 0)} = (x_{k'})_{[R-r, 0)}$, since $\chi ^{0+}(x_k) = f(y_k)$ and $\chi ^{0+}(x_{k'}) = f(y_{k'})$ and these sweeps do not modify coordinates in $[R-r, 0)$. Recall that we have $(x_k)_{[0,m)} = (x_{k'})_{[0,m)}$ by the choice of k and $k'$, so $(x_k)_{[R-r, m)}$ and $(x_{k'})_{[R-r, m)}$.

Now, we should have $\xi ^{0-}(x_k) = y_k$ and $\xi ^{0-}(x_{k'}) = y_{k'}$, in particular we should have $\xi ^{0-}(x_k)_R \ne \xi ^{0-}(x_{k'})_R$. But this is impossible: $\xi ^{0-}(x_k)_R$ is completely determined by $(x_k)_{[R-m+1, m)}$ and similarly $\xi ^{0-}(x_{k'})_R$ is determined by $(x_{k'})_{[R-m+1, m)}$, but $(x_k)_{[R-m+1, m)} = (x_{k'})_{[R-m+1, m)}$ since $(x_k)_{[R-r, m)} = (x_{k'})_{[R-r, m)}$ and $r \ge m.$    $\square$

In the rest of this section, we only consider the case when the slider relation F that $\chi$ defines is a function.

Next we analyze numbers of representations. We call a representation (x, i) of a pair (y, z) simply a representation of configuration y, because $z=f(y)$ is determined by y. Let R(y, i) be the set of configurations x such that (x, i) is a representation of y. By Lemma 6 the elements of R(y, i) have the form $x=f(y)_{(-\infty ,i)} \cdot w \cdot y_{[i+n,\infty )}$ for some word $w\in S^n$ where n is the block length of $\chi$.

By Lemma 7 the cardinality of the set R(y, i) is independent of i. Let us denote by N(y) this cardinality. It turns out that the number is also independent of the configuration y.

Lemma 13

$N(y)=N(y')$ for all configurations $y,y'$.

Proof

Let n be the block length of rule $\chi$.

• (i) Assume first that $y,y'$ are left-asymptotic. There is an index $i\in \mathbb {Z}$ such that $y_{(-\infty ,i)} = y'_{(-\infty ,i)}$. Then for any z we have that $z_{(-\infty ,i)}y_{[i,\infty )}\in R(y,i-n)$ if and only if $z_{(-\infty ,i)}y'_{[i,\infty )}\in R(y',i-n)$. This gives a bijection between $R(y,i-n)$ and $R(y',i-n)$ so that $N(y)=|R(y,i-n)|=|R(y',i-n)|=N(y')$.

• (ii) Assume then that $y,y'$ are right-asymptotic. Also f(y) and $f(y')$ are right-asymptotic so there is an index $i\in \mathbb {Z}$ such that $f(y)_{[i,\infty )} = f(y')_{[i,\infty )}$. Consider $z_{[i,\infty )}$ be such that $x=f(y)_{(-\infty ,i)}z_{[i,\infty )}\in R(y,i)$. Then $\chi ^{i+}(x) = f(y)$. Consider then $x'=f(y')_{(-\infty ,i)}z_{[i,\infty )}$ obtained by replacing the left half $f(y)_{(-\infty ,i)}$ by $f(y')_{(-\infty ,i)}$. Because $f(y)_{[i,\infty )} = f(y')_{[i,\infty )}$ we have that $\chi ^{i+}(x') = f(y')$. The configuration $y''$ represented by $(x',i)$ is right-asymptotic with $y'$ and satisfies $f(y'')=f(y')$. Because f is left-closing by Lemma 12, we must have $y''=y'$. We conclude that $f(y)_{(-\infty ,i)}z_{[i,\infty )}\in R(y,i)$ implies that $f(y')_{(-\infty ,i)}z_{[i,\infty )}\in R(y',i)$, and the converse implication also holds by a symmetric argument. As in (i), we get that $N(y)=|R(y,i)|=|R(y',i)|=N(y')$.

• (iii) Let $y,y'$ be arbitrary. Configuration $y''=y_{(-\infty ,0)}y'_{[0,\infty )}$ is left-asymptotic with y and right-asymptotic with $y'$. By cases (i) and (ii) above we have $N(y)=N(y'')=N(y')$.

   $\square$

As N(y) is independent of y we write N for short.

Next we define right stairs. They were defined in [2] for reversible cellular automata – here we generalize the concept to other CA and show that the concept behaves well when the cellular automaton is left-closing. A right stair is a pair of words that can be extracted from two consecutive configurations x and f(x) that coincide with y and z, respectively, as shown in Fig. 2. The precise definition is as follows.

Fig. 2.

A right stair (v, w) of length $3\,\mathrm{m}$ connecting y and z, confirmed by x at position $i=0$.

Definition 14

Let $f:S^\mathbb {Z}\longrightarrow S^\mathbb {Z}$ be a cellular automaton, and let m be a positive integer. Let $y\in S^{[i+3m,\infty )}$ be a right infinite word and let $z\in S^{(-\infty ,i)}$ be a left-infinite word.

• A pair of words $(v,w)\in S^{2m}\times S^{2m}$ is a right stair connecting (y, z) if there is a configuration $x\in S^{\mathbb {Z}}$ such that $vy=x_{[i+m,\infty )}$ and $zw=f(x)_{(-\infty ,i+2m)}$.

• The stair has length $3\,\mathrm{m}$ and it is confirmed (at position i) by configuration x.

• We write $\varPsi _{3m}(y,z)$ for the set of all right stairs of length $3\,\mathrm{m}$ connecting (y, z).

• We write $\varPsi _{3m}$ for the union of $\varPsi _{3m}(y,z)$ over all y and z.

Due to shift invariance, x confirms $(v,w)\in \varPsi _{3m}(y,z)$ if and only if $\sigma (x)$ confirms $(v,w)\in \varPsi _{3m}(\sigma (y),\sigma (z))$. This means that $\varPsi _{3m}(y,z)=\varPsi _{3m}(\sigma (y),\sigma (z))$, so it is enough to consider $i=0$ in Definition 14. In terms of cylinders, $(v,w)\in \varPsi _{3m}$ if and only if $f([v]_{[m,3m)})\cap [w]_{[0,2m)} \ne \emptyset$.

Fig. 3.

(a) An illustration for Lemma 15, and (b) an illustration for Corollary 16(b) and for Lemma 18.

We need the following known fact concerning left-closing CA. It appears as Proposition 5.44 in [3] where it is stated for right-closing CA. See Fig. 3(a) for an illustration.

Lemma 15

(Proposition 5.44 in [3]). Let f be a left-closing CA. For all sufficiently large $m\in \mathbb {N}$, if $s\in S^m$ and $t\in S^{2m}$ are such that $f([s]_{(m,2m]})\cap [t]_{(0,2m]} \ne \emptyset$ then for all $b\in S$ there exists a unique $a\in S$ such that $f([as]_{[m,2m]})\cap [bt]_{[0,2m]} \ne \emptyset$.

The condition $f([s]_{(m,2m]})\cap [t]_{(0,2m]} \ne \emptyset$ is just a way to write that there exists $x\in S^\mathbb {Z}$ with $x_{(m,2m]}=s$ and $f(x)_{(0,2m]}=t$. Note that the statement of the lemma has two parts: the existence of a and the uniqueness of a. We need both parts in the following.

A number m is a strong¹ left-closing radius for a CA f if it satisfies the claim of Lemma 15, and furthermore $m\ge 2r$ where $r\ge 1$ is a neighborhood radius of f. Next we state corollaries of the previous lemma, phrased for right stairs in place of s and t to be directly applicable in our setup.

Corollary 16

Let f be a left-closing CA. Let m be a strong left-closing radius.

• (a) $\varPsi _{3m}(y,z)=\varPsi _{3m}$ for all y and z.

• (b) Let $(vc,wd)\in \varPsi _{3m}$ for $c,d\in S$ and $v,w\in S^{2m-1}$. For every $b\in S$ there exists a unique $a\in S$ such that $(av,bw)\in \varPsi _{3m}$. (See Fig. 3(b) for an illustration.)

• (c) Every $(v,w)\in \varPsi _{3m}(y,z)$ is confirmed by a unique x.

Proof

(a) Let $y,y'\in S^{[3m,\infty )}$ and $z,z'\in S^{(-\infty ,0)}$ be arbitrary. It is enough to prove that $\varPsi _{3m}(y',z')\subseteq \varPsi _{3m}(y,z)$. The claim then follows from this and shift invariance $\varPsi _{3m}(y,z)=\varPsi _{3m}(\sigma (y),\sigma (z))$.

First we show that $\varPsi _{3m}(y',z')\subseteq \varPsi _{3m}(y,z')$. Let $(v,w)\in \varPsi _{3m}(y',z')$ be arbitrary, so that there exists $x'\in [vy']_{[m,\infty )}$ such that $f(x')_{(-\infty ,2m)} = z'w$. Then $(v,w)\in \varPsi _{3m}(y,z')$ is confirmed by the configuration $x''$ such that $x''_{(-\infty ,3m)}=x'_{(-\infty ,3m)}$ and $x''_{[3m,\infty )}=y$. Indeed, $x''_{[m,\infty )}=vy$, and because $m\ge r$, the radius of the local rule of f, we also have $f(x'')_{(-\infty ,2m)}=f(x')_{(-\infty ,2m)} = z'w$.

Next we show that $\varPsi _{3m}(y,z')\subseteq \varPsi _{3m}(y,z)$. Let $(v,w)\in \varPsi _{3m}(y,z')$. We start with finite extensions of w on the left: we prove that for every finite word $u\in S^*$ we have $f([vy]_{[m,\infty )})\cap [uw]_{[-|u|,2m)}\ne \emptyset$. Suppose the contrary, and let $bu\in S^{k+1}$ be the shortest counter example, with $b\in S$ and $u\in S^{k}$. (By the assumptions, the empty word is not a counter example.) By the minimality of bu, there exists $x^r\in [vy]_{[m,\infty )}$ such that $f(x^r)_{[-k,2m)}=uw$. Choose $s=x^r_{[-k+m,-k+2m)}$ and $t=f(x^r)_{[-k,-k+2m)}$ and apply the existence part of Lemma 15. By the lemma, there exists a configuration $x^l$ such that $x^l_{[-k+m,-k+2m)}=x^r_{[-k+m,-k+2m)}$ and $f(x^l)_{[-k-1,-k+2m)}=b\cdot f(x^r)_{[-k,-k+2m)}$.

Consider x obtained by gluing together the left half of $x^l$ and the right half of $x^r$: define $x_{(-\infty ,-k+2m)}=x^l_{(-\infty ,-k+2m)}$ and $x_{[-k+m,\infty )}=x^r_{[-k+m,\infty )}$. Note that in the region $[-k+m,-k+2m)$ configurations $x^l$ and $x^r$ have the same value. By applying the local rule of f with radius r we also get that $f(x)_{(-k-1,-k+2m-r)}=f(x^l)_{(-k-1,-k+2m-r)}=b\cdot f(x^r)_{[-k,-k+2m-r)}$ and $f(x)_{[-k+m+r,2m)} =f(x^r)_{[-k+m+r,2m)}$. Because $m\ge 2r$ we have $-k+2m-r\ge -k+m+r$, so that $f(x)_{(-k-1,2m)}=b\cdot f(x^r)_{(-k,2m)}=buw$. We also have $x_{[m,\infty )}=x^r_{[m,\infty )}=vy$, so that x proves that bu is not a counter example.

Consider then the infinite extension of w on the left by z: Applying the finite case above to each finite suffix of z and by taking a limit, we see with a simple compactness argument that there exists $x\in [vy]_{[m,\infty )}$ such that $f(x)_{[-\infty ,2m)}=zw$. This proves that $(v,w)\in \varPsi _{3m}(y,z)$.

(b) Let $(vc,wd)\in \varPsi _{3m}$ and let $b\in S$ be arbitrary. Let $y\in S^{[3m,\infty )}$ be arbitrary, and and let $z\in S^{(-\infty ,0)}$ be such that $z_{-1}=b$. By (a) we have that $(vc,wd)\in \varPsi _{3m}(y,z)$. Let x be a configuration that confirms this, so $x_{[m,\infty )}=vcy$ and $f(x)_{(-\infty ,2m)}=zwd$. Let $a=x_{m-1}$. Because $x_{[m-1,3m-1)}=av$ and $f(x)_{[-1,2m-1)}=bw$, configuration x confirms (at position $i=-1$) that $(av,bw)\in \varPsi _{3m}$.

Let us prove that a is unique. Suppose that also $(a'v,bw)\in \varPsi _{3m}$. We apply the uniqueness part of Lemma 15 on s and t where $t=wd$ and s is the prefix of v of length m. Because $(a'v,bw)$ is a right stair, $f([a'v]_{[m-1,3m-1)})\cap [bw]_{[-1,2m-1)}\ne \emptyset$. Because $m-1\ge 2r-1\ge r$, the local rule of f assigns $f(x)_{2m-1}=d$ for all $x\in [a'v]_{[m-1,3m-1)}$, so that $f([a'v]_{[m-1,3m-1)})\cap [bwd]_{[-1,2m)}\ne \emptyset$. But then $f([a's]_{[m-1,2m)})\cap [bt]_{[-1,2m)}\ne \emptyset$, so that by Lemma 15 we must have $a'=a$.

(c) Suppose $x\ne x'$ both confirm that $(v',w')\in \varPsi _{3m}(y,z)$. Then $x_{[m,\infty )}=v'y=x'_{[m,\infty )}$. Let $k<m$ be the largest index such that $x_{k}\ne x'_{k}$. Extract $a,a',b,c,d\in S$ and $v,w\in S^{2m-1}$ from x and $x'$ as follows: $avc=x_{[k,k+2m]}$ and $a'vc=x'_{[k,k+2m]}$ and $bwd=f(x)_{[k-m,k+m]}=f(x')_{[k-m,k+m]}$. Then $(vc,wd)\in \varPsi _{3m}$ and $(av,bw), (a'v,bw)\in \varPsi _{3m}$. This contradicts (b).    $\square$

Now we can state another constraint on sliders.

Lemma 17

Let f be a slider. Let m be a strong left-closing radius, and big enough so that f is defined by a bijective block rule $\chi :S^{n}\longrightarrow S^{n}$ of block length $n=3m$. Let N be the number of representatives of configurations (independent of the configuration) with respect to $\chi$. Then

$$ N\cdot |\varPsi _n|=|S|^n. $$

In particular, $|\varPsi _n|$ divides $|S|^n$.

Proof

Fix any $y\in S^{[3m,\infty )}$ and $z\in S^{(-\infty ,0)}$. Denote $A=\{x\in S^\mathbb {Z}\ |\ x_{[3m,\infty )}=y \text{ and } f(x)_{(-\infty ,0)}=z\}$. Consider the function $A\longrightarrow \varPsi _{3m}(y,z)$ defined by $x\mapsto (x_{[m,3m)}, f(x)_{[0,2m)})$. It is surjective by the definition of $\varPsi _{3m}(y,z)$, and it is injective by Corollary 16(c). Because $\varPsi _{3m}(y,z)=\varPsi _{3m}$ by Corollary 16(a), we see that $|A|=|\varPsi _{3m}|$.

For each $w\in S^{3m}$ define configuration $x^w= zwy$. Representations (x, 0) of $y\in A$ are precisely $(x^w,0)$ for $w\in S^{3m}$. Because each y has N representations and there are $|S|^{3m}$ words w we obtain that $N\cdot |\varPsi _{3m}|=|S|^{3m}$.    $\square$

Now we state the converse: the constraints we have for sliders are sufficient. This completes the characterization of sliders.

Lemma 18

Let f be a left-closing cellular automaton, let m be a strong left-closing radius, and assume that $|\varPsi _n|$ divides $|S|^n$ for $n=3\,\mathrm{m}$. Then f is a slider.

Proof

Let $N=|S|^n/|\varPsi _n|$ and pick an arbitrary bijection $\pi :\varPsi _n\times \{1,2,\dots ,N\}\longrightarrow S^n$. Let $f_\mathrm {loc}: S^{2m+1}\longrightarrow S$ be the local rule of radius m for the cellular automaton f.

Let us define a block rule $\chi :S^{n+1}\longrightarrow S^{n+1}$ as follows (see Fig. 3). Consider any $c\in S$, any $k\in \{1,2,\dots ,N\}$ and any $(av,bw)\in \varPsi _n$ where $a,b\in S$ and $v,w\in S^{2m-1}$. Let $d = f_\mathrm {loc}(avc)$. We set $\chi : \pi ((av,bw),k)\cdot c \mapsto b\cdot \pi ((vc,wd),k))$. This completely defines $\chi$, but to see that it is well defined we next show that (vc, wd) is a right stair. By Corollary 16(a) we have that $(av,bw)\in \varPsi _n(cy,z)$ for arbitrary y, z so there is a configuration x such that $x_{[m,\infty )}=avcy$ and $f(x)_{(\infty ,2m)}=zbw$. The local rule $f_\mathrm {loc}$ determines that $f(x)_{2m}=f_\mathrm {loc}(avc)=d$. It follows that $(vc,wd)\in \varPsi _n(y,zb)$, confirmed by x at position $i=1$.

Now that we know that $\chi$ is well defined, let us prove that $\chi$ is a bijection. Suppose $\pi ((av,bw),k)\cdot c$ and $\pi ((a'v',b'w'),k')\cdot c'$ have the same image $b\cdot \pi ((vc,wd),k))=b'\cdot \pi ((v'c',w'd'),k'))$. We clearly have $b=b'$, and because $\pi$ is a bijection, we have $v=v'$, $c=c'$, $w=w'$, $d=d'$ and $k=k'$. By Corollary 16(a) we also have that $a=a'$.

As $\chi$ is a bijective block rule, it defines a slider relation F. We need to prove that for every configuration y, the only z such that $(y,z)\in F$ is $z=f(y)$. Therefore, consider an arbitrary representation (x, i) of $(y,z)\in F$. Write $x=z_{(-\infty ,i)}\cdot \pi ((av,bw),k)\cdot c \cdot y_{[i+n+1,\infty )}$ for letters $a,c,b\in S$ words $v,w\in S^{2m-1}$ and $k\in \{1,2,\dots ,N\}$. This can be done and as $\pi$ is surjective and all items in this representation are unique as $\pi$ is injective. We have $(av,bw)\in \varPsi _n(cy,z)$ so by Corollary 16(c) there is a unique configuration $x'$ that confirms this. Then $x'_{[i+m,\infty )} = avc\cdot y_{[i+n+1,\infty )}$ and $f(x')_{(-\infty , i+2m)} = z_{(-\infty ,i)}\cdot bw$. Associate $x'$ to (x, i) by defining $g(x,i)=x'$.

Let us show that $g(\chi ^i(x),i+1)=g(x,i)$. By the definition of $\chi$ we have

$$ \chi ^i(x)=z_{(-\infty ,i)}\cdot b\cdot \pi ((vc,wd),k))\cdot y_{[i+n+1,\infty )} $$

where $d=f_\mathrm {loc}(avc)$. To prove that $g(\chi ^i(x),i+1)=x'=g(x,i)$ it is enough to show that $x'$ confirms $(vc,wd)\in \varPsi _n(y,zb)$. But this is the case because $x'_{[i+m+1,\infty )} = vc\cdot y_{[i+n+1,\infty )}$ and $f(x')_{(-\infty , i+2m+1)} = z_{(-\infty ,i)}\cdot bwd$. The fact that $f(x')_{i+2m}=d$ follows from $x'_{[i+m,i+3m]}=avc$ and $d=f_\mathrm {loc}(avc)$.

By induction we have that for any $j\ge i$ holds $g(\chi ^{[i,j)}(x),j)=x'$. Moreover, pair $(\chi ^{[i,j)}(x),j)$ represents the same $(y,z)\in F$ as (x, i). Therefore, $x'_{[j+n+1,\infty )}=y_{[j+n+1,\infty )}$ and $f(x')_{(-\infty , j)} = z_{(-\infty ,j)}$ for all $j\ge i$. Let us look into position $p=i+n+m+1$. Using any $j>p$ we get $f(x')_p=z_p$ and using $j=i$ we get $x'_{[p-m,p+m]}=y_{[p-m,p+m]}$. This means that $z_p=f_\mathrm {loc}(y_{[p-m,p+m]})$, that is, $z_p=f(y)_p$. Because i was arbitrary, p is arbitrary. We have that $z=f(y)$, which completes the proof.    $\square$

By Corollary 16, for a left-closing cellular automaton f the limit

$$\begin{aligned} \lambda _f = \lim _{m\rightarrow \infty } \frac{|\varPsi _{3m}|}{|S|^{3m}} \end{aligned}$$

(2)

is reached in finite time, namely as soon as m is a left-closing radius, and thus $\lambda _f$ is rational for left-closing f. In [2] it is shown that the map $f \mapsto \lambda _f$ gives a homomorphism from the group of reversible cellular automata into the rational numbers under multiplication. For a prime number p and an integer n, write $v_p(n)$ for the largest exponent k such that $p^k | n$. For prime p and rational $r = m/n$, write $v_p(r) = v_p(m) - v_p(n)$ for the p-adic valuation of r.

Theorem 19

The function f is a slider if and only if f is a left-closing cellular automaton and $v_p(\lambda _f) \le 0$ for all primes p.

Example 20

Let $A = \{0,1\} \times \{0,1,2\}$ and write $\sigma _2$ and $\sigma _3$ for the left shifts on the two tracks of $A^\mathbb {Z}$. Then consider $f = \sigma _2 \times \sigma _3^{-1}$. For this CA we have by a direct computation $|\varPsi _3| = 2^2 \cdot 3^4$ so $\lambda _f = 2^2 \cdot 3^4 / 6^3$ so $v_3(\lambda _f) = 1 > 0$, and thus f is not a slider. Similarly we see that $\sigma _3 \times \sigma _2^{-1}$ is not a slider.

Example 21

Let $S=\{0,1\}$ and consider the exclusive-or CA with neighborhood $\{-1,0\}$, i.e. $f(x) = x + \sigma ^{-1}(x)$. Then f is left-closing but a direct computation shows $v_2(\lambda _f) = 1 > 0$, so f is not a slider. Compare with Example 4.

2.3 Definition of Sweepers

An alternative approach not requiring bijectivity of $\chi$ is specified in the following:

Definition 22

A block rule $\chi$ defines a sweeper relation $F \subset S^\mathbb {Z}\times S^\mathbb {Z}$ by $(y, z) \in F$ iff some subsequence of $\chi ^{0+}(y), \chi ^{-1+}(y), \chi ^{-2+}(y),\dots$ converges to z.

Lemma 23

The projection $(y,z)\mapsto y$ on the first component maps a sweeper relation F surjectively onto $S^\mathbb {Z}$. The relation F is a function f if and only if for each configuration y the limit $\lim _{i\rightarrow -\infty } {\chi }^{i+}(y)$ exists and equals f(y).

Definition 24

Let $\chi$ be a block rule such that for each configuration y the limit $z= \lim _{i\rightarrow -\infty } {\chi }^{i+}(y)$ exists. The function $y\mapsto z$ is called the sweeper defined by $\chi$.

Compared to Definition 10 the advantage of Definition 24 is that it does not require $\chi$ to be bijective. But as long as $\chi$ is bijective, there is in fact no difference.

Theorem 25

Let $\chi$ be a bijective block rule and f a one-dimensional CA. The slider relation defined by $\chi$ is equal to f if and only if the sweeper relation it defines is equal to f.

While the slider and sweeper relations defined by a block rule are equal when at least one of them defines a cellular automaton, sweeper relations can also define non-continuous functions.

Example 26

Let $S= \{\left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] ,\left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] ,\left[ {\begin{matrix} 1 \\ 0 \end{matrix}} \right] ,\left[ {\begin{matrix} 1 \\ 1 \end{matrix}} \right] \}$ and define $\chi : S^2 \rightarrow S^2$ by $\chi (\left[ {\begin{matrix} 1 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] ) = \left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right]$, $\chi (\left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] ) = \left[ {\begin{matrix} 1 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right]$, and $\chi (ab) = ab$ for $ab \notin \{\left[ {\begin{matrix} 1 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] , \left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] \}$.

We claim that $\lim _{i \rightarrow -\infty } \chi ^{i+}(x)$ is well-defined for all $x \in S^\mathbb {Z}$, so that the sweeper relation $\chi$ defines is a function. Let $x \in S^\mathbb {Z}$ be arbitrary, and let $n \in \mathbb {Z}$. We need to show that $\chi ^{i+}(x)_n$ converges.

Suppose first that for some $k < n$, we have $x_k = \left[ {\begin{matrix} 1 \\ a \end{matrix}} \right]$ for $a \in \{0,1\}$. Then for all $i < k$, the value $\chi ^{i+}(x)_n$ is independent of the values $x_j \le k$, since $\chi ^{[i,k-1]}(x)_k = \left[ {\begin{matrix} 1 \\ a \end{matrix}} \right]$, meaning that the sweep is synchronized (in the sense that whatever information was coming from the left is forgotten and the sweep continues the same way) and $\chi ^{i+}(x)_n$ is determined by $x_{[k,n]}$ for all $i < k$. Thus, in this case $\chi ^{i+}(x)_n$ converges.

Suppose then that for all $k < n$, $x_k = \left[ {\begin{matrix} 0 \\ a \end{matrix}} \right]$ for some $a \in \{0,1\}$. If $x_k = \left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right]$ for some $k < n$, then since $x_{k-1} \ne \left[ {\begin{matrix} 1 \\ 0 \end{matrix}} \right]$ we also have $\chi ^{[i,k-2]}(x)_{k-1} \ne \left[ {\begin{matrix} 1 \\ 0 \end{matrix}} \right]$. Thus, the value at k does not change when $\chi$ is applied at $k-1$, and as in the previous paragraph, the sweep is synchronized at this position. Again $\chi ^{i+}(x)_n$ is determined by $x_{[k,n]}$ for all $i < k$, so $\chi ^{i+}(x)_n$ converges.

In the remaining case, $x_k = \left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right]$ for all $k < n$. Then since $\chi (\left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] ) = \left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right]$, the rule is not applied in the left tail of x, and thus certainly $\chi ^{i+}(x)_n$ converges.

The function defined by the sweeper relation is not continuous at $\left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] ^\mathbb {Z}$ since $\chi ^\mathbb {Z}(\left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] ^\mathbb {Z}) = \left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] ^\mathbb {Z}$ while for any $n \in \mathbb {N}$ we have

$$ \chi ^\mathbb {Z}(...\left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] ^n . \left[ {\begin{matrix} 0 \\ 1 \end{matrix}} \right] ^\mathbb {N}) = ...\left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 0 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 1 \\ 0 \end{matrix}} \right] \left[ {\begin{matrix} 1 \\ 0 \end{matrix}} \right] ^n . \left[ {\begin{matrix} 1 \\ 0 \end{matrix}} \right] ^\mathbb {N}$$

3 Realization of Bi-closing CA Using LR and RL Sliders

In the definition of a slider we use a left-to-right slide of the window to realize the CA transition. Of course, one can analogously define right-to-left sliders and state a characterization via right-closing CA. We can also alternate these two types of rules, and obtain a ladder-shaped hierarchy analogous to the Borel, arithmetic and polynomial hierarchies.

Definition 27

Let $\mathcal {R}$ denote the set of CA definable as slider relations with the “left to right” definition as in Definition 10. Analogously let $\mathcal {L}$ denote the set of CA definable as right-to-left slider relations. Denote $\varDelta = \mathcal {L}\cap \mathcal {R}$. Let now $\mathcal {L}_0 = \mathcal {R}_0 = \{\mathrm {id}\}$, and for all $k \in \mathbb {N}_0$ let $\mathcal {L}_{k+1} = \mathcal {L}\circ \mathcal {R}_{k}$ and $\mathcal {R}_{k+1} = \mathcal {R}\circ \mathcal {L}_{k}$. For all n, write $\varDelta _n = \mathcal {L}_n \cap \mathcal {R}_n$.

Note that in $\mathcal {L}_n$, there are n sweeps (slider applications) in total, and the last sweep goes from right to left. We have $\mathcal {L}_1 = \mathcal {L}$, $\mathcal {R}_1 = \mathcal {R}$, $\varDelta _1 = \varDelta$. See Fig. 4.

Fig. 4.

The sliding hierarchy.

In Theorem 30 below we will show a close relation between this “slider hierarchy” and a “closingness hierarchy” defined as follows, exactly analogously. Let $\mathcal {L}^{cl}$ denote the set of left-closing CA and $\mathcal {R}^{cl}$ the set of right-closing CA. Define $\mathcal {L}^{cl}_0 = \mathcal {R}^{cl}_0 = \{\mathrm {id}\}$ and for all k, $\mathcal {L}^{cl}_{k+1} = \mathcal {L}^{cl}\circ \mathcal {R}^{cl}_k$ and $\mathcal {R}^{cl}_{k+1} = \mathcal {R}^{cl}\circ \mathcal {L}^{cl}_k$.

As always with such hierarchies, it is natural to ask whether they are infinite or collapse at some finite level. We do not know if either hierarchy collapses, but we show that after the first level, the hierarchies coincide. The main ingredients for the theorem are the following two lemmata.

Lemma 28

Let f be a left-closing CA. For all n large enough, $|\varPsi _{n}|$ divides some power of $|S|$.

Lemma 29

Let f be a left-closing CA. Then for any large enough n, we have $\sigma ^n \circ f \in \mathcal {R}$.

Theorem 30

For each $k\in \mathbb {N}$ with $k\ge 2$ we have $\mathcal {L}_k = \mathcal {R}^{cl}_k$ and $\mathcal {R}_k = \mathcal {L}^{cl}_k$.

A cellular automaton f is bi-closing if it is both left-closing and right-closing, i.e. $f \in \varDelta ^{cl}_1$. Such cellular automata are also called open, since they map open sets to open sets. By the previous result, every bi-closing CA can be realized by a left-to-right sweep followed by a right-to-left sweep by bijective block rules:

Theorem 31

Each bi-closing CA is in $\varDelta _2$.

4 Decidability

In this section, we show that our characterization of sliders and sweepers shows that the existence of them for a given CA is decidable. We also show that given a block rule, whether it defines some CA as a slider (equivalently as a sweeper) is decidable. We have seen that sweepers can also define shift-commuting functions which are not continuous. We show that this condition is also decidable.

Lemma 32

Given a cellular automaton $f : S^\mathbb {Z}\rightarrow S^\mathbb {Z}$, it is decidable whether it is left-closing, and when f is left-closing, a strong left-closing radius can be effectively computed.

Lemma 33

Given a left-closing cellular automaton $f : S^\mathbb {Z}\rightarrow S^\mathbb {Z}$, one can effectively compute the rational number $\lambda _f$ defined in Eq. (2) on page 12.

Theorem 34

Given a cellular automaton $f : S^\mathbb {Z}\rightarrow S^\mathbb {Z}$, it is decidable whether f is a slider (resp. sweeper).

We now move on to showing that given a block rule, we can check whether its slider or sweeper relation defines a CA.

In the rest of this section, we explain the automata-theoretic nature of both types of rules, which allows one to decide many properties of the slider and sweeper relations even when they do not define cellular automata. As is a common convention in automata theory, all claims in the rest of this section have constructive proofs (and thus imply decidability results), unless otherwise specified.

We recall definitions from [4] for automata on bi-infinite words. A finite-state automaton is $A = (Q, S, E, I, F)$ where Q is a finite set of states, $S$ the alphabet, $E \subset Q \times S\times Q$ the transition relation, $I \subset Q$ the set of initial states and $F \subset Q$ the set of final states.

The pair (Q, E) can be naturally seen as a labeled graph with labels in $S$. The language of such an automaton A the set $\mathcal {L}(A) \subset S^\mathbb {Z}$ of labels of bi-infinite paths in (Q, E) such that some state in I is visited infinitely many times to the left (negative indices) and some state in F infinitely many times to the right. Languages of finite-state automata are called recognizable.

In the theorems of this section, note that the set $S^\mathbb {Z}\times S^\mathbb {Z}$ is in a natural bijection with $(S^2)^\mathbb {Z}$.

Proposition 35

Let $\chi : S^m \rightarrow S^m$ be a bijective block rule. Then the corresponding slider relation $F \subset (S^2)^\mathbb {Z}$ is recognizable.

Lemma 36

Given a recognizable set $X \subset (S^2)^\mathbb {Z}$, interpreted as a binary relation over $S^\mathbb {Z}$, it is decidable whether X defines a function.

The following is a direct corollary.

Theorem 37

Given a block rule, it is decidable whether it is the sliding rule of a CA.

We now discuss sweeping rules.

Proposition 38

Let $\chi : S^m \rightarrow S^m$ be a block rule. Then the corresponding sweeper relation $F \subset (S^2)^\mathbb {Z}$ is recognizable.

The sweeping relation need not be closed, as shown in Example 26. However, whether it is closed is decidable.

Lemma 39

Given a recognizable $X \subset S^\mathbb {Z}$, it is decidable whether X is closed.

Theorem 40

Given a block rule, it is decidable whether the sweeping relation it defines is a CA.

5 Future Work and Open Problems

To obtain a practical computer implementation method for cellular automata, one would need much more work. The radius of $\chi$ should be given precise bounds, and we would also need bounds on how long it takes until the sweep starts producing correct values. Future work will involve clarifying the connection between the radii m of local rules $\chi : S^m \rightarrow S^m$ and the strong left-closing radii, the study of non-bijective local rules, and the study of sweeping rules on periodic configurations.

On the side of theory, it was shown in Sect. 3 that the hierarchy of left- and right-closing cellular automata corresponds to the hierarchy of sweeps starting from the second level. Neither hierarchy collapses on the first level, since there exists CA which are left-closing but not right-closing, from which one also obtains CA which are in $\mathcal {L}_1$ but not $\mathcal {R}_1$.

Question 41

Does the hierarchy collapse on a finite level? Is every surjective CA in this hierarchy?

As we do not know which cellular automata appear on which levels, we do not know whether these levels are decidable. For example we do not know whether it is decidable if a given CA is the composition of a left sweep and a right sweep.

It seems likely that the theory of sliders can be extended to shifts of finite type. If X is a subshift, say that a homeomorphism $\chi : X \rightarrow X$ is local if its application modifies only a (uniformly) bounded set of coordinates. One can define sliding applications of such homeomorphisms exactly as in the case of $S^\mathbb {Z}$.

Question 42

Let $X \subset S^\mathbb {Z}$ be a transitive subshift of finite type. Which endomorphisms of X are defined by a sliding rule defined by a local homeomorphism?

In [2], block representations are obtained for cellular automata in one and two dimensions, by considering the set of stairs of reversible cellular automata. Since stairs play a fundamental role for sliders as well, it seems natural to attempt to generalize our theory to higher dimensions.