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 sweep of a bijective rule from left to right over an infinite tape. Such cellular automata are necessarily left-closing, and they move at least as much information to the left as they move information to the right.
Notes
Research supported by the Academy of Finland Grants 296018 and 2608073211.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Cellular automata are models of parallel computation, so when implementing cellular automata 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, and to apply the cellular automaton we sweep a permutation \(\chi : S^n \rightarrow S^n\) from left to right over x (applying it consecutively to all length-n 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’.
Advertisement
It turns out that the cellular automata that admit a sliding rule are precisely the ones that are left-closing (Definition 5), and whose number of right stairs (see Definition 6) of length 3m divides \(|S|^{3m}\) for large enough m. This can be interpreted as saying that the the average movement ‘with respect to any prime number’ is not to the right. See Theorems 2 and 3 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 level. 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\).
Advertisement
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\) 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
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 to half-infinite configurations and denote for any \(D\subseteq \mathbb {Z}\) and any \(y\in S^D\)
A block rule is a function \(\chi : S^n \rightarrow S^n\). 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 functions 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 fist define what it means to apply a block rule on a configuration.
Definition 1
Let \(\chi : S^n \rightarrow S^n\) 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+n)} = \chi (x_{[i,i+n)})\) 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
In general 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 (in the topological space \(S^{\mathbb {Z}}\)) which we write as \({\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.
Example 1
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
$$\begin{aligned} 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. } \end{aligned}$$
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 2
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 4 that the exclusive-or CA with neighborhood \(\{-1,0\}\) can not be defined this way.
2.1 Definition of sliders
A slider applies a bijective block rule in order to transition between two configurations, as in popular before/after image sliders. Sliding the block rule from left to right transforms the “before” configuration into the “after” configuration, and sliding the inverse block rule back from right to left reconstructs the “before” configuration from the “after” configuration. This relates pairs of configurations to each other. Figure 1 shows a slider in action that relates configuration y to its left shift \(z=\sigma (y)\).
Definition 3
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 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 1
Let (x, i) be a representation of\((y, z)\in F\)under a bijective block rule\(\chi\)of block lengthn. 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 2
Let\((y,z)\in F\)be fixed. For all\(i\in \mathbb {Z}\)denote
$$\begin{aligned} R_i=\{x\in S^\mathbb {Z}\ |\ (x,i) \text{ is } \text{ a } \text{ representation } \text{ of } (y, z)\}. \end{aligned}$$
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
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 1: there are at most \(|S|^n\) choices of \(x_{[i,i+n)}\) in \(x\in R_i\). \(\square\)
Lemma 3
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\)mapFsurjectively onto\(S^\mathbb {Z}\).
Proof
By Lemma 2 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 1
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 total 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 4
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 1 indicates that the slider for the block rule swapping two states is the left shift. By Corollary 1 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 1 and show that sliders are left-closing cellular automata.
Definition 5
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 right-asymptotic configurations y and \(y'\) holds: If \(y\not =y'\) then \(f(y)\not = f(y')\). Right-closing CA are defined symmetrically using left-asymptotic configurations.
Lemma 4
A slider is a left-closing cellular automaton.
Proof
Let slider f be defined by a bijective block rule \(\chi : S^n \rightarrow S^n\), 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 n\), 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 m be such that \(2^m > |S|^n\) and for each \(k \in \{0,1\}^m\), define the configuration
$$\begin{aligned} y_k = \ldots 0000 w_{k_1} v w_{k_2} v \ldots v w_{k_n} v . 0000\ldots \end{aligned}$$
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,n)} = (x_{k'})_{[0,n)}\). 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)(m-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,n)} = (x_{k'})_{[0,n)}\) by the choice of k and \(k'\), so \((x_k)_{[R-r, n)}\) and \((x_{k'})_{[R-r, n)}\).
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-n+1, n)}\) and similarly \(\xi ^{0-}(x_{k'})_R\) is determined by \((x_{k'})_{[R-n+1, n)}\), but \((x_k)_{[R-n+1, n)} = (x_{k'})_{[R-n+1, n)}\) since \((x_k)_{[R-r, n)} = (x_{k'})_{[R-r, n)}\) and \(r \ge n.\)\(\square\)
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 1 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 2 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 5
\(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 4, 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. There were defined in Kari (1996) 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 3m connecting y and z, confirmed by x at position \(i=0\)
×
Definition 6
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 3m 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 3m 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 6. 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 6, and b an illustration for Corollary 2(b) and for Lemma 8
×
We need the following known fact concerning left-closing CA. It appears as Proposition 5.44 in Kůrka (2012) where it is stated for right-closing CA. See Fig. 3(a) for an illustration.
Lemma 6
(Proposition 5.44 in Kůrka (2012)) Letfbe 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 strongleft-closing radius for a CA f if it satisfies the claim of Lemma 6,1 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 2
Letfbe a left-closing CA. Letmbe a strong left-closing radius.
(a)
\(\varPsi _{3m}(y,z)=\varPsi _{3m}\)for allyandz.
(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.3b for an illustration.)
(c)
Every\((v,w)\in \varPsi _{3m}(y,z)\)is confirmed by a uniquex.
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 counterexample, with \(b\in S\) and \(u\in S^{k}\). (By the assumptions, the empty word is not a counterexample.) 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 6. 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 counterexample.
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 6 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 6 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 prove another constraint on sliders.
Lemma 7
Letfbe a slider. Letmbe a strong left-closing radius, and big enough so thatfis defined by a bijective block rule\(\chi :S^{n}\longrightarrow S^{n}\)of block length\(n=3m\). LetNbe the number of representatives of configurations (independent of the configuration) with respect to\(\chi\). Then
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 2(c). Because \(\varPsi _{3m}(y,z)=\varPsi _{3m}\) by Corollary 2(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 prove the converse: the constraints we have proved for sliders are sufficient. This completes the characterization of sliders.
Lemma 8
Letfbe a left-closing cellular automaton, letmbe a strong left-closing radius, and assume that\(|\varPsi _n|\)divides\(|S|^n\)for\(n=3m\). Thenfis 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 2(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 2(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 2(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
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\)
Theorem 1
The functionfadmits a slider if and only iffis a left-closing cellular automaton and\(|\varPsi _n|\)divides\(|S|^n\)for\(n = 3m\)wheremis the smallest strong left-closing radius.
We can state this theorem in a slightly more canonical (but completely equivalent) form by normalizing the length of stairs:
By Corollary 2, for a left-closing cellular automaton f the limit
is reached in finite time, namely as soon as m is a strong left-closing radius, and thus \(\lambda _f\) is rational for left-closing f. In Kari (1996) 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 2
The functionfadmits a slider if and only iffis a left-closing cellular automaton and\(v_p(\lambda _f) \le 0\)for all primesp.
Example 3
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 does not admit a slider. Similarly we see that \(\sigma _3 \times \sigma _2^{-1}\) does not admit a slider.
Example 4
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 does not admit a slider. Compare with Example 2.
2.3 Definition of sweepers
An alternative approach not requiring bijectivity of \(\chi\) is specified in the following:
Definition 7
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 9
The projection \((y,z)\mapsto y\)on the first component maps a sweeper relationFsurjectively onto\(S^\mathbb {Z}\). The relationFis a functionfif and only if for each configurationythe limit\(\lim _{i\rightarrow -\infty } {\chi }^{i+}(y)\)exists and equalsf(y).
Proof
For every \(y\in S^\mathbb {Z}\) the sequence \(\chi ^{0+}(y), \chi ^{-1+}(y), \chi ^{-2+}(y),\dots\) has a converging subsequence with some limit z. Then \((y,z)\in F\) so the projection is onto.
If \(z=\lim _{i\rightarrow -\infty } {\chi }^{i+}(y)\) exists then every subsequence of \(\chi ^{0+}(y), \chi ^{-1+}(y), \chi ^{-2+}(y),\dots\) converges to z so z is the unique configuration such that \((y,z)\in F\). Conversely, if \(\lim _{i\rightarrow -\infty } {\chi }^{i+}(y)\) does not exist then \(\chi ^{0+}(y), \chi ^{-1+}(y), \chi ^{-2+}(y),\dots\) has two subsequences converging to distinct \(z_1\) and \(z_2\). In this case \((y,z_1)\) and \((y,z_2)\) are both in relation F. \(\square\)
Definition 8
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\).
Before we are going to compare the notions of sliders and sweepers we provide a result on a special kind of Mealy automata.
2.4 A note on finite Mealy automata
In this section we consider Mealy automata with a set Q of states and where the set A of input symbols and the set of output symbols coincide. For convenience instead of pairs of elements we use words of length 2. Thus, we denote by \(\mu :Q A \rightarrow A Q\) the function mapping the current state q and an input symbol a to \(\mu (qa)=a'q'\), where \(q'\) is the new state of the automaton.
The motivation for this is the following. When a block rule \(\chi\) is sweeping over a configuration one can think of the block \(q\in S^n\) where \(\chi\) will be applied next as encoding the state of a Mealy automaton. The word \(a\in S^n\) immediately to the right of it is the next input symbol. By applying \(\chi\) at positions \(0,1,\dots ,n-1\) the word qa is transduced into a word \(a'q'\in S^{2n}\) where \(a'\) can be considered the output symbol and \(q'\) the next state of the automaton. When \(\chi\) is bijective then clearly \(\mu\) is bijective, too.
Let \(\delta :QA\rightarrow Q\) denote the function yielding only the new state of the Mealy automaton. The extension \(\delta ^*:QA^*\rightarrow A^*Q\) to input words is for all states q, all inputs \(w\in A^*\) and \(a\in A\) defined by \(\delta ^*(q\varepsilon )=q\) and \(\delta ^*(qwa)=\delta (\delta ^*(qw)a)\).
Because of the application we have in mind we now restrict ourselves to the case where \(Q=A\) and speak of elements \(e\in Q\). Let \(\bar{e}=(\ldots ,e_{-2},e_{-1},e_0)\) denote a sequence of elements which is infinite to the left.
Definition 9
A finite tail \(\bar{e}_i=(e_{-i},\ldots ,e_0)\) of \(\bar{e}\) is good for q if \(\delta ^*(\bar{e}_i)=q\). An infinite sequence \(\bar{e}\) is good for q if infinitely many finite tails \(\bar{e}_i=(e_{-i},\ldots ,e_0)\) are good for q. A state q is good, if there is an infinite sequence \(\bar{e}\) that is good for q. Let \(G\subseteq Q\) denote the set of good states and \(B\subseteq Q\) the set of bad states.
First, observe that the property of being good is preserved by \(\delta\). If g is good, then each \(\delta (ga)\) is good, too: If \(\bar{e}\) is good for g, then \(\bar{e}a\) is good for \(\delta (ga)\) since \(\delta ^*(e_{-i},\ldots ,e_0)=g\) implies \(\delta ^*(e_{-i},\ldots ,e_0,a)=\delta (ga)\). This means that \(\mu (GA)\subseteq AG\).
Since \(\mu\) is injective and \(|GA|=|AG|\), in fact \(\mu (GA)= AG\). Therefore \(\mu (BA)\subseteq AB\), that is \(\delta\) preserves bad states. Now, assume that there indeed exists a bad state \(b\in B\). Consider \(\bar{b}=(\ldots , b,b,b)\). The states \(b_i=\delta ^*(b^i)\) are all bad, but at least one of them happens infinitely often, which would mean that it is good, which is a contradiction. \(\square\)
2.5 Relation between sliders and sweepers
Compared to Definition 4 the advantage of Definition 8 is that it does not require \(\chi\) to be bijective. But as long as \(\chi\) is bijective, there is in fact no difference.
Theorem 3
Let\(\chi\)be a bijective block rule andfa one-dimensional CA.The rule\(\chi\)is an slider forfif and only if it is a sweeper forf.
The two implications are considered separately in Lemmata 11 and 12 below. For the remainder of this section let \(\chi :S^n \rightarrow S^n\) always denote a bijective block rule and let \(f:S^{\mathbb {Z}}\rightarrow S^{\mathbb {Z}}\) denote a one-dimensional CA (without stating this every time).
Lemma 11
If\(\chi\)is not a sweeper forfthen it is not a slider forf.
Proof
If \(\chi\) is not a sweeper for f then there is a configuration y for which the limit \(\lim _{i\rightarrow -\infty } \chi ^{[i,\infty )}(y)\) does not exist or is wrong.In both cases there is a cell \(j\in \mathbb {Z}\) and a state \(s\in S\) such that \(s\not =f(y)_j\) but \(\chi ^{[i,\infty )}(y)_j=s\) for infinitely many \(i < j-n\).
We will construct a configuration x such that \(\chi ^{j-}(x)=y\) and \(\chi ^{j+}(x)_j=s\not =f(y)_j\). Therefore \(\chi\) is not a slider for f (see Definition 4).
As a first step we subdivide the “left part” \((-\infty ,j+n)\) of \(\mathbb {Z}\) into windows\(W_k\) of length n. For \(k\ge 0\) let \(p_k=-kn+j\) denote the smallest index in \(W_k\), i. e. \(W_k=[p_k,p_{k-1})\) (where \(p_{-1}=j+n\)).Analogously divide the “left part” of y into words \(y^{(k)}\) of length n by setting \(y^{(k)} = y|_{W_k}\) (see Fig. 4).
Fig. 4
For configuration y the windows \(W_k\) contain the words \(y^{(k)}\)
×
Let M denote the set \(\{i \mid \chi ^{[i,\infty )}(y)_j=s\}\). M contains infinitely many integers \(i< p_1=j-n\). Then there has to be a word \(v^{(0)}\in S^n\) such that the set \(M_0 = \{ i\in M \mid i<p_1 \text { and } \chi ^{[i,j)}(y)|_{W_0} = v^{(0)} \}\) is infinite. Since \(M_0\subseteq M\) certainly \(\chi (v^{(0)})_0 = s\) holds.
Fig. 5
Transition from \(v^{(k+1)}y^{(k)}\) to \(x^{(k+1)}v^{(k)}\) by applying \(\chi\) from left to right at the positions indicated by the gray bars. Application of the inverse \(\xi\) from right to left realizes the opposite transition from bottom to top
×
For all \(k\ge 0\) we now inductively define words \(v^{(k+1)}\) and \(x^{(k+1)}\) (all of length n) and along with it infinite sets \(M_{k+1}\). Since \(M_k\) is infinite, there is a word \(v^{(k+1)}\) such that the set
$$\begin{aligned} M_{k+1} = \{ i \in M_k \mid i< p_{k+2} \text { and } \chi ^{[i,p_k)}(y)|_{W_{k+1}} = v^{(k+1)} \} \end{aligned}$$
is infinite. Since \(M_{k+1}\subseteq M_k\) one has \(\chi ^{[p_{k+1},p_k)}(v^{(k+1)}y^{(k)}) = x^{(k+1)} v^{(k)}\) for some \(x^{(k+1)}\) (see Fig.5). Since \(\chi\) is bijective, for the inverse \(\xi\) of \(\chi\) holds \(v^{(k+1)}y^{(k)} = \xi ^{[p_{k+1},p_k)^R}(x^{(k+1)} v^{(k)})\), too. Note again that \(\xi\) is applied from right to left.
On one hand \(\chi ^{j+}(x)\) already after the application of \(\chi\) at position j produces state s there which never changes again. Thus \(\chi ^{j+}(x)\not =f(y)\).
On the other hand by construction for all \(k\ge 0\) holds \(\xi ^{[p_{k+1},p_k)^R}(x^{(k+1)} v^{(k)}) = v^{(k+1)}y^{(k)}\).
Obviously one gets \({\xi }^{i-}(x) =y\). \(\square\)
Lemma 12
If\(\chi\)is not a slider forfthen it is not a sweeper forf.
Proof
If \(\chi\) is not a slider for f then there exists a configuration x and an \(i\in \mathbb {Z}\) such that for \(z={\chi }^{i+}(x)\) and \(y={\chi }^{i-}(x)\) one has \(f(y) \not = z\). Let \(\xi\) be the inverse of \(\chi\). Let j be a cell where \(f(y)_j\not = z_j\). If \(j<i+n\) instead of x can consider \(x'=\xi ^{[i-1,\dots ,i-m]}(x)\) for some sufficiently large m. Assume therefore that \(j\ge i+n\).
We will prove that there is a configuration v such that for infinitely many positions m the configuration \(\chi ^{[m,\infty )}(v)\) will not have the correct state at position j. Therefore the limit \(\lim _{m\rightarrow -\infty }\chi ^{[m,\infty )}(v)\) cannot exist and have the correct state at position j. Thus \(\chi\) is not a sweeper for f.
Below the abbreviation \(Q=S^n\) is used.
Configuration x is of the form \(z_{(-\infty ,i)}\cdot w \cdot y_{[i+n,\infty )}\) for some \(w\in Q\). Applying \(\chi\) at position i and further to the right produces the same result independent of what is to the left of w. Therefore if \(z_{(-\infty ,i)}\) is replaced by any \(z'_{(-\infty ,i)}\) still the wrong state is produced at position j.
Define a Mealy automaton with \(Q=A\) by \(\mu (qa)=\chi ^{[0,n)}(qa)\) (observe that \(qa\in S^{2n}\)). Since \(\mu\) is bijective, one can now use the result from Lemma 10 and conclude that there is a sequence \((\ldots ,v^{(2)},v^{(1)})\), infinite to the left, of elements \(v^{(k)}\in Q\) such that
$$\begin{aligned} \delta ^*(v^{(k)}\cdots v^{(1)})=w \text { for infinitely many } k. \end{aligned}$$
(3)
Let v be the infinite to the left half-configuration obtained by concatenating all \(v^{(k)}\), more precisely \(v:(-\infty ,i+n)\rightarrow S\) where \(v_{-kn+j+i} = v^{(k)}_j\) for all \(k\ge 1\) and all \(j\in [0,n)\).
Condition (3) implies that for infinitely many \(k\ge 1\) applying \(\chi\) in v from position \(-kn+i\) up to but excluding i produces w at the end, i. e. in the window \([i,i+n)\). In other words \(\chi ^{[-kn+i,i)}(v) = v'_{(-\infty ,i)} \cdot w\) (\(v'\) depends on k but doesn’t matter).
Since we could assume that the position j where \(f(y)_j\not = z_j\) is in the interval \([i+n,\infty )\) one can conclude that \(\chi\) is not a sweeper for f. \(\square\)
While the sliding and sweeping rule defined by a block rule are equal when both define a cellular automaton, sweeping rules can also define non-continuous functions.
We claim that \(\lim _{i \rightarrow -\infty } \chi ^{i+}(x)\) is well-defined for all \(x \in S^\mathbb {Z}\), so that the sweeping 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]\) either. 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 sweeping rule 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
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 prove 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 10
Let \(\mathcal {R}\) denote the set of CA for which there is a slider “from left to right” as in Definition 4.
Analogously let \(\mathcal {L}\) denote the set of CA for which there is a right-to-left slider. 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 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. 6.
Fig. 6
The slider hierarchy
×
In Theorem 4 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 13
Letfbe a left-closing CA. For allnlarge enough, \(|\varPsi _{n}|\)divides some power of\(|S|\).
Proof
Let m be a strong left-closing radius for f. Number m can be chosen as large as needed. Let \(f_\mathrm {loc}\) be the local update rule of f of radius 3m. By Theorem 14.7 in Hedlund (1969) there exist, for \(k=3m\) chosen sufficiently large,
positive integers L, M and R such that \(L\cdot M\cdot R = |S|^{2k}\),
pairwise different words \(u_1,\dots ,u_M\) of length k,
sets \({{\mathcal {L}}}_1,\dots , {{\mathcal {L}}}_M\subseteq S^{2k}\) of words of length 2k, each of cardinality \(|{{\mathcal {L}}}_i|=L\),
sets \({{\mathcal {R}}}_1,\dots , {{\mathcal {R}}}_M\subseteq S^{2k}\) of words of length 2k, each of cardinality \(|{{\mathcal {R}}}_i|=R\),
a word w of length 3k whose set pre-images of length 5k under \(f_\mathrm {loc}\) is precisely
Illustration of Theorem 14.7 in Hedlund (1969), with \(L=4\), \(R=3\)
×
Let \(y\in S^{[k,\infty )}\) be arbitrary and let \(z\in S^{(-\infty ,0)}\) be such that \(z_{[-3k,0)}=w\). Define \(A=\{x\in S^\mathbb {Z}\ |\ x_{[k,\infty )}=y, f(x)_{(-\infty ,0)}=z\}\). By Corollary 2 we know that \(|\varPsi _{3m}|=|A|\).
(i) If \(x\in A\) then \(x_{[-4k,k)}\) is a pre-image of \(w=z_{[-3k,0)}\). This means that for some \(i\in \{1,\dots , M\}\), we have \(x_{[-4k,k)}\in {{\mathcal {L}}}_iu_i{{\mathcal {R}}}_i\) and, in particular, \(x_{[-2k,k)}\in u_i{{\mathcal {R}}}_i\).
(ii) Conversely, let \(i\in \{1,\dots , M\}\) and \(v\in {{\mathcal {R}}}_i\) be arbitrary. Words in \({{\mathcal {L}}}_iu_iv\) are pre-images of w so \(f([u_iv]_{[-2k,k)})\cap [w]_{[-3k,0)} \ne \emptyset\). Because f is left-closing and k is a strong left-closing radius for f there exists a unique \(x\in A\) such that \(x_{[-2k,k)}=u_iv\).
From (i) and (ii) we can conclude that \(|A|=M\cdot R\). Hence \(L\cdot |\varPsi _{3m}|=L\cdot |A|=L\cdot M\cdot R = |S|^{2k}\). \(\square\)
Lemma 14
Letfbe a left-closing CA. Then for any large enoughn, we have\(\sigma ^n \circ f \in \mathcal {R}\).
Proof
By the previous lemma, we have \(v_p(\lambda _f) = 0\) for all \(p \not \mid |S|\). Similarly as in Kari (1996) one sees that the map \(g \mapsto \lambda _g\) is a homomorphism among left-closing CA, so
By Lemma 4 we have \(f \in \mathcal {L}\implies f \in \mathcal {R}^{cl}\) and \(f \in \mathcal {R}\implies f \in \mathcal {L}^{cl}\), so by induction \(\mathcal {L}_k \subset \mathcal {R}^{cl}_k\) and \(\mathcal {R}_k \subset \mathcal {L}^{cl}_k\).
Suppose then that \(f \in \mathcal {R}^{cl}_k\) and \(k \ge 2\), so
where \(\sum _{i = 1}^k n_i = 0\) and for each odd i, \(n_i \le 0\) is small enough that \(f_i \circ \sigma ^{n_i} \in \mathcal {L}\) and for each even i, \(n_i \ge 0\) is large enough that \(f_i \circ \sigma ^{n_i} \in \mathcal {R}\). This shows that \(f \in \mathcal {L}_k\). Similarly \(\mathcal {L}^{cl}_k \subset \mathcal {R}_k\), concluding the proof. \(\square\)
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 5
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 15
Given a cellular automaton\(f : S^\mathbb {Z}\rightarrow S^\mathbb {Z}\), it is decidable whether it is left-closing, and whenfis left-closing, a strong left-closing radius can be effectively computed.
Proof
It is obviously decidable whether a given \(m \in \mathbb {N}\) is a strong left-closing radius, since checking this requires only quantification over finite sets of words. This shows that left-closing is semi-decidable and the m can be computed when f is left-closing. When f is not left-closing, there exist x, y such that \(x_{[1,\infty )} = y_{[1,\infty )}\), \(x_0 \ne y_0\) and \(f(x) = f(y)\). A standard pigeonhole argument shows that there then also exist such a pair of points whose left and right tails are eventually periodic, showing that not being left-closing is semidecidable. \(\square\)
Lemma 16
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 (2).
Proof
As observed after defining (2), the limit is reached in finite time, once m is a strong left-closing radius. By the previous lemma, one can effectively compute a strong left-closing radius. \(\square\)
Theorem 6
Given a cellular automaton\(f : S^\mathbb {Z}\rightarrow S^\mathbb {Z}\), it is decidable whetherfadmits a slider (resp. sweeper).
Proof
By Theorem 3, a block rule is a sweeping rule for f if and only if it is a slider rule for f, so in particular f admits a slider if and only if it admits a sweeper. Theorem 2 characterizes cellular automata admitting a slider as ones that are left-closing and satisfy \(v_p(\lambda _f) \le 0\) for all primes p. Decidability follows from the previous two lemmas. \(\square\)
We now move on to showing that given a block rule, we can check whether its slider or sweeper rule 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 Perrin and Pin (2004) 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.
If \(A \subset S^{-\mathbb {N}}\) and \(B \subset S^{\mathbb {N}}\), write \([A, B] \subset S^\mathbb {Z}\) for the set of configurations \(x \in S^\mathbb {Z}\) such that for some \(y \in A, z \in B\), \(x_i = A_{i+1}\) for \(i < 0\) and \(x_i = B_i\) for \(i \ge 0\). We need the following lemma.
Lemma 17
(Part of Proposition IX.2.3 in Perrin and Pin (2004)) For a set\(X \subset S^\mathbb {Z}\)the following are equivalent
Xis recognizable
Xis shift-invariant and a finite union of sets of the form [A, B] whereBis\(\omega\)-recognizable (accepted by a Büchi automaton) andAis the reverse of an\(\omega\)-recognizable set.
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 1
Let\(\chi : S^m \rightarrow S^m\)be a bijective block rule. Then the correspondingslider relation\(F \subset (S^2)^\mathbb {Z}\)is recognizable.
Proof
Let \(\xi = \chi ^{-1}\). The slider relation is defined as the pairs \(y, z \in S^\mathbb {Z}\) such that for some representation (x, 0) we have \(\chi ^{0-}(x) = y\) and \(\xi ^{0+}(x) = z\).
For each \(uw \in S^{[-m,m-1]}\) where \(|u| = |w| = m\), we define recognizable languages \(A_{uw} \subset (S^2)^{(-\infty ,0)}, B_{uw} \in (S^2)^{[0, \infty )}\) such that the slider relation is \(\bigcup _{uw \in S^{[-m,m-1]}} [A_{uw}, B_{uw}]\).
For finite words, one-way infinite words and more generally patterns over any domain \(D \subset \mathbb {Z}\), define the ordered applications of \(\chi\) and \(\xi\) (e.g. \(\chi ^{i+}\)) with the same formulas as for \(x \in S^\mathbb {Z}\), when they make sense.
For each word \(uw \in S^{[-m,m-1]}\), define the \(\omega\)-recognizable set \(B_{uw} \subset (S^2)^\mathbb {N}\) containing those (y, z) for which \(\chi ^{0+}(x) = z\) where \(x \in S^\mathbb {N}\) satisfies \(x_{[0,m-1]} = w\), \(x_{[m,\infty )} = y_{[m,\infty )}\), and \(\xi ^{[-m+1,-1]^R}(uw)|_{[0,m-1]} = y_{[0,m-1]}\). One can easily construct a Büchi automaton recognizing this language, so \(B_w\) is \(\omega\)-recognizable.
Let then for \(w \in S^m\) the set \(A_w \subset (S^2)^{-\mathbb {N}}\) be defined as those pairs (y, z) such that \(\xi ^{0-}(zw)|_{(-\infty , 0)} = y\), where \(zw \in S^{(-\infty , m-1]}\). Again it is easy to construct a Büchi automaton for the reverse of \(A_w\).
Now it is straightforward to verify that the slider relation of \(\chi\) is
which is recognizable by Lemma 17 since the slider relation is always shift-invariant. \(\square\)
Lemma 18
Given a recognizable set\(X \subset (S^2)^\mathbb {Z}\), interpreted as a binary relation over\(S^\mathbb {Z}\), it is decidable whetherXdefines a function.
Proof
Since recognizable sets representing relations are closed under Cartesian products, projections and intersections (by standard constructions), if X is recognizable also the ‘fiber product’ \(Y \subset (S^2)^\mathbb {Z}\) containing those pairs \((z,z')\) satisfying \(\exists y: (y,z) \in X \wedge (y,z') \in X\) is recognizable. The diagonal \(\varDelta\) of \((S^2)^\mathbb {Z}\) containing all pairs of the form (z, z) is also clearly recognizable.
Since recognizable languages are closed under complementation (Perrin and Pin 2004), we obtain that \(((S^2)^\mathbb {Z}\setminus \varDelta ) \cap Y\) is recognizable. This set is empty if and only if X is a function, proving decidability, since all proofs in this section are constructive and emptiness of a recognizable language is decidable using standard graph algorithms. \(\square\)
The following is a direct corollary.
Theorem 7
Given a block rule, it is decidable whether it is the sliding rule of a CA
We now discuss sweeping rules.
Proposition 2
Let\(\chi : S^m \rightarrow S^m\)be a bijective block rule. Then the correspondingsweeper relation\(F \subset (S^2)^\mathbb {Z}\)is recognizable.
Proof
One can easily construct a finite-state automaton accepting the language \(X \subset (\{0,1\}^2 \times S^2)^\mathbb {Z}\) containing those \((x, x', y, z) \in (\{0,1\}^2 \times S^2)^\mathbb {Z}\) where
and \(x_i = 1 \iff i = m\) and \(x'_i = 1 \iff i = n\). Simply construct an automaton that checks that there is exactly one 1-symbol on each of the first two tracks, and when it sees the first 1 is seen on the first track it starts keeping in its state the current contents of the active window (where the block rule is being applied). When 1 is seen on the second track, it also starts checking that the image is correct.
Since X is described by an automaton and \(|S| \le 2^k\) for some k, an adaptation of (Perrin and Pin 2004, Theorem IX.7.1) shows that there exists a monadic second-order formula over the successor function of \(\mathbb {Z}\), i.e. some formula \(\varphi \in \text{ MF }_2(<)\), that defines those tuples sets of integers \((x, x', y_1, \ldots , y_k, z_1, \ldots , z_k)\) where \((y_1,\ldots ,y_k)\) codes some y and \((z_1,\ldots ,z_k)\) some z such that \((x, x', y, z)\) is in X.
Since in tuple \((x, x', y_1, \ldots , y_k, z_1, \ldots , z_k)\) that satisfies \(\varphi\) we have \(|x| = |x|' = 1\), it is standard to modify \(\varphi '\) into a formula where \(x, x'\) are replaced by first-order variables i, j and correspond to the unique places in x and \(x'\) where the unique 1 appears. Now the formula \(\psi\) defined by
defines those tuples \((y_1, \ldots , y_k, z_1, \ldots , z_k)\) that code pairs (y, z) which are in the sweeper relation for \(\chi\). Another application of (Perrin and Pin 2004, Theorem IX.7.1) then shows that sweeper relation is recognizable. \(\square\)
The sweeping relation need not be closed, as shown in Example 5. However, whether it is closed is decidable.
Lemma 19
Given a recognizable\(X \subset S^\mathbb {Z}\), it is decidable whetherXis closed.
Proof
Take an automaton recognizing X, remove all states from which an initial state is not reachable to the left, and those from which a final state is not reachable to the right. Turn all states into initial and final states. Now X is closed if and only if the new automaton recognizes X, which is decidable by standard arguments. \(\square\)
Theorem 8
Given a block rule, it is decidable whether it is the sweeping rule of a CA.
Proof
The sweeping rule of a block rule defines a CA if and only if the sweeping relation is closed and defines a function. These are decidable by Lemmas 18 and 19, respectively. \(\square\)
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 1
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 2
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 Kari (1996), 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.
Acknowledgements
Open access funding provided by University of Turku (UTU) including Turku University Central Hospital. The authors gratefully acknowledge partial support for this work by two short term scientific missions of the EU COST Action IC1405.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
