# Descriptive Complexity of Sensitivity of Cellular Automata

Tom Favereau, Ville Salo

<figure><img src="image_1.png" /></figure>

To cite this version:

Tom Favereau, Ville Salo. Descriptive Complexity of Sensitivity of Cellular Automata. 2025. hal-05023429

HAL Id: hal-05023429

https://hal.univ-lorraine.fr/hal-05023429v1

Preprint submitted on 7 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Descriptive Complexity of Sensitivity of Cellular Automata

Tom Favereau<fnref n="1" />(✉) [0009-0008-5876-8676] and Ville Salo<fnref n="2" />[0000-0002-2059-194X]

**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$-complete in dimension 1 and $Σ_3^0$-complete in dimension 2 and higher. This solves a question posed by Sablik and Theyssier.

**Keywords:** Cellular automata, Sensitivity, Arithmetical hierarchy

## 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 [7] 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 [6]. 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 [3].

Sablik and Theyssier [5] 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 $Π_2^0$ in one dimension, but did not prove completeness. For dimensions three and higher, they showed it to be $Σ_3^0$-hard. However, they did not provide results for two dimensions. They raised these two questions in their paper.

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 $Π_2^0$-complete in one dimension and $Σ_3^0$-complete in two dimensions and higher.

<footnote n="1">¹ Mines Nancy, University of Lorraine, France</footnote>

<footnote>tom.favereau@etu.mines-nancy.univ-lorraine.fr</footnote>

<footnote n="2">² University of Turku, Finland</footnote>

<footnote>vosalo@utu.fi</footnote>
As a corollary, we provide a new proof that the finite nilpotency problem for cellular automata, originally proven by Sutner in [6], is $Π_2^0$-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.** *The problem of determining whether a one-dimensional cellular automaton is sensitive is $Π_2^0$-complete.*

For higher dimension, we establish:

**Theorem 2.** *For $d > 1$, the problem of determining whether a $d$-dimensional cellular automaton is sensitive is $Σ_3^0$-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 in Section 3, and the proof of Theorem 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 $Π_2^0$-c indicates $Π_2^0$-completeness, while $Σ_1^0$-? 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.

<table><thead><tr><th></th><th>ε = A<sup>Z<sup>d</sup></sup></th><th>ε ≠ ∅</th><th>ε = ∅</th><th>Sensitive</th><th>Expansive</th></tr></thead><tbody><tr><td>d = 1</td><td>Σ<sub>1</sub><sup>0</sup>-c</td><td>Σ<sub>2</sub><sup>0</sup>-c*</td><td>Π<sub>2</sub><sup>0</sup>-c*</td><td>Π<sub>2</sub><sup>0</sup>-c*</td><td>Σ<sub>1</sub><sup>0</sup>-?</td></tr><tr><td>d > 1</td><td>Σ<sub>1</sub><sup>0</sup>-c</td><td>?</td><td>?</td><td>Σ<sub>3</sub><sup>0</sup>-c*</td><td>Σ<sub>1</sub><sup>0</sup>-?</td></tr></tbody></table>

## 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 CA, $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} | x(n) \neq y(n)\}} \quad (1)$$

