We show that a cellular automaton on a one-dimensional two-sided mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from previous joint work of the author and Törmä that von Neumann regularity is a decidable condition, and we decide it for all elementary CA, obtaining the optimal radii for weak generalized inverses. Two sufficient conditions for non-regularity are having a proper sofic image or having a point in the image with no preimage of the same period. We show that the non-regular ECA 9 and 28 cannot be proven non-regular using these methods. We also show that a random cellular automaton is non-regular with high probability.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
The von Neumann regular elements – elements a having a weak inverse b such that \(aba = a\) – of cellular automaton (CA) semigroups are studied in Castillo-Ramirez and Gadouleau (2020). We show that in the context of cellular automata on one-dimensional two-sided mixing subshifts of finite type, von Neumann regularity coincides with the notion of split epicness onto the image, another generalized invertibility notion from category theory.
Question 1 of Castillo-Ramirez and Gadouleau (2020) asks which of the so-called elementary cellular automata (ECA) are von Neumann regular. They determine this for all ECA except ones equivalent to those with numbers 6, 7, 9, 23, 27, 28, 33, 41, 57, 58 and 77, see the next section for the definition of the numbering scheme.
Advertisement
What makes this question interesting is that von Neumann regularity of one-dimensional cellular automata is not obviously1 decidable – clearly checking if a given CA f has a weak inverse is semidecidable, but it is not immediately clear how to semidecide the nonexistence of a weak inverse. However, split epicness has been studied previously in Salo and Törmä (2015), and in particular it was shown there that split epicness of a morphism between two sofic shifts is a decidable condition. This means Question 1 of Castillo-Ramirez and Gadouleau (2020) can in theory be decided algorithmically.
As the actual bound stated in Salo and Törmä (2015) is beyond astronomical, it is an interesting question whether the method succeeds in actually deciding each case. Using this method we give a human proof that 9, 27, 28, 41 and 58 are not von Neumann regular, and we prove by computer that ECA 6, 7, 23, 33, 57 and 77 are von Neumann regular, answering the remaining cases of Question 1 of Castillo-Ramirez and Gadouleau (2020).
The von Neumann regular CA on this list have weak inverses of radius at most four. Non-regularity is proved in each case by looking at eventually periodic points of eventual period one and applying the method of Salo and Törmä (2015), namely the strong periodic point condition. For ECA 27, 41 and 58, non-regularity can also be proved by simply observing that their images are proper sofic. For ECA 9 and ECA 28, this method cannot be used, as the image is an SFT. The ECA 9, 27, 28, 58 admit preimages of the same period for all periodic points, so the method used in Castillo-Ramirez and Gadouleau (2020) cannot be used to prove their non-regularity. In particular 9 and 28 seem to require using the strong periodic point condition.
This is an extended version of the paper (Salo 2021). The new results about ECA are the precise optimal radii for the weak inverses (one of those reported in Salo (2021) was suboptimal, and we had only checked the optimality in one case), and the observation that 9 and 28 admit preimages of the same period for periodic points. We also prove that a random CA is not von Neumann regular with high probability (Theorem 35), which refutes an almost-conjecture stated in Salo (2021).
Advertisement
2 Preliminaries
The full shift is \(\Sigma ^{\mathbb {Z}}\) where \(\Sigma \) is a finite alphabet, carrying the product topology. It is homeomorphic to the Cantor set, thus compact and metrizable. It is a dynamical system under the shift\(\sigma (x)_i = x_{i+1}\). Its subsystems (closed shift-invariant subsets) are called subshifts, and the bi-infinite words \(x \in \Sigma ^{\mathbb {Z}}\) are their points.
A cellular automaton (CA) is a shift-commuting continuous function \(f: X \rightarrow X\) on a subshift X. The cellular automata on a subshift X form a monoid \(\textrm{End}(X)\) under function composition. A CA f is reversible if \(\exists g: f \circ g = g \circ f = \textrm{id}\) where g is a cellular automaton. Reversibility is equivalent to bijectivity by a compactness argument.
A CA has a local rule, that is, there exists a radius\(r \in {\mathbb {N}}\) such that \(f(x)_i\) is determined by \(x {\mid }_{[i-r,i+r]}\) for all \(x \in X\) (and does not depend on i). More generally, a neighborhood is a finite subset \(N \subset {\mathbb {Z}}\) such that \(f(x)_i\) is determined by \(x {\mid }_{i+N}\). The elementary cellular automata (ECA) are the CA on the binary full shift \(\{0,1\}^{\mathbb {Z}}\) which can be defined with radius 1. There is a numbering scheme for such CA: If \(n \in [0,255]\) has base 2 representation \(b_7b_6...b_1b_0\), then ECA number n is the one mapping \(f(x)_i = b_{(x_{[i-1,i+1]})_2}\) where \((x_{[i-1,i+1]})_2\) is the number represented by \(x_{[i-1,i+1]}\) in base 2. This numbering scheme is from Wolfram (1983). The usage of base 10 for n in this notation is standard, and some CA researchers remember ECA by these numbers. From radius 2 onward, we switch to hexadecimal notation.
We recall (Castillo-Ramirez and Gadouleau 2020, Definition 3): define maps \(R, S: \{0,1\}^{\mathbb {Z}}\rightarrow \{0,1\}^{\mathbb {Z}}\) by the formulas \(R(x)_i = x_{-i}\) (this reverses the configuration) and \(S(x)_i = 1-x_i\) (this flips all the bits in the configuration). Two cellular automata \(f, g \in \textrm{End}(\{0,1\}^{\mathbb {Z}})\) are equivalent if \(f \in \langle S \rangle \circ g \circ \langle S \rangle \cup \langle S \rangle \circ R \circ g \circ R \circ \langle S \rangle \), where \(\circ \) denotes function composition and \(\langle S \rangle = \{\text{id}, S\}\). This means that we may pre- or postcompose by the bit flip S, and we may conjugate the CA by the reversal R. Composing by R from just one side almost never gives a cellular automaton, so this is not allowed.
A subshift can be defined by forbidding a set of finite words from appearing as subwords of its points (which themselves are infinite words), and this is in fact a characterization of subshifts. A subshift is of finite type or SFT if it can be defined by a finite set of forbidden words, and sofic if it can be defined by forbidding a regular language, in the sense of automata and formal languages. A proper sofic subshift is one that is sofic but not SFT.
The language\({\mathcal {L}}(X)\) of a subshift X is the set of finite words that appear in its points. A subshift X is mixing if for all words u, v appearing in the language of X, for all large enough n some word uwv with \({\mid }w {\mid }= n\) appears in the language of X. In the case of a sofic shift X with language L, we can simplify this to \(\exists m: \forall u,v \in L: \exists w \in L: {\mid }w {\mid }= m \wedge uwv \in L\).
The language of a subshift determines it uniquely, and thus a convenient way to define a subshift is to describe its language. For a language L which is extendable meaning \(\forall v \in L: \exists u, w \in L: uvw \in L\), there exists a unique smallest subshift whose language contains L. We write this subshift as \({\mathcal {L}}^{-1}(L)\). For L regular, this gives a sofic shift. We note that this is not an inverse for \({\mathcal {L}}\), but rather \({\mathcal {L}}({\mathcal {L}}^{-1}(L))\) is the factor closure of L, i.e. \(v \in {\mathcal {L}}({\mathcal {L}}^{-1}(L)) \iff \exists u, w: uvw \in L\).
If \(u \in A^*\) is a finite nonempty word, we write \(u^{\mathbb {Z}}\) for the \({\mid }u{\mid }\)-periodic point (i.e. fixed point of \(\sigma ^{{\mid }u{\mid }}\)) in \(A^{\mathbb {Z}}\) whose subword at \([0, {\mid }u{\mid }-1]\) is equal to u. We say two points are left-asymptotic if their values agree at \(-n\) for large enough n, and symmetrically define right-asymptoticity. Points are asymptotic if they are left- and right-asymptotic. The notation \({^\omega }uwv {^\omega }\) denotes a point left-asymptotic to (a shift-image of) \(u^{\mathbb {Z}}\) and right-asymptotic to (a shift-image of) \(v^{\mathbb {Z}}\), with the word w between. When the positioning is important, we include a decimal point.
The de Bruijn graph (with parameter n) is the graph with nodes for words of length \(n-1\). When considering a cellular automaton with neighborhood consisting of n consecutive positions, we typically label the transition from au to ub (\(|u| = n-2\)) by the image of aub under the local rule. This is a convenient way to write the local rule of an ECA (in the case \(n = 3\)). Images of configurations can be found by following the corresponding path in the de Bruijn path (looking at consecutive pairs of symbols) and reading the edge labels.
In some parts of the paper, we assume knowledge of automata theory and formal languages. In automata theoretic terms, the de Bruijn graph can be directly seen as a non-deterministic finite-state automaton for the language of a CA with neighborhood \([0, n-1]\) (note that shifting the neighborhood does not affect the image): simply consider every node as both initial and final. This is called the de Bruijn automaton.
See standard references for more information on symbolic dynamics (Lind and Marcus 1995) or automata theory and formal languages (Hopcroft et al. 2006).
A semigroup is a set with an associative product, denoted by juxtaposition. A category is specified by a class of objects, for each pair of objects A, B a class of morphisms \(f: A \rightarrow B\), a composition \(gf = g \circ f: A \rightarrow C\) for morphisms \(f: A \rightarrow B, g: B \rightarrow C\), and identity morphisms \(\textrm{id}: A \rightarrow A\) for each object. The composition should be associative, and the identity morphism should act trivially in composition. See MacLane (1971) for more information on categories (very little is needed here).
3 Split epicness and von Neumann regularity
In this section, we show split epicness and von Neumann regularity are equivalent concepts on mixing SFTs. On full shifts, this is simply a matter of defining these terms.
If S is a semigroup, then \(a \in S\) is (von Neumann) regular if \(\exists b \in S: a b a = a \wedge b a b = b\). We say b is a generalized inverse of a. If \(aba = a\) (but not necessarily \(bab = b\)), then b is a weak inverse of a. (More properly, one might call this a weak generalized inverse, but we use the shorter term as it is unambiguous.)
Lemma 1
If a has a weak inverse, then it has a generalized inverse and thus is regular.
Proof
If \(aba = a\), then letting \(c = bab\), we have \(aca = ababa = aba = a\) and \(cac = bababab = babab = bab = c\). \(\square \)
If \({\mathcal {C}}\) is a category, a morphism \(f: X \rightarrow Y\) is split epic if there is a morphism \(g: Y \rightarrow X\) such that \(f \circ g = \textrm{id}_Y\). Such a g is called a right inverse or a section.
Note that, in general, category-theoretic concepts depend on the particular category at hand, but if \({\mathcal {C}}\) is a full subcategory of \({\mathcal {D}}\) (meaning a subcategory induced by a subclass of the objects, by taking all the morphisms between them), then split epicness for a morphism \(f: X \rightarrow Y\) where X, Y are objects of \({\mathcal {C}}\) means the same in both.
We are in particular interested in the categories K2, K3, K4 (in the naming scheme of Salo and Törmä (2015)) with respectively SFTs, sofic shifts, or all subshifts as objects, and block maps, i.e. shift-commuting continuous functions \(f: X \rightarrow Y\) as morphisms. Note that K2 is a full subcategory of K3, which in turn is a full subcategory of K4. By the previous paragraph, the choice does not really matter.
The following theorem is essentially only a matter of translating terminology, and works in many concrete categories.
Theorem 2
Let X be a subshift, and \(f: X \rightarrow X\) a CA. Then the following are equivalent:
\(f: X \rightarrow f(X)\) has a right inverse \(g: f(X) \rightarrow X\) which can be extended to a morphism \(h: X \rightarrow X\) such that \(h{\mid }_{f(X)} = g\),
f is regular as an element of \(\textrm{End}(X)\).
Proof
Suppose first that f is regular, and \(h \in \textrm{End}(X)\) satisfies \(fhf = f\) and \(hfh = h\). Then the restriction \(g = h{\mid }_{f(X)}: f(X) \rightarrow X\) is still shift-commuting and continuous, and \(\forall x: fg(f(x)) = f(x)\) implies that for all \(y \in f(X)\), \(fg(y) = y\), i.e. g is a right inverse for the codomain restriction \(f: X \rightarrow f(X)\) and it extends to the map \(h: X \rightarrow X\) by definition.
Suppose then that \(fg = \textrm{id}_{f(X)}\) for some \(g: f(X) \rightarrow X\), as a right inverse of the codomain restriction \(f: X \rightarrow f(X)\). Let \(h: X \rightarrow X\) be such that \(h{\mid }_{f(X)} = g\), which exists by assumption. Then \(fh(f(x)) = fg(f(x)) = f(x)\). Thus f is regular, and hfh is a generalized inverse for it by the proof of the previous lemma. \(\square \)
Note that when X is a full shift, extending morphisms is trivial: if \(g: Y \rightarrow X\) has been defined by a local rule of radius r, defined on the words of length \(2r+1\) in Y, we can simply fill in the local rule arbitrarily to obtain a cellular automaton \(h: X \rightarrow X\) with \(h{\mid }_Y = g\). This does not work for general Y, X, as the image of h might not be contained in X, but it turns out that partially defined CA on mixing SFTs can be extended in an analogous way.
For two subshifts X, Y write \(X \overset{\textrm{per}}{\rightarrow } Y\) if the period of every periodic point of X is divisible by the period of some periodic point of Y. The following is Boyle’s extension lemma (Boyle 1983).
Lemma 3
Let \({\tilde{S}} \subset S\) be subshifts, let T be a mixing SFT. Suppose \({\tilde{\phi }}: {\tilde{S}} \rightarrow T\) is shift-commuting and continuous, and \(S \overset{\textrm{per}}{\rightarrow } T\). Then there exists a shift-commuting continuous map \(\phi : S \rightarrow Y\) such that \(\phi {\mid }_{{{\tilde{S}}}} = {\tilde{\phi }}\).
Lemma 4
Let X be a mixing SFT, \(Y \subset X\) a subshift, and \(g: Y \rightarrow X\) any shift-commuting continuous map. Then \(g = h{\mid }_Y\) for some cellular automaton \(h: X \rightarrow X\).
Proof
In the previous lemma, let \(S = T = X, {{\tilde{S}}} = Y\), \({\tilde{\phi }} = g\). The condition \(S \overset{\textrm{per}}{\rightarrow } T\), i.e. \(X \overset{\textrm{per}}{\rightarrow } X\), is trivial. \(\square \)
Theorem 5
Let X be a mixing SFT, and \(f: X \rightarrow X\) a CA. Then the following are equivalent for \(n = 2,3,4\):
\(f: X \rightarrow f(X)\) is split epic in Kn.
f is regular as an element of \(\textrm{End}(X)\).
Proof
By Theorem 2, we need to check that “\(f: X \rightarrow f(X)\) has a right inverse \(g: f(X) \rightarrow X\) which can be extended to a morphism \(h: X \rightarrow X\) such that \(h{\mid }_{f(X)} = g\)” is equivalent to split epicness. The forward implication is trivial, and the backward implication follows from the previous lemma, since every \(g: f(X) \rightarrow X\) extends to such h. \(\square \)
Theorem 5 clearly implies that regularity respects equivalence of CA (this is not difficult to obtain directly from the definition either).
Corollary 6
If \(f, g \in \textrm{End}(\{0,1\}^{\mathbb {Z}})\) are equivalent, then f is regular if and only if g is regular.
4 Deciding split epicness
We recall the characterization of split epicness (Salo and Törmä 2015, Theorem 1). This is Theorem 7 below.
Definition 1
Let X, Y be subshifts and let \(f: X \rightarrow Y\) be a morphism. Define
$$\begin{aligned} {\mathcal {P}}_p(Y) = \{ u \in {\mathcal {L}}(Y) \;{\mid }\; u^{\mathbb {Z}}\in Y, {\mid }u{\mid }\le p \}. \end{aligned}$$
We say f satisfies the strong p-periodic point condition if there exists a length-preserving function \(G: {\mathcal {P}}_p(Y) \rightarrow {\mathcal {L}}(X)\) such that for all \(u, v \in {\mathcal {P}}_p(Y)\) and \(w \in {\mathcal {L}}(Y)\) with \({^\omega }u.w v {^\omega }\in Y\), there exists an f-preimage for \({^\omega }u.w v {^\omega }\) of the form \({^\omega }G(u) w'. w'' w''' G(v) {^\omega }\in X\) where \({\mid }u{\mid }\) divides \({\mid }w'{\mid }\), \({\mid }v{\mid }\) divides \({\mid }w'''{\mid }\) and \({\mid }w{\mid }= {\mid }w''{\mid }\). The strong periodic point condition is that the strong p-periodic point condition holds for all \(p \in {\mathbb {N}}\).
The condition states that we can pick, for each eventually periodic point, a preimage whose tails have the same eventual periods as the image, and that we can make these choices consistently (determined by a function G).
The strong periodic point condition is an obvious necessary condition for having a right inverse, as the right inverse must consistently pick preimages for periodic points, and since it is a CA, eventually it only sees the periodic pattern when determining the preimage, and begins writing a periodic preimage. Let us show the XOR CA with neighborhood \(\{0,1\}\) is not regular using this method – this is clear from the fact it is surjective and noninjective, or from the fact there are 1-periodic points with no preimage of period 1, but it also neatly illustrates the strong periodic point method.
Example 1
The CA \(f: \{0,1\}^{\mathbb {Z}}\rightarrow \{0,1\}^{\mathbb {Z}}\) defined by
is not regular. To see this, consider the strong p-periodic point condition for \(p = 1\). Since \(f(0^{\mathbb {Z}}) = f(1^{\mathbb {Z}}) = 0^{\mathbb {Z}}\), the point \(0^{\mathbb {Z}}\) has two preimages, and we must have either \(G(0) = 0\) or \(G(0) = 1\). It is enough to show that neither choice of \(a = G(0)\) is consistent, i.e. there is a point y which is in the image of f such that y has no preimage that is left and right asymptotic to \(a^{\mathbb {Z}}\). This is shown by considering the point
$$\begin{aligned} y ={\ldots}0000001000000{\ldots} \end{aligned}$$
(which is in the image of f since f is surjective). It has two preimages, and the one left-asymptotic to \(a^{\mathbb {Z}}\) is right-asymptotic to \((1-a)^{\mathbb {Z}}\). \(\bigcirc \)
In (Salo and Törmä 2015, Theorem 1), it is shown that the strong periodic point condition actually characterizes split epicness, in the case when X is an SFT and Y is a sofic shift.
Theorem 7
Given two sofic shifts \(X \subset S^{\mathbb {Z}}\) and \(Y \subset R^{\mathbb {Z}}\) and a morphism \(f: X \rightarrow Y\), it is decidable whether f is split epic. If X is an SFT, split epicness is equivalent to the strong periodic point condition.
We note that Definition 1 is equivalent to a variant of it where G is only defined on Lyndon words (Lothaire 2002), i.e. lexicographically minimal representative words of periodic orbits: if G is defined on those, it can be extended to all of \({\mathcal {P}}_p\) in an obvious way, and the condition being satisfied by minimal representatives implies it for all eventually periodic points.
Remark 1
It is observed in (Castillo-Ramirez and Gadouleau 2020, Theorem 1) that if \(f: X \rightarrow Y\) is split epic, then every periodic point in Y must have a preimage of the same period in X – this is a special case of the above, and could thus be called the weak periodic point condition. In (Salo and Törmä 2015, Example 5), an example is given of morphism between mixing SFTs which satisfies the weak periodic point condition but not the strong one. We will see later that ECA 9 and ECA 28 are non-regular, but satisfy the weak periodic point condition. In (Castillo-Ramirez and Gadouleau 2020, Theorem 4), for full shifts on finite groups, the weak periodic point condition is shown to be equivalent to split epicness (when CA are considered to be morphisms onto their image). In the context of CA on \({\mathbb {Z}}^2\), there is no useful strong periodic point condition in the sense that split epicness is undecidable, see Corollary 12.
In the proof of Theorem 7 in Salo and Törmä (2015), decidability is obtained from giving a bound on the radius of a minimal inverse, and a very large one is given, as we were only interested in the theoretical decidability result. The method is, however, quite reasonable in practise:
To semidecide non-(split epicness), look at periodic points one by one, and try out different possible choices for their preimages. Check by automata-theoretic methods (or “by inspection”) which of these are consistent in the sense of Definition 1.
To semidecide split epicness, invent a right inverse – note that here we can use the other semialgorithm (running in parallel) as a tool, as it tells us more and more information about how the right inverse must behave on periodic points, which tells us more and more values of the local rule.
One of these is guaranteed to finish eventually by Salo and Törmä (2015). For the regular elementary cellular automata, a simpler method sufficed, we essentially used only the weak periodic point condition combined with brute force search, see Sect. 7.
We finish this section with two more conditions for regularity. Proposition 9 below is a slight generalization of (Salo and Törmä 2015, Proposition 1). We give a proof here, as the proof in Salo and Törmä (2015) unnecessarily applies a more difficult result of S. Taati (and thus needs the additional assumption of “mixing”).
Lemma 8
If X is an SFT and \(f: X \rightarrow X\) is idempotent, i.e. \(f^2 = f\), then f(X) is an SFT.
Proof
Clearly \(x \in f(X) \iff f(x) = x\), which is an SFT condition. Namely, if the radius of f is r, the forbidden patterns are the words of length \(2r+1\) where the local rule changes the value of the current cell. \(\square \)
Proposition 9
If X is an SFT and \(f: X \rightarrow X\) is regular, then f(X) is of finite type.
Proof
Let \(g: X \rightarrow X\) be a weak inverse. Then \(g \circ f: X \rightarrow X\) is idempotent, so g(f(X)) is an SFT. Note that the domain-codomain restriction \(g{\mid }_{f(X), g(f(X))}: f(X) \rightarrow g(f(X))\) is a conjugacy, meaning shift-commuting homeomorphism, between f(X) and g(f(X)): its two-sided inverse is \(f{\mid }_{g(f(X)), f(X)}: g(f(X)) \rightarrow f(X)\) by a direct computation. Thus f(X) is also an SFT, since being an SFT is preserved under conjugacy (Lind and Marcus 1995, Theorem 2.1.10). \(\square \)
We also mention another condition, Proposition 11 below, although it is not applicable to the ECA we consider.
Lemma 10
Let X be a subshift with dense periodic points and \(f: X \rightarrow X\) a CA. If f is injective, it is surjective.
Proof
The set \(X_p = \{x \in X \;{\mid }\; \sigma ^p(x) = x\}\) satisfies \(f(X_p) \subset X_p\). Since f is injective and \(X_p\) is finite, we must have \(f(X_p) = X_p\). Thus f(X) is a closed set containing the periodic points. If periodic points are dense, \(f(X) = X\). \(\square \)
We are interested mainly in mixing SFTs, where periodic points are easily seen to be dense. We remark in passing that in the case of mixing SFTs, the previous lemma can also be proved with an entropy argument: An injective CA cannot have a diamond2 when seen as a block map, so (Lind and Marcus 1995, Theorem 8.1.16) shows that the entropy of the image f(X) of an injective CA is equal to the entropy of X. By (Lind and Marcus 1995, Corollary 4.4.9), a mixing SFT X is entropy minimal, that is, it has no proper subshifts of the same entropy, and it follows that \(f(X) = X\).
Proposition 11
Let X be a mixing SFT and \(f: X \rightarrow X\) a surjective CA. Then f is injective if and only if it is regular.
Proof
Suppose f is a surjective CA on a mixing SFT. If it is also injective, it is bijective, thus reversible (by compactness of X), thus regular. Conversely, let f be surjective and regular, and let \(g: X \rightarrow X\) be a weak inverse. Then g is injective, so it is surjective by the previous lemma. Thus f must be bijective as well. \(\square \)
More generally, the previous proposition works on surjunctive subshifts in the sense of (Ceccherini-Silberstein and Coornaert 2010, Exercise 3.29), i.e. subshifts (on groups) where injective cellular automata are surjective. In particular this is the case for full shifts on surjunctive groups (Gottschalk 1973; Weiss 2000) such as abelian ones. Since injectivity is undecidable for surjective CA on \({\mathbb {Z}}^d\), \(d \ge 2\) by Kari (1994), we obtain the following corollary.
Corollary 12
Regularity is undecidable for two-dimensional cellular automata. In fact, given a surjective CA \(f: \Sigma ^{{\mathbb {Z}}^2} \rightarrow \Sigma ^{{\mathbb {Z}}^2}\), it is undecidable whether f is split epic.
5 Von Neumann non-regularity of elementary CA
In Castillo-Ramirez and Gadouleau (2020), regularity was resolved for all ECA where the weak periodic point condition failed for period at most three, or there was a weak inverse directly among the ECA. The remaining cases up to equivalence are 6, 7, 9, 23, 27, 28, 33, 41, 57, 58, 77. In this section, we prove the non-regular cases.
Theorem 13
The elementary CA with numbers 9, 27, 28, 41 and 58 are not regular.
Proof
See the lemmas below. \(\square \)
For the reader’s convenience, we include the de Bruijn graphs in Fig. 1.
Fig. 1
De Bruijn graphs of the non-regular ECA
×
Lemma 14
The elementary CA 9 is not regular.
Proof
Let f be the ECA 9, i.e. \(f(x)_i = 1 \iff x_{[i-1,i+1]} \in \{000, 011\}\). Let X be the image of f.
We have \(f(0^{\mathbb {Z}}) = 1^{\mathbb {Z}}\) and \(f(1^{\mathbb {Z}}) = 0^{\mathbb {Z}}\), so if \(g: X \rightarrow \{0,1\}^{\mathbb {Z}}\) is a right inverse for f, then \(g(0^{\mathbb {Z}}) = 1^{\mathbb {Z}}\). Consider now the configuration
$$ x ={\ldots}000011.00000{\ldots} $$
where coordinate 0 is to the left of the decimal point (i.e. at the rightmost 1 of the word 11).
We have \(x \in X\) because \(f({\ldots}10101000.010101{\ldots}) = x\). (Alternatively, by Proposition 27, X is precisely the SFT defined by forbidden words 1011, 10101, 11001, 11000011 and 110000101.)
Let \(g(x) = y\). Then \(y_i = 1\) for all large enough i and \(y_i = 0\) for some i. Let n be maximal such that \(y_n = 0\). Then \(y_{[n,n+2]} = 011\) so \(f(y)_{n+1} = 1\) and \(f(y)_{n+1+i} = 0\) for all \(i \ge 1\). Since \(f(y) = x\), we must have \(n = -1\) and since \(\{000, 011\}\) does not contain a word of the form a01, it follows that \(f(y)_{-1} = 0 \ne x_{-1}\), a contradiction. \(\square \)
The proof above shows that the ECA 9 does not have the strong periodic point property for \(p = 1\). In general, for fixed p one can use automata theory to decide whether it holds up to that p, though here (and in all other proofs) we found the contradictions by hand before we had to worry about implementing this.
Next, we cover ECA 27. The image X of f can be shown to be proper sofic, so Proposition 9 directly shows that the CA can not be regular. Nevertheless, we give a direct proof to illustrate the method.
Lemma 15
The ECA 27 is not regular.
Proof
Let f be the ECA 27, i.e. \(f(x)_i = 1 \iff x_{[i-1,i+1]} \in \{000, 001, 011, 100\}\). Let X be the image of f.
Again, we will see that this CA does not satisfy the strong periodic point condition for \(p = 1\). Observe that \(f(1^{\mathbb {Z}}) = 0^{\mathbb {Z}}\) and \(f(0^{\mathbb {Z}}) = 1^{\mathbb {Z}}\) so if g is a right inverse from the image to \(\{0,1\}^{\mathbb {Z}}\), then \(g(0^{\mathbb {Z}}) = 1^{\mathbb {Z}}\) and \(g(1^{\mathbb {Z}}) = 0^{\mathbb {Z}}\).
We have
$$ f({\ldots}0001100.10101{\ldots}) = {\ldots}1111011.00000{\ldots} = x \in X. $$
We now reason similarly as in Lemma 14. We have \(g(x)_i = 1\) for all large enough i, and if n is maximal such that \(g(x)_n = 0\), then \(f(g(x))_{n+1} = 1\) and \(f(g(x))_{n+1+i} = 0\) for all \(i \ge 1\), so again necessarily \(n = -1\). A short combinatorial analysis shows that no continuation to the left from n produces \(f(g(x))_{n} = 1\) and \(f(g(x))_{n-1} = 0\), that is, the image of g has no possible continuation up to coordinate \(-3\). \(\square \)
Lemma 16
The ECA 28 is not regular.
Proof
Let f be the ECA 28, i.e. \(f(x)_i = 1 \iff x_{[i-1,i+1]} \in \{010, 011, 100\}\). Let X be the image of f.
We have \(f(0^{\mathbb {Z}}) = f(1^{\mathbb {Z}}) = 0^{\mathbb {Z}}\). We have
$$ f({\ldots}1111.0000{\ldots}) = {\ldots}0000.1000{\ldots} = x \in X. $$
(Alternatively, \(x \in X\) by Proposition 25 which states that X is the SFT with the single forbidden word 111.)
This contradicts the choice \(g(0^{\mathbb {Z}}) = 0^{\mathbb {Z}}\) by a similar analysis as in Example 1: computing the preimage from right to left, the asymptotic type necessarily changes to 1s. Thus we must have \(g(0^{\mathbb {Z}}) = 1^{\mathbb {Z}}\).
On the other hand, if \(g(0^{\mathbb {Z}}) = 1^{\mathbb {Z}}\), then going from right to left, we cannot find a consistent preimage for
(Alternatively, going from left to right, the asymptotic type necessarily changes to 0s or never becomes 1-periodic.)
It follows that \(g(0^{\mathbb {Z}})\) has no consistent possible choice, a contradiction. \(\square \)
Next we consider ECA 41. Again Proposition 9 would yield the result, because the image is proper sofic. For ECA 41, in fact even the weak periodic point condition fails, see Sect. 6.
Lemma 17
The ECA 41 is not regular.
Proof
Let f be the ECA 41, i.e. \(f(x)_i = 1 \iff x_{[i-1,i+1]} \in \{000, 011, 101\}\).
We have \(f(1^{\mathbb {Z}}) = 0^{\mathbb {Z}}\) and \(f(0^{\mathbb {Z}}) = 1^{\mathbb {Z}}\). In the usual way (right to left), we verify that the point
has no preimage that is right asymptotic to \(1^{\mathbb {Z}}\), obtaining a contradiction. \(\square \)
Next we consider ECA 58. Again Proposition 9 would also yield the result, since the image is proper sofic.
Lemma 18
The ECA 58 is not regular.
Proof
Let f be the ECA 58, i.e. \(f(x)_i = 1 \iff x_{[i-1,i+1]} \in \{001, 011, 100, 101\}\).
The point \(0^{\mathbb {Z}}\) has two 1-periodic preimages. We show neither choice satisfies the strong periodic point condition: if \(g(0^{\mathbb {Z}}) = 1^{\mathbb {Z}}\), then g cannot give a preimage for
In this section we look at the weak periodic point condition (WPP) and the condition of having SFT images, for the five non-regular CA that were left open in Castillo-Ramirez and Gadouleau (2020) (where the WPP was checked up to period 3) and for which we showed the strong periodic point condition (SPP) fails in the previous section. The results are summarized in Table 1, “no” means that the particular method can be used to conclude non-regularity (because the necessarily condition does not hold), “yes” means that it can not.
Table 1
Necessary conditions for regularity satisfied by the five non-regular ECA
SFT image
WPP
SPP
ECA 9
Yes
Yes
No
ECA 27
No
Yes
No
ECA 28
Yes
Yes
No
ECA 41
No
No
No
ECA 58
No
Yes
No
6.1 Weak periodic point condition
We show that the ECA 9, 27, 28 and 58 satisfy the weak periodic point condition, i.e. every periodic point in the image has a preimage with the same period, while 41 does not.
Proposition 19
ECA 41 does not satisfy the weak periodic point condition.
Proof
In the local rule of this ECA f, we have \(000, 011, 101 \rightarrow 1\), others map to 0. We have \(f((000101)^{\mathbb {Z}}) = (010)^{\mathbb {Z}}\), \(f((001)^{\mathbb {Z}}) = 0^{\mathbb {Z}}\), \( f((011)^{\mathbb {Z}}) = (110)^{\mathbb {Z}}\), so \((010)^{\mathbb {Z}}\) has a 6-periodic preimage, but no 3-periodic preimage. \(\square \)
Proposition 20
ECA 28 satisfies the weak periodic point condition.
Proof
In this ECA, \(010, 011, 100 \rightarrow 1\), others map to 0. It is easy to check that this ECA amounts to a right shift followed by a bit flip when restricted to the flipped golden mean shift, i.e. the SFT with the unique forbidden word 00. Thus, on the golden mean shift (the SFT with unique forbidden word 11), a section for this CA is left shift composed with bit flip.
Thus, any periodic point in the golden mean shift will have a preimage with the same period. Consider then a p-periodic point x not in the golden mean shift, we may assume \(x = (11u)^{\mathbb {Z}}\) for some u, say \({\mid }u{\mid }= p-2\). Now take any preimage y for x, and observe that necessarily \(y_{[n-1,n+3]} = 0100\) for all \(n \in p{\mathbb {Z}}\), by a quick look at the local rule. In automata theoretic terms, 11 is a synchronizing word for the de Bruijn automaton. This synchronization means that also \((y_{[0,p-1]})^{\mathbb {Z}}\) is a preimage. \(\square \)
Proposition 21
ECA 9 satisfies the weak periodic point condition.
Proof
In this one, \(000, 011 \rightarrow 1\), others map to 0. It is easy to check that on the subshift \({\mathcal {L}}^{-1}((1000^*)^*)\) (on the image side), a section is again given by left shift composed with bit flip. The words 11, 101 are easily seen to force a unique preimage word of length at least 2 (i.e. are synchronizing for the automaton), and we can argue as in the previous proof for all periodic points containing one of these words. \(\square \)
For ECA 27 and 58 we decided the weak periodic point condition by computer.
Proposition 22
The weak periodic point condition is decidable.
Proof
Let f be a CA. The language of words (u, v) of the same length such that \(f(u^{\mathbb {Z}}) = v^{\mathbb {Z}}\) is clearly regular, let L be its right projection. The image of f is sofic, so let K be the language of words v such that \(v^{\mathbb {Z}}\) is in the image subshift of f, which is also clearly regular. If every periodic point admits an f-preimage of the same period, then clearly \(K = L\). If \(u^{\mathbb {Z}}\) does not admit a point of the same period, and \({\mid }u{\mid }\) is minimal for this point, then \(u \in K \setminus L\). \(\square \)
An implementation (as a Python/SAGE script) is included in [15] as check_WPP.sage.
Proposition 23
ECA 27 and 58 satisfy the weak periodic point condition.
6.2 SFT images
We show that ECA 9 and 28 have SFT images, while the others do not. We begin with the observation that one can do this easily by computer:
Proposition 24
It is decidable whether the image of a CA is an SFT.
Proof
The image subshift is sofic. To check if a sofic shift is an SFT, observe that by (Lind and Marcus 1995, Exercise 1.3.8), a subshift is an SFT if and only if the set of first offenders, i.e. the minimal forbidden words, is finite. If L is the complement of the language of \(X \subset \Sigma ^{\mathbb {Z}}\), then the first offenders are by definition exactly the language \(L {\setminus } (\Sigma ^+ L \cup L \Sigma ^+)\), where \(\Sigma ^+\) denotes the non-empty words over \(\Sigma \); regular languages are effectively closed under these operations and it is trivial to check if a regular language is finite. \(\square \)
In the remainder of this section, we give more or less ad hoc human proofs of SFTness and proper soficness of images, not following this algorithm.
Proposition 25
ECA 28 has SFT image, defined by a single forbidden word 111.
The reader may also find the labeled de Bruijn graph given in Fig. 1 helpful.
As we saw in the proof of Proposition 20, the only preimage of 11 is 0100, so 111 does not have a preimage.
We describe a procedure (in fact, a type of transducer) giving preimages for transitive points (points containing every finite word that appears in the image, which are clearly dense). As we saw in the proof of Proposition 20, the only preimage of 11 is 0100, so 111 does not have a preimage. Now, consider a transitive point in the SFT with 111 forbidden (note that this SFT is mixing, so one exists). To construct a preimage, on top of every 11 put the word 0100. Now start filling the gaps to the right from each 0100 already filled. For the leftmost run of 0s, write 0s on top. When you reach the first 1, write 1 on top of it. If it is part of a 11, you have completed the run successfully. Otherwise, start filling according to the shift-and-flip-rule. \(\square \)
Proposition 26
ECA 27, 41 and 58 have proper sofic images.
Proof
For ECA 27, the word 0100 is synchronizing for the de Bruijn automaton. It is then easy to verify that for large n, \({^\omega }0 1 1 0 (00)^n 1 {^\omega }\) is in the image subshift, but \({^\omega }0 1 1 0 0 (00)^n 1 {^\omega }\) is not, which immediately shows that the image is proper sofic.
For ECA 41, we similarly see that 111 is synchronizing, and then that \({^\omega }0 111 00 (000)^n 11 0 {^\omega }\) is in the image subshift, but \({^\omega }0 111 0 (000)^n 11 0 {^\omega }\) is not. For ECA 58 we similarly see that 0100 is synchronizing, and from this it is clear that \({^\omega }0 1 0 {^\omega }\) is in the image subshift, but \({^\omega }0 1 0^n 1 0 {^\omega }\) is not. \(\square \)
Remark 2
We found the above proofs by performing the subset construction on the de Bruijn automaton and looking for cycles. Analyzing cycles is a general way to prove proper soficity, in the sense that if we have a DFA for the language of a proper sofic subshift, we can always find words u, v, w such that \(uv^n\) and \(v^nw\) are in the language for all n, but the words \(u v^n w\) are not (for any n). To see this, apply a suitable variant of the pumping lemma to a long first offender. Such a triple is also easy to verify from the DFA. In the case of the ECA, we found cycles consisting of singleton states (in the subset DFA), and following the suggestion of the anonymous referee, we rephrased the proof in terms of synchronizing words instead.
Proposition 27
ECA 9 has SFT image with first offenders
$$ 1011, 10101, 11001, 11000011, 110000101. $$
Proof
Performing the subset construction and complementation on the de Bruijn automaton, and merging the state \(\{00,01,10\}\) into \(\{0,1\}^2\) (as they are clearly equivalent), we obtain a DFA for the orphans of ECA 9.
The DFA is shown in Fig. 2. By renaming the states by the maximal relevant suffix we have seen, we can directly interpret this as a DFA for one-way infinite words that lack the listed offenders, see Fig. 3. The main thing to note is that having seen the 1100001 is equivalent to having seen 101, as continuations 01, 1 fail and continuation 00 resets the state. \(\square \)
Fig. 2
DFA for orphans of ECA 9. For conciseness we use the binary variables a, b to express arbitrary bits, e.g. aa represents the state \(\{00, 11\}\). By \(\lnot \) we denote complement, e.g. \(\lnot aa\) represents \(\{01, 10\}\)
Fig. 3
The DFA from Fig. 2 with states renamed with the suffix they are tracking
×
×
7 Von Neumann regularity of elementary CA
Theorem 28
The elementary CA with numbers 6, 7, 23, 33, 57 and 77 are regular.
Proof
We found weak inverses by computer. A program (written for Python version 3.9) for finding inverses can be found at [15] in find_weak_inverses.py. In Sect. 7.1 we describe the simple procedure used to find the weak inverses, and in Sect. 7.2 we give hexadecimal codes for them. \(\square \)
7.1 The procedure
To find the weak inverses for 6, 7, 23, 33, 57 and 77, we used the following very simple procedure (executed by computer). We go through the possible radii in increasing order, and for each we enumerate the (possibly empty) list of weak inverses of that radius, until we find the first radius for which an inverse exists.
For a given radius r, the weak inverses g can be listed as follows. First, we consider all periodic points up to some period p, and compute their periodic images under the ECA f being considered. Each periodic point in the image of f must be mapped by g to one of its f-preimages with the same period, and we keep track of the possible choices with a mapping d from periodic points (i.e. cyclic words) to their possible g-images. We then compute the words of length \(2r+1\) in the image of the ECA, and construct a partial local rule for the weak inverse, call this local rule \(\ell \) (initially all the entries hold an unknown value ?).
We then iterate the following simplification steps, which are simply the obvious mutual consistency conditions for d and \(\ell \), until reaching a fixed point:
If a periodic point \(x\) has only one preimage left in \(d\), set the corresponding values in \(\ell \) and drop \(x\) from \(d\).
If some possible choices in d are inconsistent with \(\ell \), remove them.
If after reaching the fixed point we have not yet determined the \(\ell \)-image of some word, pick a random such word, recursively try both values for the \(\ell \)-image and enumerate the results.
We initially also used the following consistency condition:
If all the possible preimages of a particular periodic point have a particular bit b in position i, then we can safely make \(\ell \) map the word at \([i-r, i+r]\) to b.
We also experimented with more sensible choices for the choice of a new image in \(\ell \). With a naive implementation, these only made the calculation slower, but such ideas (and even the strong periodic point condition) might be more useful with larger neighborhoods and state sets.
Finding the inverses using this procedure takes a few seconds with the highly non-optimized Python program find_weak_inverses.py in [15]. For ECA 7, finding the unique weak inverse takes only a few minutes when performed by hand. The optimal radii and p used are listed in Table 2, and we give the actual inverses in the following section.
Table 2
For the regular ECA, the optimal radius for a weak inverse, the number of inverses (counting only the possible behaviors on the words in the image of the ECA), and the p-value we used when executing the algorithm
Optimal r
Number of inverses
Recommended p
ECA 6
3
2
9
ECA 7
2
1
6
ECA 23
2
1
5
ECA 33
2
1
6
ECA 57
4
32
11
ECA 77
2
1
6
7.2 The weak inverses
In the conference version (Salo 2021) of this paper, we picked the behavior of the weak inverse rules on an ad hoc basis on the words not in the image subshift, in order to get a nice presentation for each rule. Here, as we give the exhaustive list, it seems cleaner to simply output 0 on the inputs that do not appear in the image subshift, which means that the rule numbers are different from those reported in the conference version even in the case when the weak inverse is “unique”.
To get all weak inverses of the optimal radius r, take one of the rules listed in the propositions below, compute the words L in the image subshift of the ECA in question (for example by applying the ECA to all words of length \(2r+3\)), and change 0 to 1 on any of the words in the complement of L. These propositions are simply a summary of the output of the program find_weak_inverses.py in [15]. There is also a separate (independent) script check_weak_inverses.py in [15] that verifies these propositions.
Proposition 29
The radius 3 weak inverses for ECA 6, which map to 0 outside the image subshift, have hex codes
$$ 00000e030f03000f00000e0f0f030e0{*} $$
where \({*}\) is replaced by one of 7, f.
Proposition 30
The unique radius 2 weak inverse for ECA 7, which maps to 0 outside the image subshift, has hex code 21232123. On the image subshift of ECA 7, this is equivalent to the ECA 35 composed with \(\sigma \), which has hex code 23232323.
Proposition 31
The unique radius 2 weak inverse for ECA 23, which maps to 0 outside the image subshift, has hex code 23bb003b.
Proposition 32
The unique radius 2 weak inverse for ECA 33, which maps to 0 outside the image subshift, has hex code 00070707.
Proposition 33
The radius 4 weak inverses of ECA 57, which map to 0 outside the image subshift, are
The unique radius 2 weak inverse for ECA 77, which maps to 0 outside the image subshift, has hex code 00733177.
8 Most cellular automata are non-regular
In the conference version (Salo 2021) of this paper, we stated:
[...] Based on this, one might conjecture that regularity is common in cellular automata as radius grows.
We show that in fact most cellular automata are non-regular, for rather uninteresting reasons, namely the weak periodic point condition fails with high probability. Post-composition with a shift preserves regularity, so we restrict to CA with one-sided neighborhoods in the statement. By one-sided radius r we refer to neighborhood [0, r]. Clearly all CA with one-sided radius \(r = 0\) are regular, so we restrict to larger radii. Similarly, we do not consider alphabets with one or fewer letters.
Theorem 35
Let \(X_{n,r}\) be a uniformly random one-sided CA with radius r over an alphabet of size n. Then as \(n+r \rightarrow \infty \), with high probability \(X_{n,r}\) is non-regular, and indeed the weak periodic point condition fails.
More precisely, for all \(\epsilon > 0\) there exists \(n_0\) such that for all \(n+r \ge n_0\), \(n \ge 2\), \(r \ge 1\), \(X_{n,r}\) is regular with probability at most \(\epsilon \).
Proof
Let \({\mid }A {\mid }= n\) be the alphabet. Let us first show that for large n, \(X_{n,r}\) is very likely to be non-regular no matter what the value of r is. It turns out that it suffices to look at the behavior of points of period 1 or 2, namely we show that with high probability there is a point of period 1 with a preimage of period 2 but no preimage of period 1. Let \(P_1\) be the set of points of period 1. For \(a,b \in A\) with \(a \ne b\) write \(\iota (a,b) = abababa...\) and \(\iota (a) = aaa..\). All that matters to us is how f maps these points; note that this only depends on how the local rule maps inputs of the form abab... for \(a,b \in A\).
Note that the image of a point in \(P_1\) is uniformly chosen out of points in \(P_1\). Write N for the random number of points in \(P_1\) with a preimage in \(P_1\), and write I for this set. Next, let M be the number of pairs \(a, b \in A\), \(a \ne b\), such that \(f(\iota (a,b)) = f(\iota (b,a))\), meaning both \(\iota (a,b)\) and \(\iota (b,a)\) are mapped to a point in \(P_1\).
It is clear that, conditioned on fixed values of N and M, the following things are independent and uniformly distributed:
the actual set I (conditioned on N),
the M many choices of images \(f(\iota (a,b)) = f(\iota (b,a))\) for \(a \ne b\),
From this, it follows that if we have \(N < 0.9n\) and \(M \ge k\), then the probability that some pair is mapped to a unary point that is not in I is at least \(1 - 0.9^k\), which tends to 1 as \(k \rightarrow \infty \). It remains to show that \(N < 0.9n\) and \(M \ge k\) with high probability where \(k \rightarrow \infty \).
First, let us look at N. Writing \(N_a \in \{0, 1\}\) for the random variable indicating that the symbol \(a \in A\) has a preimage, \(N = \sum _a N_a\), we have
Here recall that for fixed k, \((1 + k/n)^n = e^k + O(1/n)\).
The claim now follows from Chebyshev’s inequality, which states that the difference between the value of a random variable and its mean is likely to be of the order of the square root of its variance. More precisely, writing \(\textrm{Var}(N) = \sigma ^2 = \alpha n\) (where \(\alpha = O(1)\) is technically a function of n) we have \(0.2 n = 0.2 \sigma \sqrt{n/\alpha }\), and by Chebyshev’s inequality
Next, we look at M. Order the alphabet and write \(M = \sum _{a < b} M_{a, b}\) where \(M_{a, b} \in \{0, 1\}\) is the random variable where \(M_{a,b} = 1\) denotes \(f(\iota (a,b)) = f(\iota (b,a))\). We see that M is simply a sum of independent random variables, thus follows the binomial distribution \(M \sim B(\left( {\begin{array}{c}n\\ 2\end{array}}\right) , 1/n) = B(m, p)\). The expected value is \(E(M) = pm = (n-1)/2\), and the variance is
so again with high probability the value is above, say 0.25n. Of course, we have \(k = 0.25 n \rightarrow \infty \).
To conclude, it clearly suffices to show that for any fixed n, cellular automata are non-regular with high probability for large r. The argument is essentially the same as the above, with minor changes: Instead of unary points, we use points of period p with \(2p \le r\) and p large. Most words of length p are primitive, i.e. the corresponding periodic point has least period p, write again \(P_p\) for this set. The set \(P_p\) splits into equivalence classes under the shift, and if we pick the local rule at random, then the image of each \(x \in P_p\) is picked uniformly from the set \(Q_p\) of points of (not necessarily least) period p.
The images for different points in \(P_p\) are independent from each other, so this is in fact the same distribution as we considered above, except that some periodic points may be mapped to a point of smaller period. Thus, by a coupling argument the probability that 90% of points in \(P_p\) have preimages in \(P_p\) is clearly at most as large as it was in the previous process.
Now, we just have to show that there are at least k points in \(P_p\) with preimages in \(P_{2p}\) with high probability, with k tending to infinity with r. We observe that images of points in \(P_{2p}\) are picked uniformly at random from points in \(Q_{2p}\), and are independent from each other and from the choices of images of points in \(P_p\). Thus, the calculation is the same as above, since given that a point in \(P_{2p}\) maps to a point in \(Q_p\), the probability that it did not map to \(P_p\) is negligible. \(\square \)
Acknowledgements
We thank Jarkko Kari for observing that Proposition 11 works in all dimensions. We thank Johan Kopra for pointing out that Lemma 10 is easier to prove than to find in Lind and Marcus (1995). We thank the anonymous referees for suggesting significant improvements to the presentation, and simpler proofs. In particular, the proof of Theorem 35 was simplified essentially.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Specifically, many things about “one-step behavior” of cellular automata (like surjectivity and injectivity) are decidable using automata theory, or the decidability of the MSO logic of the natural numbers under successor. No decision algorithm for split epicness using these methods is known. Split epicness is a first-order property where we quantify over cellular automata/block maps, and many such properties, for example conjugacy (Jalonen and Kari 2020), are undecidable.
