Descriptive Complexity of Sensitivity of Cellular Automata
Juliette Favereau (✉), Ville Salo · 2025
Read Descriptive Complexity of Sensitivity of Cellular Automata by Juliette Favereau (✉), Ville Salo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05012.txt.
Introduction
Juliette Favereau and Ville Salo settle a question about how hard a computing puzzle is. Their paper, from twenty twenty-five, studies cellular automata, grids of cells that update by simple rules. The puzzle asks whether a given machine is sensitive, meaning small input changes can grow large. They show the puzzle sits at a set level in the logic hierarchy for one-row grids, and one level higher for wider grids. That answers a question posed by Sablik and Theyssier.
Catalog record
| CREATOR | Juliette Favereau (✉), Ville Salo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-05012
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Descriptive Complexity of Sensitivity of Cellular Automata Juliette Favereau (✉), Ville Salo Abstract We study the computational complexity of determining whether a cellular automaton is sensitive to initial conditions. We show that this problem is Π 2 0 \Pi^{0}_{2} -complete in dimension 1 and Σ 3 0 \Sigma^{0}_{3} -complete in dimension 2 and higher. This solves a question posed by Sablik and Theyssier. 1 Introduction Cellular automata are discrete dynamical systems that exhibit complex behavior despite their simple local rules. There have been numerous attempts to classify such systems, with the first notable classification proposed by Wolfram [ 9 ] for one-dimensional cellular automata. However, this classification lacked rigorous formality, which led Kůrka [ 2 ] to propose a more formal classification of one-dimensional cellular automata based on their sensitivity to initial conditions. Other classification schemes have also been proposed, such as Culik’s classification. The arithmetical complexity of Culik’s classes has been established and demonstrated by Sutner in [ 8 ] . The decidability of Kůrka’s classes, particularly the problem of sensitivity to initial conditions, was studied by Durand et al. [ 1 ] , while the reversible case was addressed by Lukkarila [ 4 ] . Sablik and Theyssier [ 7 ] showed that Kůrka’s classification no longer holds in higher dimensions and that additional classes must be introduced. In the same article, they investigated the arithmetical complexity of Kůrka’s classes. They demonstrated that sensitivity to initial conditions is \Pi^{0}_{2} in one dimension, but did not prove completeness, and showed \Sigma^{0}_{3} -hardness starting from dimension three, but the exact complexity of sensitivity within the arithmetical hierarchy was left open. Understanding the dynamical properties of cellular automata, particularly their sensitivity to initial conditions, is crucial for characterizing their behavior. In this paper, we address these open questions and provide a precise characterization of the computational complexity of determining sensitivity across different dimensions. Specifically, we demonstrate that sensitivity to initial conditions is \Pi^{0}_{2} -complete in one dimension and \Sigma^{0}_{3} -complete in two dimensions and higher. As a corollary, we provide a new proof that the finite nilpotency problem for cellular automata, originally proven by Sutner in [ 8 ] , is \Pi^{0}_{2} -complete. Additionally, we explore an application of our results by constructing a cellular automaton whose sensitivity is equivalent to the truth of the twin prime conjecture. These findings not only fill gaps left by previous research but also expose the fundamental difference in complexity between one-dimensional and higher-dimensional cellular automata with respect to sensitivity. Our main results establish a complete classification of the complexity of the sensitivity problem in cellular automata. We formally state them as follows. For one-dimensional cellular automata, establish: Theorem 1.1 The problem of determining whether a one-dimensional cellular automaton is sensitive is \Pi^{0}_{2} -complete. For higher dimension, we establish: Theorem 1.2 For d>1 , the problem of determining whether a d -dimensional cellular automaton is sensitive is \Sigma^{0}_{3} -complete. The proofs of these theorems rely on embedding Turing machines into cellular automata and reducing the problems TOT and COF to the respective sensitivity problem. With these new results, the classification of cellular automata with respect to sensitivity can be summarized in Table 1 . Formal definitions and preliminaries are provided in Section 2 . We present the proof of Theorem 1.1 in Section 3 , and the proof of Theorem 1.2 in Section 4 . An application is given in Section 5 . Table 1: Descriptive complexity of Kůrka’s classification of cellular automata. The set \mathcal{E} denotes the equicontinuity points. The notation \Pi^{0}_{2} -c indicates \Pi^{0}_{2} -completeness, while \Sigma^{0}_{1} -? signifies that completeness is unknown. A question mark (?) indicates that both completeness and the position in the hierarchy are unknown. Our contributions are highlighted with an asterisk. \mathcal{E}=A^{\mathbb{Z}^{d}} \mathcal{E}\neq\emptyset \mathcal{E}=\emptyset Sensitive Expansive d=1 \Sigma^{0}_{1} -c \Sigma^{0}_{2} -c ∗ \Pi^{0}_{2} -c ∗ \Pi^{0}_{2} -c ∗ \Sigma^{0}_{1} -? d>1 \Sigma^{0}_{1} -c ? ? \Sigma^{0}_{3} -c ∗ \Sigma^{0}_{1} -? 2 Preliminaries We will first recall some basic definitions that we will need throughout this document. Definition 1 (Cellular Automaton) A cellular automaton is a quadruple (d,S,N,f) where d is the dimension of the automaton, S is a finite set of states, N is a finite subset of \mathbb{Z}^{d} called the neighborhood, and f:S^{N}\to S is the local transition function. This induces a global function F:S^{\mathbb{Z}^{d}}\to S^{\mathbb{Z}^{d}} . The sensitivity to initial conditions is a property of dynamical systems that states that for any configuration, we can always find an arbitrarily close configuration that tends to diverge from our original configuration. To formalize this we endow S^{\mathbb{Z}^{d}} with the following metric: d(x,y)=2^{-\min\{\|n\|_{\infty}\mid x(n)\neq y(n)\}} (1) where \|n\|_{\infty}=\max_{1\leq i\leq d}|n_{i}| denotes the supremum norm on \mathbb{Z}^{d} . We formalize the concept of sensitivity in the following definition: Definition 2 (Sensitivity) A cellular automaton F is sensitive to initial conditions if there exists \epsilon>0 such that for all configurations x and \delta>0 , there exists y\in B_{\delta}(x) and n\in\mathbb{N} such that d(F^{n}(x),F^{n}(y))>\epsilon . In one dimension, a famous result states a connection between sensitivity and having words that block information, i.e., blocking words. Blocking words are characterized by a length that no information can cross. Indeed, to truly prevent information from propagating, such words must have a length larger than the automaton’s radius. Given a set K\subset\mathbb{Z}^{d} and a word w\in S^{K} , we write w\sqsubset_{K}u if u\in S^{\mathbb{Z}^{d}} contains w at position K , and we define the cylinder : \text{Cyl}(w,K)=\{u\in S^{\mathbb{Z}^{d}}\mid w\sqsubset_{K}u\} (2) We provide a definition of an m -blocking word: Definition 3 (m-blocking word) A word w\in S^{*} together with an integer p is m-blocking if for any configurations u,v\in\text{Cyl}(w,[0,|w|-1]) , for all n\in\mathbb{N},F^{n}(u)_{|[p,p+m]}=F^{n}(v)_{|[p,p+m]} . Hence, we can state the well-known characterization of sensitivity in one dimension: Theorem 2.1 (Kůrka [ 3 ] ) A one-dimensional cellular automaton with radius r is not sensitive if and only if it has an r -blocking word. We will also need a notion of blocking word in higher dimensions. In dimension d , we want an m -blocking word to be any pattern that contains a subpattern of size m^{d} that no information can enter. We define the shift action by: \displaystyle\sigma^{p}(x)_{u} \displaystyle=x_{u+p},\quad\forall x\in S^{\mathbb{Z}^{d}},\ \forall u,p\in\mathbb{Z}^{d} (3) \displaystyle\sigma^{p}(K) \displaystyle=\{u+p\mid u\in K\},\quad\forall K\subset\mathbb{Z}^{d},\ \forall p\in\mathbb{Z}^{d} (4) Definition 4 (Higher dimensional m-blocking word) For any finite subset K\subset\mathbb{Z}^{d} together with a vector p\in\mathbb{Z}^{d} such that \sigma^{p}([0,m]^{d})\subseteq K , a word w\in S^{K} is m-blocking if for any configurations u,v containing w at the position K , for all n\in\mathbb{N} , F^{n}(u)_{|\sigma^{p}([0,m]^{d})}=F^{n}(v)_{|\sigma^{p}([0,m]^{d})} . With that definition, we state the following lemma that shows how one can extend the blocking word characterization for higher-dimensional cellular automata. Lemma 1 A cellular automaton is not sensitive if and only if it has arbitrarily large blocking words. Proof If F is a sensitive cellular automaton, there exists \epsilon>0 such that for all x and \delta>0 , there exists y\in B_{\delta}(x) and n such that d(F^{n}(x),F^{n}(y))>\epsilon . This means that there exists m>-\log_{2}(\epsilon) such that arbitrarily close configurations will eventually differ on [0,m]^{d} , hence there is no m -blocking word. Conversely, if F is not sensitive, for every \epsilon>0 and m>-\log_{2}(\epsilon) , we can find a pattern \pi such that every configuration that matches with