where $\|n\|_{\infty} = \max_{1 \le i \le 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 \sqsubseteq_K u$ if $u \in S^{\mathbb{Z}^d}$ contains $w$ at position $K$, and we define the *cylinder*:

$$Cyl(w, K) = \{u \in S^{\mathbb{Z}^d} | w \sqsubseteq_K u\} \quad (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 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 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 cross.

We define the *shift action* by:

$$\sigma^p(x)_u = x_{u+p}, \quad \forall x \in S^{\mathbb{Z}^d}, \forall u, p \in \mathbb{Z}^d \quad (3)$$
**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 $\pi$ at position 0 will never differ on $[0, m]^d$. Hence, we have arbitrarily large blocking words.

Turing machines are abstract computational models that provide a formal definition of a computable function. These machines can perform basic operations such as reading, writing, and moving the head. Their power lies in their ability to simulate any algorithm or computational process. We will use them to prove our complexity results.

A Turing machine is formally defined as a 6-tuple $(Q, A, q_i, q_h, \delta, \Gamma)$ where $Q$ is a finite set of states, including an initial state $q_i$ and a halting state $q_h$; $A$ is a finite alphabet that includes a blank symbol; $\Gamma \subseteq A$ is the input alphabet; and $\delta: Q \times A \to Q \times A \times \{-1, 0, 1\}$ is the transition function, such that for all $a \in A$, $\delta(q_h, a) = (q_h, a, 0)$.

The transition function $\delta$ determines the machine's behavior: given a current state and a symbol under the head, it specifies the next state, the symbol to write, and the direction to move the head (-1 for left, 0 for stay, 1 for right).

Fix an enumeration of Turing machines, we denote $W_e := \{x \mid M_e(x) \downarrow\}$ the set of inputs on which the machine halts. We introduce the two sets we will use in our proof:

$$ \text{TOT} := \{e \mid W_e = \mathbb{N}\} \qquad (4) $$

and

$$ \text{COF} := \{e \mid W_e \text{ is cofinite}\} \qquad (5) $$

**Lemma 2.** TOT is $\Pi_2^0$-complete and COF is $\Sigma_3^0$-complete.

*Proof.* The reader can find a proof of these results in [4].

Let us note a basic result about Turing machines: one-way tape Turing machines are equivalent to two-way tape Turing machines.
**Proposition 1.** Given a two-way Turing machine $M_2$, there exists a one-way Turing machine $M_1$ such that for all $x \in \mathbb{N}$, $M_2$ halts on $x$ if and only if $M_1$ halts on $x$.

*Proof.* The backward direction is trivial. For the converse, we can simulate any two-way Turing machine on a one-way tape by instructing the machine, when it wants to move left to 0, to copy all its non-blank symbols one step to the right.

In particular, this proposition allows us to consider the sets **TOT** and **COF** as sets of indices of one-way Turing machines.

Finally, we introduce our main tool for lifting results to higher dimensions: slicing.

**Definition 5 (Slicing).** For any $d$-dimensional cellular automaton with global function $F$, we can construct a $(d+1)$-dimensional cellular automaton with the same function $F$, which corresponds to applying the $d$-dimensional cellular automaton independently on each hyperplane $x_{d+1} = k$ (called a **slice**).

This construction often allows us to reduce a $d$-dimensional problem to a $(d+1)$-dimensional one.

## 3 One-dimensional Cellular Automata

In this section, we prove our first result: the $\Pi_2^0$-completeness of the sensitivity problem for one-dimensional cellular automata. We begin with a simple lemma.

**Lemma 3.** The problem of determining whether a given cellular automaton has an $m$-blocking word is in $\Sigma_2^0$.

*Proof.* Observe that in the definition of a blocking word, we only need to quantify over finite objects. Hence, having an $m$-blocking word can be written as:

$$ \exists K \subset \mathbb{Z}^d, \exists p \in \mathbb{Z}^d, \exists w \in S^K, \forall u, v \in (S^d)^*, n \in \mathbb{N}, \\ (\sigma^p([0, m]^d) \subset K \wedge w \sqsubseteq_K u \wedge w \sqsubseteq_K v) \qquad (6) \\ \implies F^n(u)|_{\sigma^p([0,m]^d)} = F^n(v)|_{\sigma^p([0,m]^d)} $$

This formulation clearly places the problem in $\Sigma_2^0$.

### 3.1 Upper Bound on Complexity of the Sensitivity Problem

The sensitivity problem for one-dimensional cellular automata is in $\Pi_2^0$. The proof follows directly from Lemma 3. We note that this result was already known from Sablik and Theyssier [5].

**Lemma 4.** The problem of determining whether a one-dimensional cellular automaton is sensitive to initial conditions is in $\Pi_2^0$.

*Proof.* A cellular automaton is sensitive to initial conditions if and only if it does not have a blocking word of any length. This is clearly a $\Pi_2^0$ formula, as it negates a $\Sigma_2^0$ formula (from Lemma 3).
## 3.2 Construction of $G_e$

To prove $Π_2^0$-hardness, we reduce from TOT, which is known to be $Π_2^0$-hard. Given a number $e$ in, we denote the associated Turing machine by $M_e = (Q, A, q_i, q_h, δ, Γ)$. Let us first recall that we do not change the problem by requiring $M_e$ to operate only on a one-way infinite tape.

It is important to note that we must consider all possible configurations, including those where the Turing machine has performed an incorrect computation. These 'degenerate' configurations arise because any configuration can serve as an initial configuration of the cellular automaton. We will explain how to address this issue in the following sections of the construction.

We construct a cellular automaton $G_e$ as follows:

The state set of $G_e$ is $(Γ \cup \{□\}) \times ((Q \cup \{□\}) \times A) \times (\{<, >, p\} \cup X)$, where: < and > are delimiter symbols that partition the space into computational blocks and $X = \{x_r, x_l, x_0\}$ is a set of elements that handle the extension of the computational zone and restart the Turing machine on the input tape to prevent degenerate configurations.

It is a three-tape cellular automaton with a witness input tape, a working tape, and a delimiter tape.

The cellular automaton $G_e$ simulates multiple copies of $M_e$, where each copy operates within its own computational block, delimited by sequences of < and > symbols. A typical configuration is shown in Figure 1.

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Structure of computational blocks in $G_e$. The upper row shows the delimiters and machine heads, while the lower rows show the tape content.</figcaption></figure>

The transition rules of $G_e$ enforce the following behaviors:

1. The set $X$ contains $x_r$, which moves to the right on computational blocks, $x_l$, which moves to the left, and $x_0$, which moves to the left while resetting the computation on the witness tape. Symbols move back and forth in the computational zone and always try to extend it to the right when possible. When this happens, the Turing machine restarts on the input tape (eventually eliminating degenerate configurations).

2. < and > delimit computational blocks. $x_r$ can only move to the right if it is to the left of a <; otherwise, it becomes an $x_l$. Similarly $x_0$ and $x_l$ can only move to the left if they are to the right of a >; otherwise, they become an $x_r$.
3. The blank symbol on the witness tape propagates to the right on the computational block, preventing the input from being divided by a blank.

4. When a machine halts, it writes a blank symbol that propagates throughout the computational block.

5. The $x$ symbol can extend its computational block if and only if the machine to its right has been destroyed.

6. $p$ is a particle that always travels to the right on blank symbols of the first tape and gets destroyed when it encounters non-blank cells. It allows us to establish sensitivity.

We provide the complete rule of the cellular automaton $G_e$ in Figure 2.

### 3.3 Lower Bound and $Π_2^0$-Hardness

**Lemma 5.** For any $e \in \mathbb{N}$, the Turing machine $M_e$ halts on all inputs if and only if the cellular automaton $G_e$ is sensitive.

*Proof.* We now prove that $e \in \text{TOT}$ if and only if $G_e$ is sensitive.

*If* $e \in \text{TOT}$: We need to show that $G_e$ is sensitive. Let $w$ be any word. We can take $y \in \text{Cyl}(w)$ such that $y$ has only blank symbols (on all tapes) to the right of $P$, and to the left of $P$, there is an $p$ particle moving to the right and blank symbols.

Since $e \in \text{TOT}$, all computational blocks in $w$ will eventually be destroyed. Indeed, in the rightmost computational block in $w$, the $x$ symbols will eventually be inserted and then be able to extend the computational block arbitrarily far, allowing the Turing machine to compute on its input without being restarted and with arbitrary large space. Hence, the rightmost Turing machine will halt and erase itself in finitely many steps, leaving space for the machine to its left. Therefore, in finitely many steps, $w$ will become blank. Thus, the particle we placed to the left of $w$ can pass through $w$ if the particle is placed far enough. Therefore, since we can choose whether or not to place the particle, this establishes sensitivity.

*If* $e \notin \text{TOT}$: Then there exists an input $n$ such that $M_e$ runs forever on $n$ without halting. Consider the word pattern $uu$ where $u$ is a computational block of size at least radius of $G_e$ containing input $n$. The machine simulated in the second copy of $u$ will never halt and will never be destroyed. Consequently, the machine in the first copy of $u$ remains confined to its computational block and likewise never halts. This creates a barrier that no information can cross. Therefore $uu$ is an $r$-blocking word, proving that $G_e$ is not sensitive.

Thus, we have shown that $G_e$ is sensitive if and only if $e \in \text{TOT}$. Since the TOT problem is $Π_2^0$-hard,

*Proof (Theorem 1).* By Lemma 4, we know that the sensitivity problem is in $Π_2^0$, and by Lemma 5, we have hardness. We conclude that determining sensitivity for one-dimensional cellular automata is $Π_2^0$-complete. This proves the theorem.
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Complete transition function of the cellular automaton $G_e$. Black cells act as wildcards and can match any state in the neighborhood. When no rule applies, the cell remains unchanged.</figcaption></figure>
As a corollary of these constructions, we obtain a new proof of Sutner's result on finite nilpotency [6].

**Corollary 1.** The problem of determining whether a cellular automaton is nilpotent on finite configurations is $Π_2^0$-complete.

*Proof.* Given a one dimensional cellular automaton $G$, finite nilpotency is a $Π_2^0$ property since it requires

$$ \forall w \in A^*, \forall k \in \mathbb{N}, \exists n \in \mathbb{N}, G(0^k w 0^k) = 0. \qquad (7) $$

We obtain hardness by reducing TOT and removing particle $p$ in our construction of $G_e$. Hence, from our previous proof, all finite patterns $P$ will eventually become blank if and only if the given Turing machine halts on every input. We can then lift the result to higher dimensions using slices. For any $d$ and a $d$ dimensional cellular automaton $G$ which is finitely nilpotent. Consider the slice version of $G$. Any finite configuration on $A^{2^{d+1}}$ is finite on every slice and non-null on finitely many. Therefore, the slice version of $G$ is finitely nilpotent if and only if $G$ is. By induction, finite nilpotency is $Π_2^0$-complete.

# 4 Higher Dimensional Cellular Automata

In this section, we extend our analysis to cellular automata in two or more dimensions and prove Theorem 2.

## 4.1 Upper Bound: $Σ_3^0$

We begin by showing that for any $d > 1$, the sensitivity problem for $d$-dimensional cellular automata belongs to the arithmetical hierarchy. First, we recall a crucial lemma from our previous discussion, Lemma 1: A cellular automaton is not sensitive if and only if it has an arbitrarily large blocking word. We then state the following lemma.

**Lemma 6.** For any $d > 1$, the problem of determining whether a $d$-dimensional cellular automaton is sensitive is $Σ_3^0$.

*Proof.* Recall that the property "there exists an $M$-blocking word" is $Σ_2^0$ by Lemma 3. Therefore, by Lemma 1, being non-sensitive is $Π_3^0$, as it requires the existence of $M$-blocking words for all sufficiently large $M$. Consequently, being sensitive is $Σ_3^0$. This establishes that the sensitivity problem is at most $Σ_3^0$.

## 4.2 Lower Bound: $Σ_3^0$-Hardness

In this section, we aim to prove the following result:

**Theorem 4.** The problem of determining whether a two-dimensional cellular automaton is sensitive is $Σ_3^0$-complete.
To prove $\Sigma_3^0$-hardness, we reduce from the Cofinite Set (COF) problem, which is known to be $\Sigma_3^0$-hard. For each $e$, let $M_e = (Q, A, q_i, q_h, \delta, \Gamma)$ be the associated Turing machine. We construct a 2D cellular automaton $G_e$ as follows:

The states of $G_e$ are $(A \cup \{\square\}) \times (Q \cup \{\square\}) \times (T \cup \{\square\}) \times (P \cup \{\square\}) \times \{\text{red1, red2, red3, red4, white, green}\}$.

Where $P = \{p_r, p_l, q_r, q_l, p_{ru}, p_{rd}, p_{lu}, p_{ld}, q_{ru}, q_{rd}, q_{lu}, q_{ld}\}$ is a set of particles, $T = Q \cup \{t_h\}$, with $Q$ a set of states for tentacles and $t_h$ a signal for halting. The colors red, white, and green delimit the computational zones.

We describe the cellular automaton's behavior as follows:

Each red cell can have at most two red neighbors. A red cell marked with 1 can have either a 1 neighbor to the west and a 1 neighbor to the east, a 2 neighbor to the west and a 1 neighbor to the east, or a 4 neighbor to the north and a 1 neighbor to the west. Other marker rules are given Figure 3. Consequently given a finite configuration, after finitely many steps, the only remaining red zones are the ones forming rectangular loops (Lemma 7), these rectangles will form the tape of Turing machines.

$P$ is a set of particles, that move on white or green cells. There are two types of particles: $p$ particles, which send a signal to a Turing machine to process one step of computation, and $q$ particles, which place a Turing machine at the beginning of the tape in the initial state. The particles $p$ and $q$ are divided into right and left particles ($p_r, p_l$) that move to the right and left, respectively. When they meet at the beginning of a tape, they send a signal into that tape. If a particle meets an obstacle (i.e. a red zone) it divides into an up particle and a down particle ($p_{ru}, p_{lu}, p_{rd}, p_{ld}$) that follow the red loop and reform when meeting again.

When a $p$-signal enters a red zone, it follows the loop guided by the 1, 2, 3, and 4 markers. When it encounters a Turing machine head, it allows the head to process one step of computation. The Turing machine head is guided along the loop by the markers. If it encounters another head on the tape, it erases that head. When it halts, it erases itself and the red zone.

When a machine runs out of space, it requests the creation of a tentacle that operates with $T$ symbols on green zones. Tentacles always grow to the east, or to the north if there is a red zone in the eastward position. These extension rules define local rules, and tentacles can be defined as green zones respecting these rules. The set $T$ contains copies of states of $M_e$ and includes a signal $t_h$ that is sent when the machine halts to destroy the connected red zone. By the first rules, when two green zones meet, they erase each other.

We give below the main rules of the cellular automaton $G_e$ in Figure 3.

**Lemma 7.** *Given a finite configuration, after finitely many steps all red zones will form rectangular loops, and all green zones will become tentacles. This process is illustrated in Figure 4.*

*Proof.* Given a finite configuration, each green cell which does not follow local rules will become white, hence in finitely many steps the green zone will be erased and the only remaining connected green zones will be the ones that follow local rule i.e. tentacles.
Consider the 5-state cellular automaton with states {0, 1, 2, 3, 4} with the transition rules of red1, red2, red3, red4, and white, as shown in Figure 3. Given a 0-finite configuration, the local rules force any connected non-zero zone to form a spiral (the proof is omitted). If a connected non-zero zone spirals inward, a conflict arises because the spiral cannot continue infinitely. If it spirals outward, it also leads to a conflict due to the finiteness of the configuration. Therefore, the only possible connected non-zero zones are those that form rectangles.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Illustration of the stabilization process. (a) Defective red regions are progressively eliminated. (b) Green regions are removed in parallel. (c) A representative configuration after the system has stabilized.</figcaption></figure>

**Lemma 8.** *Given a finite configuration, we can send particles from outside the configuration to meet at any position outside the red zones within the configuration after the red zones have stabilized.*

*Proof.* Consider a finite configuration in which the only red zones are rectangular loops, and suppose there is a single right-moving particle (possibly split) to
the left of a left-moving particle (possibly split), both located outside the red zones. This configuration has a preimage. This follows from the fact that red zones are rectangular, allowing us to trace the evolution backward using the local rules. Moreover, since the right-moving particle is to the left of the left-moving one, they could not have met in the past. We place the particles at the desired meeting point and trace the consecutive preimages of the configuration backward. This allows us to determine where to initially place the particles outside the configuration so that they meet as intended. We only need to place them sufficiently far from the configuration to ensure that the red zones have time to evolve into rectangular loops.

**Lemma 9.** For any $e \in \mathbb{N}$, the Turing machine $M_e$ halts on all but finitely many inputs if and only if the associated cellular automaton $G_e$ is sensitive.

*Proof.* We prove that $e \in \text{COF}$ if and only if $G_e$ is sensitive. Let $x$ be any finite configuration, by Lemma 7 in finite time all red zone will be rectangular red loops. These rectangular loops will be our Turing machines tapes and the input of a Turing machines will the length of its loop/tape divided by two.

*If* $e \in \text{COF}$: Let $x$ be any finite configuration. In finite time, $P$ will be constituted of rectangular red loops, white zones, and tentacles. For any accessible red zone (not inside another), we can send a particles $q$ to place a Turing machine on the zone. We can then send processing particles in those zones. Because inaccessible zones are surrounded by red zones, if these zones are sufficiently large, they must be surrounded by a large red area. Since $e \in \text{COF}$, there exists an $N$ such that for all $y > N$, $M_e$ halts on $y$. Therefore, any sufficiently large block will have its border destroyed because the Turing on that tape will eventually halt, allowing us to send particles through it. by Lemma 1, $G_e$ is sensitive.

*If* $e \notin \text{COF}$: Then there exist infinitely many $y$ such that $M_e(y)$ does not halt. We can construct arbitrarily large blocking words as follows: For any $M > 0$, choose $y > M$ such that $M_e(y)$ does not halt. Construct a red rectangle with perimeter $2y$. This rectangle forms an $M$-blocking word, as:

1. The Turing machine simulating $M_e(y)$ will never halt, so the rectangle will never be destroyed. 2. No particles can penetrate the red border. 3. The interior of the rectangle is inaccessible to any external influence.

Since we can construct such blocking words for arbitrarily large $M$, by Lemma 1, $G_e$ is not sensitive.

*Proof (Theorem 4).* By Lemma 6, we know that the sensitivity problem for two-dimensional cellular automata is $\Sigma_3^0$, and by Lemma 9, we have established hardness. Hence, the theorem is proved.

*Proof (Theorem 2).* By Lemma 6, we know that the sensitivity problem for $d$-dimensional cellular automata is in $\Sigma_3^0$. We prove $\Sigma_3^0$-hardness by reducing from the two-dimensional case using a slicing argument.
Let $G_d$ be a $d$-dimensional cellular automaton, and let $G_{d+1}$ be its slice extension to dimension $d+1$. Suppose $w_d$ is an $m$-blocking word for $G_d$ over some finite set $K \subset \mathbb{Z}^d$. Then the word

$$w_{d+1}(x, x_{d+1}) = w_d(x), \quad \forall x_{d+1} \in [0, m-1], \quad \forall x \in K \quad (8)$$

defines an $m$-blocking word for $G_{d+1}$. Therefore, if $G_d$ is not sensitive, neither is $G_{d+1}$.

Conversely, if $G_d$ is sensitive, then it does not admit arbitrarily large blocking words, so information can propagate in slices. Hence, $G_{d+1}$ is also sensitive. By induction on $d$, this proves the theorem.

This construction establishes a reduction from COF to the sensitivity problem, proving that the latter is $\Sigma_3^0$-hard. Combined with our earlier upper bound, this shows that the sensitivity problem for $d > 1$ dimensional cellular automata is $\Sigma_3^0$-complete.

# 5 Application

In this section, we explore an application of our results in number theory, specifically in relation to the twin prime conjecture. While we do not believe this to be a suitable approach for solving the twin prime conjecture, we argue that it demonstrates a concrete application of the arithmetical hierarchy that are not often explored. Furthermore, this construction illustrates how complexity classifications can provide unexpected connections between different areas of mathematics.

**Proposition 2.** The twin prime conjecture is a $\Pi_2^0$ statement in the arithmetic hierarchy.

*Proof.* The twin prime conjecture can be stated as:

$$\forall n, \exists p (p > n \land \mathrm{Prime}(p) \land \mathrm{Prime}(p+2)) \quad (9)$$

We construct a Turing machine $M$ that, given an input $n$ in unary (represented by a string of 0s), halts if and only if it finds a pair of twin primes larger than or equal to $n$.

**Theorem 5.** There exists a cellular automaton $G_e$ that is sensitive to initial conditions if and only if the twin prime conjecture is true.

*Proof.* By our construction, the Turing machine $M$ halts on all inputs if and only if the twin prime conjecture is true. Using our reduction from the TOT problem to the sensitivity problem for cellular automata, we can construct a cellular automaton $G_e$ that is sensitive to initial conditions if and only if $M$ halts on all inputs. Therefore, $G_e$ is sensitive to initial conditions if and only if the twin prime conjecture is true.

We have implemented this cellular automaton, which can be explored interactively at the following URL: https://tom-favereau.github.io/misc/ca.html. The source code for the automaton is also available on GitHub at: https://github.com/tom-favereau/twin_prime_automaton.
# 6 Conclusion and Future Work

In this paper, we have established the precise complexity of determining sensitivity to initial conditions for cellular automata within the arithmetical hierarchy. Specifically, we have shown that this problem is $Π_2^0$-complete for one-dimensional cellular automata and $Σ_3^0$-complete for cellular automata of dimension two and higher. These results provide a complete characterization of the complexity of the sensitivity problem across all dimensions.

Additionally, we have provided a new proof of Sutner's result stating that the problem of determining finite nilpotency for one-dimensional cellular automata is $Π_2^0$-complete. We have also constructed a cellular automaton that is sensitive to initial conditions if and only if the twin prime conjecture is true.

As a corollary to our main results, we can conclude that the problem of determining non-sensitivity is $Σ_2^0$-complete for one-dimensional cellular automata and $Π_3^0$-complete for higher dimensions. This complementary result completes our analysis of Kůrka's classes.

However, it is important to note that our reductions are not reversible. Consequently, the complexity of the sensitivity problem for reversible cellular automata remains an open question. This presents an interesting avenue for future research, as reversible cellular automata form an important subclass with unique properties and applications.

Furthermore, our work does not address the case of expansive cellular automata, which constitute the final class in Kůrka's classification. For expansive cellular automata, we know they are at the level $Σ_1^0$ of the arithmetical hierarchy, yet the question of the decidability or undecidability of the problem is a well-known open problem in the field. This gap in our understanding presents another significant direction for future investigations.

Additionally, the complexity of determining the existence of equicontinuity points in cellular automata remains unknown, and it is possible that it might be analytical. This presents another important direction for future research, as having equicontinuity points can be seen as a two-dimensional Kůrka class.

*Question 1.* What is the complexity of determining whether a $d$-dimensional reversible cellular automaton is sensitive to initial conditions?

*Question 2.* What is the complexity of determining the existence of equicontinuity points for a $d$-dimensional cellular automaton?

*Question 3.* What is the complexity of determining whether a $d$-dimensional cellular automaton is expansive?

In conclusion, while our results provide a comprehensive complexity analysis for the sensitivity problem for general cellular automata, they also highlight important open questions and future directions.
References

1. Durand, B., Formenti, E., Varouchas, G.: On undecidability of equicontinuity classification for cellular automata. Discrete Mathematics & Theoretical Computer Science *DMTCS Proceedings* vol. AB, Discrete Models for Complex Systems (DMCS'03), 2 (Jan 2003). https://doi.org/10.46298/dmtcs.2302, https://dmtcs.episciences.org/2302

2. Kůrka, P.: Languages, equicontinuity and attractors in cellular automata. Ergodic Theory and Dynamical Systems **17**(2), 417–433 (Apr 1997). https://doi.org/10.1017/S014338579706985X

3. Lukkarila, V.: On Undecidable Dynamical Properties of Reversible One-Dimensional Cellular Automata. Ph.D. thesis, University of Turku (2010)

4. Rogers, H.: Theory of recursive functions and effective computability. MIT Press, Cambridge, MA, USA (1987)

5. Sablik, M., Theyssier, G.: Topological dynamics of cellular automata: Dimension matters. Theory Comput Syst **48**(4), 693–714 (2011). https://doi.org/10.1007/s00224-010-9255-x, https://doi.org/10.1007/s00224-010-9255-x

6. Sutner, K.: A note on Culik-Yu classes. Complex Systems **3**(1), 107–115 (1989)

7. Wolfram, S.: Statistical mechanics of cellular automata. Rev. Mod. Phys. **55**, 601–644 (Jul 1983). https://doi.org/10.1103/RevModPhys.55.601, https://link.aps.org/doi/10.1103/RevModPhys.55.601