# Classification of Elementary Cellular Automata Up to Topological Conjugacy

Jeremias Epperlein

► To cite this version:

Jeremias Epperlein. Classification of Elementary Cellular Automata Up to Topological Conjugacy. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. pp.99-112, 10.1007/978-3-662-47221-7_8. hal-01442485

HAL Id: hal-01442485

https://inria.hal.science/hal-01442485

Submitted on 20 Jan 2017

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Classification of Elementary Cellular Automata
up to Topological Conjugacy

Jeremias Epperlein

Institute for Analysis & Center for Dynamics
TU Dresden, Germany
jeremias.epperlein@tu-dresden.de

**Abstract.** Topological conjugacy is the natural notion of isomorphism in topological dynamics. It can be used as a very fine grained classification scheme for cellular automata. In this article, we investigate different invariants for topological conjugacy in order to distinguish between non-conjugate systems. In particular we show how to compute the cardinality of the set of points with minimal period $n$ for one-dimensional CA. Applying these methods to the 256 elementary one-dimensional CA, we show that up to topological conjugacy there are exactly 83 of them.

# 1 Introduction

One-dimensional cellular automata can be topologically characterized as the continuous $\sigma$-commuting endomorphisms of the space $A^Z$. Topological dynamics is therefore a natural framework to study their dynamics and has shown to be rather fruitful [6].

Topological dynamics in our sense is the study of compact metrizable space $X$ together with a continuous map $F: X \to X$. The classical notion of isomorphism in this setting is that of a *topological conjugacy*. Two topological dynamical systems $F: X \to X$ and $G: Y \to Y$ are called conjugate, if there is a homeomorphism $\varphi: X \to Y$ such that $\varphi \circ F = G \circ \varphi$ [7]. It is easily seen that this defines an equivalence relation on topological dynamical systems. A natural problem now is to classify a certain class of such systems up to conjugacy.

This problem received a lot of attention for the case of subshifts of finite type. While there has been substantial progress and some powerful invariants have been found, there still remain many questions, ranging from the question if conjugacy is decidable for SFTs, to the question of deciding conjugacy for two concretely given edge shifts [2].

The corresponding problem of classifying CA up to topological conjugacy has up to now seen very little activity, although many classification schemes for CA have been proposed (see [8] for a survey). As a starting point we will classify the elementary one-dimensional cellular automata, mainly using the cardinality of the set of points with minimal period $n$, the Cantor-Bendixson derivative of the periodic points and various ad-hoc arguments.
## 2 Definitions

Let $A$ be a finite set with $|A| \ge 2$, which we call our *alphabet*. The set of bi-infinite sequences in $A$ is denoted by $A^Z$ and set of words over $A$ is denoted by $A^*$. We endow $A^Z$ with the product topology turning it into a Cantor space. On $A^Z$ we define the shift map $\sigma$ by $\sigma(x)_k = x_{k+1}$. The dynamical system $(A^Z, \sigma)$ is called the *full shift over A*. Replacing $\mathbb{Z}$ by $\mathbb{N} = \{1, 2, \dots\}$ we get the dynamical system $(A^\mathbb{N}, \sigma)$, called the *one-sided full shift* over $A$. A *subshift* is a closed $\sigma$-invariant subset of $A^Z$. The subshift $X$ is a *subshift of finite type (SFT)* if there is a finite list of words such that $X$ consists of all configurations not containing one of these words. For further information concerning shift spaces we refer to the standard reference [7].

Denote by $\mathcal{H}_A$ the set of all homeomorphisms from $A^Z$ to itself, and denote by $\mathcal{C}A$ the set of all cellular automata (CA), that is, the set of all continuous maps $F: A^Z \to A^Z$ with $\sigma \circ F = F \circ \sigma$. By the Curtis-Lyndon-Hedlund Theorem (see [7]) for each cellular automaton there is $r \in \mathbb{N}$, called its *radius*, and a *block map* $f: A^{2r+1} \to A$ with $F(x)_i = f(x_{i-r}, \dots, x_{i+r})$. The block map also induces a map $f: A^* \to A^*$ by $f(x_1, \dots, x_\ell) = (f(x_{1,...,2r+1}), \dots, f(x_{\ell-2r,...,\ell}))$.

Let $(X, F)$ be a dynamical system. A point $x \in X$ is called *periodic with period $n \in \mathbb{N}$*, if $F^n(x) = x$. The minimal $n$, for which this equality holds is called its *minimal period*. We denote by $\text{Per}_n(F)$ the set of all $n$-periodic points with respect to $F$ and by $\widetilde{\text{Per}}_n(F)$ the set of all points with minimal period $n$. Thus $\text{Per}_n(F)$ is the disjoint union of all sets in $\{\widetilde{\text{Per}}_k(F) ; k \mid n\}$. We also write $\text{Per}(F) = \bigcup_{n \in \mathbb{N}} \text{Per}_n(F)$ for the set of all periodic points.

When counting periodic points we will encounter sets of countable cardinality and of cardinality equal to that of the continuum. We write these cardinalities with the help of the Hebrew letter $\mathbb{Z}$ (this notation is similar to the better known notion of the *cardinal numbers*), so we define $|\mathbb{N}| =: \mathbb{Z}_0$ and $|\mathbb{R}| = |2^\mathbb{N}| =: \mathbb{Z}_1$.

For us *digraphs* are tuples $\mathcal{G} = (V(\mathcal{G}), E(\mathcal{G}), t, h)$ with $V(\mathcal{G})$ and $E(\mathcal{G})$ being finite sets and $t, h: E(\mathcal{G}) \to V(\mathcal{G})$ being the *tail* resp. the *head* of an edge. Thus our edges are directed and we allow multiple edges as well as loops. A *path* $(\gamma_i)_{i \in I}$ with $I = \{1, \dots, k\}$ or $I = \mathbb{Z}$ is sequence of edges in $\mathcal{G}$ with $h(\gamma_i) = t(\gamma_{i+1})$. We denote by $\text{Path}(\mathcal{G})$ the set of all bi-infinite pathes in $\mathcal{G}$. They form a SFT contained in $E(\mathcal{G})^Z$, the *edge shift* of the graph. A *vertex path* in $\mathcal{G}$ is a sequence of vertices $(v_i)_{i \in \{1, \dots, k\}}$ such that for each $i \in \{1, \dots, k-1\}$ there is an edge $e_i \in E(\mathcal{G})$ with $t(e_i) = v_i$ and $h(e_i) = v_{i+1}$.

## 3 Topological Conjugacies

Since the composition of cellular automata gives another cellular automaton, the conjugation of a CA by an invertible one is again a cellular automaton. The simplest instance of this is conjugacy by a symbol permutation ("exchanging black and white"). Another way of getting a conjugate CA from a given one, is to reflect the rule ("exchanging left and right"). This is equivalent to conjugation by the reflection map $\tau: A^Z \to A^Z$, $\tau(x)_k := x_{-k}$. See [3] for further properties
of these conjugacies. The next theorem will show, that these are in a sense the
only general methods to get a conjugate CA from another.

**Theorem 1.** Let $\varphi: A^Z \to A^Z$ be a homeomorphism. Then the following are equivalent.

(a) $\varphi \circ CA_A \circ \varphi^{-1} \subseteq CA_A$,

(b) $\varphi \circ CA_A \circ \varphi^{-1} = CA_A$,

(c) $\exists H \in CA_A: \varphi = H \text{ or } \varphi = H \circ \tau$.

*Proof (of Theorem 1).* (c) $\Rightarrow$ (b) and (b) $\Rightarrow$ (a) are trivial.

(a) $\Rightarrow$ (c) Let $F$ be an arbitrary CA. Then $G := \varphi \circ F \circ \varphi^{-1}$ is again a CA by the assumption and therefore commutes with $\sigma$. Hence

$$G = \sigma \circ G \circ \sigma^{-1} = \sigma \circ \varphi \circ F \circ \varphi^{-1} \circ \sigma^{-1},$$

$$F = \varphi^{-1} \circ \sigma \circ \varphi \circ F \circ \varphi^{-1} \circ \sigma^{-1} \circ \varphi$$

By setting $F = \sigma$, we see that $\varphi^{-1} \circ \sigma \circ \varphi$ is a CA. Now Ryan's theorem [9] tells us that the center of the group $H_A \cap CA_A$ consists only of powers of the shift, i.e. if an invertible CA commutes with all other invertible CA, it must be a power of the shift. Hence $\varphi^{-1} \circ \sigma \circ \varphi = \sigma^k$ for some $k \in \mathbb{Z}$ or equivalently $\sigma \circ \varphi = \varphi \circ \sigma^k$. This first of all implies that $k \neq 0$. Now take any point $y \in \text{Per}_1(\sigma^k)$. Then $(\sigma \circ \varphi)(y) = (\varphi \circ \sigma^k)(y) = \varphi(y)$. Hence $\varphi(y) \in \text{Per}_1(\sigma)$ and therefore $\varphi$ defines an injective mapping from $\text{Per}_1(\sigma^k)$ into $\text{Per}_1(\sigma)$. Having a look at the cardinalities we see that $|A|^{|k|} = |\text{Per}_1(\sigma^k)| \leq |\text{Per}_1(\sigma)| = |A|$, implying $k = \pm 1$. In the case of $k = 1$ we are done. In the other case

$$\tau \circ \varphi^{-1} \circ \sigma \circ \varphi \circ \tau^{-1} = \tau \circ \sigma^{-1} \circ \tau^{-1} = \sigma,$$

hence $\varphi \circ \tau^{-1}$ is a CA.

□

In the light of Theorem 1, we call a conjugacy $\varphi \in CA \cup CA \circ \tau$ a strong conjugacy. In Section 7 we will see conjugate cellular automata, that are not strongly conjugate.

# 4 Periodic Points and the Cantor-Bendixson Derivative

Consider two conjugate cellular automata $F$ and $G := \varphi \circ F \circ \varphi^{-1}$ with $\varphi \in H_A$. The first invariant of topological conjugacy normally considered is the number of periodic points, for if $F^k(x) = x$ then $(\varphi \circ F \circ \varphi^{-1})^k(\varphi(x)) = (\varphi \circ F^k)(x) = \varphi(x)$. Hence $\varphi$ maps $\text{Per}_k(F)$ bijectively onto $\text{Per}_k(\varphi^{-1} \circ F \circ \varphi)$. While for shifts have only finitely many periodic points of a given period, this is in general not true any more for cellular automata.

To deal with this, we use standard cardinal arithmetic in order to extend the addition on $\mathbb{N}$ to $C := \mathbb{N} \cup \{\underline{2}_0, \underline{2}_1\}$ by defining

$$\underline{2}_1 + k := k + \underline{2}_1 := \underline{2}_1 \text{ for } k \in C$$

$$\underline{2}_0 + k := k + \underline{2}_0 := \underline{2}_0 \text{ for } k \in \mathbb{N} \cup \{\underline{2}_0\}.$$
This turns $\mathcal{C}$ into a commutative monoid. The justification for this definition is given by the fact, that for $A_1, \dots, A_\ell$ pairwise disjoint sets with $|A_i| \in \mathcal{C}$ we have $|\bigcup_{i=1}^\ell A_i| = \sum_{i=1}^\ell |A_i|$. Notice however, that for two disjoint sets $A, B$ with $|A|, |B| \in \mathcal{C}$ it is no longer possible to recover the cardinality of $B$ from the knowledge of $|A|$ and $|A \cup B|$.

In settings where only a finite number of periodic points can occur, one can reconstruct $\widetilde{Per}_n(F)$ from the knowledge of $(Per_k(F))_{k \le p}$ by $\widetilde{Per}_n(F) = \sum_{d|n} \mu(\frac{n}{d})Per_d(F)$, where $\mu$ is the Möbius function. This no longer works in our case where $(\widetilde{Per}_\ell(F))_{\ell \in \{1, \dots, n\}}$ carries more information than $(Per_\ell(F))_{\ell \in \{1, \dots, n\}}$. As an easy example consider a cellular automaton $F$ with $|Per_1(F)| = 2_1$. Then $|Per_k(F)| = 2_1$ for all $k \in \mathbb{N}$. Therefore we are interested in determining $(|\widetilde{Per}_\ell(F)|)_{\ell \in \{1, \dots, n\}}$, which is harder to calculate than $(|Per_\ell(F)|)_{\ell \in \{1, \dots, n\}}$, though.

While these are already nice invariants they do not use the fact that $\varphi$ is continuous at all but only its bijectivity. However, two spaces with cardinality $2_1$ might look rather different from a topological point of view. We therefore look at the set of all limit points $D(Per_n(F))$ of $Per_n(F)$ defined as follows.

**Definition 2.** Let $B \subseteq A^Z$. The set of limit points of $B$, also called its Cantor-Bendixson derivative, is defined by

$$D(B) := \{x \in A^Z ; \exists (y_n)_{n \in \mathbb{N}} \text{ in } B \setminus \{x\} : y_n \xrightarrow{n \to \infty} x\} = \bigcap_{x \in B} \overline{B \setminus \{x\}}.$$

It is well known and easy to proof that $\varphi(D(B)) = D(\varphi(B))$ for any homeomorphism $\varphi: A^Z \to A^Z$. For a subshift $(X, \sigma)$ and a subset $B \subseteq X$ we can characterize the set of limit points as follows. A configuration $(x_i)_{i \in \mathbb{Z}}$ is a limit point of $B$ if for all $k \in \mathbb{N}$ the word $x_{-k, \dots, k}$ can be extended to a configuration in $B$ different from $X$. We will use this characterization at the end of Section 5 to compute $D(Per_n(F))$.

Now we fix $n \in \mathbb{N}$ and a cellular automaton $F: A^Z \to A^Z$ with radius $r \ge 1$ and local rule $f: A^{2r+1} \to A$, and try to determine quantities $|\widetilde{Per}_n(F)|$ and $|D(Per_n(F))|$.

We define the De Bruijn graph $\mathcal{D} = (V, E, t, h)$ by

$$ \begin{align*} V &:= A^{2nr}, \\ E &:= A^{2nr+1}, \\ t(x_1, \dots, x_{2nr+1}) &:= (x_1, \dots, x_{2nr}), \\ h(x_1, \dots, x_{2nr+1}) &:= (x_2, \dots, x_{2nr+1}), \end{align*} $$

together with a homeomorphism

$$\Psi: A^Z \to \mathrm{Path}(\mathcal{D}), \Psi(x) = (x_{i-nr}, \dots, x_{i+nr})_{i \in \mathbb{Z}}.$$

Next we annotate the edges of $\mathcal{D}$ by the function $p: E(\mathcal{D}) \to \{1, \dots, n\}$ with $p(e_1, \dots, e_{2nr+1}) = \{t \in \{1, \dots, n\} ; f^t(e_1, \dots, e_{2nr+1})_{nr-tr+1} = e_{nr+1}\}$.
<figure><img src="image_2.png" /><figcaption>Fig. 1: Successive application of $f := w_{28}(x_{-1}, x_0, x_1) \mapsto x_{-1}(1 \oplus x_1 \oplus x_0 x_1) \oplus x_0$ (see Sec. 6 for notation) to $1011011$.</figcaption></figure>

A direct calculation (see Fig. 1 for an illustration) shows, that $F^\ell(x) = x$ iff $\ell \in \bigcap_{i \in \mathbb{Z}} p(\psi(x)_i)$. Now we take the subgraph of $\mathcal{D}$ containing only those edges $e$ with $n \in p(e)$ and then remove all edges not contained in any infinite path and call the result $\mathcal{G}$. By this construction $\Psi(\text{Per}_n(F)) = \text{Path}(\mathcal{G}) =: \text{Per}_n(\mathcal{G})$ and $\Psi(\widetilde{\text{Per}}_n(F)) = \{\gamma \in \text{Path}(\mathcal{G}) ; \bigcap_{i \in \mathbb{Z}} p(\gamma_i) = \{n\} \} =: \widetilde{\text{Per}}_n(\mathcal{G})$. See Fig. 2 for an example.

# 5 Computing the Invariants

In this section we show how to compute $\widetilde{\text{Per}}_n(\mathcal{G})$ and $\mathcal{D}(\text{Per}_n(\mathcal{G}))$. Let $S_G$ be the set of strongly connected components of $\mathcal{G}$, that is the maximal strongly connected subgraphs of $\mathcal{G}$. Define the strong component digraph $S_G$ (see [1]) of $G$ as the acyclic digraph with vertex set $S_G$, edge set $E(S_G) := \{(s_1, s_2) ; \exists e \in E(\mathcal{G}) : t(e) \in s_1 \text{ and } h(e) \in s_2\}$ and tail resp. head being the first resp. second entry of the edge. For each vertex $i \in V(\mathcal{G})$ there is a unique component $s(i) \in S_G$ such that $i \in V(s(i))$. Each bi-infinite path $(\gamma_i)_{i \in \mathbb{Z}}$ in $\mathcal{G}$ induces a unique finite vertex-path $s(\gamma) = (s(\gamma)_1, \dots, s(\gamma)_\ell)$ in $S_G$ (since $S_G$ is a finite acyclic digraph, it contains only finite paths) such that

$$ \{s(\gamma)_1, \dots, s(\gamma)_{\ell}\} = \{s(h(\gamma_i)) ; i \in \mathbb{Z}\}. $$

Thus $s(\gamma)$ is the path in $S_G$ traversed by the vertices on $\gamma$.

For components $s_1, \dots, s_k \in S_G$ we define $\text{Path}(s_1, \dots, s_k)$ as the set of all bi-infinite paths in $G$ that traverse the components $s_1, \dots, s_k$ in that order, i.e.

$$ \text{Path}(s_1, \dots, s_k) = \{\gamma \in \text{Path}(\mathcal{G}) ; s(\gamma) = (s_1, \dots, s_k)\} $$

We now annotate the vertices and edges of $S_G$ by three functions defined as follows (remember that the vertices of $S_G$ are subgraphs of $\mathcal{G}$).

$$ c: V(S_G) \to \mathbb{N} \cup \{\underline{2}_1\} \quad c(s) := |\text{Path}(s)| = \begin{cases} |E(s)| & \text{if } s \text{ is a directed cycle} \\ \underline{2}_1 & \text{or a single vertex} \\ \underline{2}_1 & \text{otherwise} \end{cases} $$

$$ \rho: V(S_G) \to \{1, \dots, n\} \quad \rho(s) := \bigcap \{p(e) ; e \in E(\mathcal{G}), t(e) \in V(s), h(e) \in V(s)\} $$

$$ \mathcal{P}: E(S_G) \to 2^{\{1, \dots, n\}} \quad \mathcal{P}(s_1, s_2) := \{p(e) ; e \in E(\mathcal{G}), t(e) \in V(s_1), h(e) \in V(s_2)\} $$
<figure><img src="image_3.png" /><figcaption>Fig. 2: The subgraph $\mathcal{G}$ of the De Bruijn graph for the CA $W_{28}$ generated by $w_{28}$ with $n = 2$. Its strong component digraph $S_G$ is a directed line with vertices $s_1, s_2, s_3$. The edges are labelled by $p$.</figcaption></figure>

With these annotations, we can calculate the cardinality of $\text{Path}(s_1, \dots, s_k)$ as follows:

$$ |\text{Path}(s_1, \dots, s_k)| = \begin{cases} c(s_1) & \text{if } k = 1 \\ 0 & \text{if } c(s_1) = 0 \text{ or } c(s_2) = 0 \\ \overline{z_1} & \text{if } c(s_1) \neq \emptyset, c(s_2) \neq \emptyset, \\ \exists \ell \in \{1, \dots, k\}: c(s_\ell) = \overline{z_1} \\ \overline{z_0} & \text{otherwise} \end{cases}. \quad (1) $$

Together with the following theorem this gives an algorithm for computing $|\widetilde{Per}_n(F)| = |\widetilde{Per}_n(\mathcal{G})|$.

**Theorem 3.** Let $m$ be the length of the longest vertex path in $S_G$ and let $M_k$ be the set of all vertex paths $(s_1, \dots, s_k)$ in $S_G$ with $c(s_1) \neq 0, c(s_k) \neq 0$ and $\{n\} \in \{p(s_1) \cap \dots \cap p(s_k) \cap z_1 \cap \dots \cap z_{k-1}; z_1 \in P(s_1, s_2), \dots, z_{k-1} \in P(s_{k-1}, s_k)\}$. Then $|\widetilde{Per}_n(\mathcal{G})| = \sum_{k=1}^m \sum_{(s_1, \dots, s_k) \in M_k} |\text{Path}(s_1, \dots, s_k)| \in \mathcal{C}$.

*Proof.* We first show that a vertex path $(s_1, \dots, s_k) \in S_G$ is in $M_k$ if and only if $\text{Path}(s_1, \dots, s_k) \cap \widetilde{Per}_n(\mathcal{G}) \neq \emptyset$.

Let $\gamma \in \text{Path}(s_1, \dots, s_k) \cap \widetilde{Per}_n(\mathcal{G})$. Let $\ell_1, \dots, \ell_{k-1} \in \mathbb{Z}$ be the indices where $\gamma$ goes from one strongly connected component to another, that is, $t(\gamma_{\ell_i}) \in V(s_i), h(\gamma_{\ell_{i+1}}) \in V(s_{i+1})$ for $i \in \{1, \dots, k-1\}$. Then $p(\gamma_{\ell_i}) \in P(s_i, s_{i+1})$ for $i \in \{1, \dots, k-1\}$. This implies

$$ \{n\} = \bigcap_{i \in \mathbb{Z}} p(\gamma_i) \supseteq \bigcap_{j=1}^{k-1} p(\gamma_{\ell_j}) \cap p(s_1) \cap \dots \cap p(s_k) \supseteq \{n\}, $$
and thus $(s_1, \dots, s_k) \in M_k$.

On the other hand let $(s_1, \dots, s_k) \in M_k$. There are edges $e_1, \dots, e_{k-1} \in E(\mathcal{G})$ with $t(e_i) \in V(s_i)$, $h(e_i) \in V(s_{i+1})$ and $p(s_1) \cap \dots \cap p(s_k) \cap p(e_1) \cap \dots \cap p(e_k) = \{n\}$. Let $L \subseteq \text{Path}(\mathcal{G})$ be the set of all bi-infinite paths containing all of the edges in $E(s_1) \cup \dots \cup E(s_k) \cup \{e_1, \dots, e_{k-1}\}$ and no other edges. Then $L \subseteq \text{Path}(s_1, \dots, s_k)$ and for $\gamma \in L$ we have

$$ \{n\} \subseteq \bigcap_{i \in \mathbb{Z}} p(\gamma_i) \subseteq p(s_1) \cap \dots \cap p(s_k) \cap p(e_1) \cap \dots \cap p(e_k) \subseteq \{n\}. $$

Hence $\gamma \in \widetilde{Per}_n(\mathcal{G})$ and $\emptyset \neq L \subseteq \text{Path}(s_1, \dots, s_k) \cap \widetilde{Per}(\mathcal{G})$.

The set $L$ contains $\mathbb{Z}_1$ elements iff one of the components $s_1, \dots, s_k$ is not a directed circle or a single vertex. If this is not the case and there are at least two components, then $|L| = \mathbb{Z}_0$. If $k=1$ and $s_1$ is a directed circle or a single vertex, then $L = \text{Path}(s_1, \dots, s_k)$. Therefore by (1) $|\text{Path}(s_1, \dots, s_k)| = |\text{Path}(s_1, \dots, s_k) \cap \widetilde{Per}_n(\mathcal{G})|$ for $(s_1, \dots, s_k) \in M_k$. The result follows with $|\widetilde{Per}_n(\mathcal{G})| = \sum_{k=1}^m \sum_{(s_1, \dots, s_k) \in M_k} |\text{Path}(s_1, \dots, s_k) \cap \widetilde{Per}_n(\mathcal{G})|$. $\square$

Determining the derived set of $Per_n(\mathcal{G})$ is simpler. By the definition of the topology on $E(\mathcal{G})^{\mathbb{Z}}$ we have that $\text{Path}(s_1, \dots, s_k) \neq \emptyset$ is either contained in $D(Per_n(\mathcal{G}))$ or its complement $D(Per_n(\mathcal{G}))^c$. The first case happens if and only if at least one of the following conditions is met

(i) $c(s_1) = \mathbb{Z}_1$ or $c(s_k) = \mathbb{Z}_1$,

(ii) $\exists t \in S_G$ with $(t, s_1) \in E(S_G)$ or $\exists t \in S_G$ with $(s_k, t) \in E(S_G)$.

# 6 Data for the 256 Elementary CA

Armed with the algorithm to compute the number of minimally $p$-periodic points of a CA $F$ we can now set forth and apply this to the classification of the 256 elementary CA, the CA with alphabet $\{0, 1\}$ and radius 1. We enumerate them according to their Wolfram code [10], so $W_k$ is the CA with Wolfram code $k$.

There remains one issue. All periodic points of $F$ lie in its eventual image $\omega(F) := \bigcap_{t \in \mathbb{N}} F^t(A^{\mathbb{Z}})$. If two CA are conjugate when restricted to their eventual image but differ in their transient behaviour, we have no possibility to detect this up to now. As a very simple invariant capturing some transient behaviour we therefore check

(a) if $F$ resp. $F^2$ is idempotent, that is, if $F^2 = F$ resp. $F^4 = F^2$,

(b) if $F$ is an involution, that is, if $F^2 = \text{id}$ and

(c) if $F^3 = F$.

We already know from Section 3, that we can always get an conjugate elementary CA by conjugation with the homeomorphisms of $\{0, 1\}^{\mathbb{Z}}$ induced by

$$ v: \{0, 1\} \to \{0, 1\}, \quad v(a) = 1 - a, $$

$$ \tau: \mathbb{Z} \to \mathbb{Z}, \quad \tau(k) = -k. $$
Each equivalence class of CA up to conjugation with these two homeomorphisms contains at most four elements (it contains less if e.g. $F = vFv^{-1}$). It is well known that 88 of these equivalence classes remain [8]. We represent each of them by the member with the smallest Wolfram code. For each equivalence class we compute the invariants and group them by this data. The results are shown in Table 1.

# 7 The Special Cases

We still have 10 classes of elementary cellular automata left, that we could not distinguish with the invariants considered up to now. We start with the non-trivially conjugate CA.

The following pairs of cellular automata are conjugate by

$$ \vartheta: \{0,1\}^{\mathbb{Z}} \to \{0,1\}^{\mathbb{Z}} \quad \vartheta(x)_k := \begin{cases} 1-x_k & \text{if } k \equiv 0 \pmod 2 \\ x_k & \text{if } k \equiv 1 \pmod 2 \end{cases} $$

(a) $(15, 170)$, $W_{15} = \sigma \circ \upsilon$, $W_{170} = \sigma$. Notice that $W_{15}$ and $W_{170}$ can not be strongly conjugate since any cellular automaton commutes with $\sigma$ and therefore the only other CA strongly conjugate to $\sigma$ is $\sigma^{-1}$.

(b) (77, 232),

(c) (23, 178).

Next we have the three rules 90, 105, 150 with

$$ \begin{aligned} w_{90}(x_{-1}, x_0, x_1) &= x_{-1} \oplus x_1, \\ w_{105}(x_{-1}, x_0, x_1) &= 1 \oplus x_{-1} \oplus x_0 \oplus x_1, \\ w_{150}(x_{-1}, x_0, x_1) &= x_{-1} \oplus x_0 \oplus x_1. \end{aligned} $$

These (together with their conjugates with respect to $\upsilon$) are exactly the left- and right-permutive elementary CA. Therefore by a result of Kurka and Nasu [5] they are conjugate to the one-sided full shift with alphabet $\{1, \dots, 4\}$ and in particular they are conjugate to each other.

We will show on a case by case basis, that all CA in the remaining classes are pairwise non-conjugate. For this we use two new invariants, again only using the bijectivity of the conjugation $\varphi$. Let $Fix_k(F)$ be the set of all fixed points of $F$ with $k$ preimages, that is,

$$ \mathrm{Fix}_k(F) := \{x \in \mathrm{Per}_1(F) ; |F^{-1}(x)| = k\}. $$

It is straightforward to see, that $|F^{-1}(\mathrm{Per}_1(F))|$ and $|\mathrm{Fix}_k(F)|$ both remain invariant under conjugation.

For each CA $F$ with local rule $f: \{0,1\}^3 \to \{0,1\}$ the De Bruijn graph for $n=1$ with edges annotated by $f$ is shown. A edge is drawn thickly if $f(x_{-1}x_0x_1) = x_0$, therefore the edge shift of the subgraph defined by the thick edges is $\Psi(\mathrm{Per}_1(F)) = \mathrm{Per}_1(\mathcal{G})$.
<figure><img src="image_4.png" /><figcaption>Fig. 3: De Bruijn graphs for $W_6$ and $W_{134}$</figcaption></figure>

### Rules 6 and 134

We have that

$$ egin{gathered} |W_6^{-1}(\infty 0^{\infty})| = \mathfrak{Z}_1, \qquad |W_6^{-1}(\infty (01)^{\infty})| = 1, \\ |W_6^{-1}(\infty (01).0^{\infty})| = \mathfrak{Z}_1. \end{gathered} $$

Hence $|W_6^{-1}(\mathrm{Per}_1(W_6))| = \mathfrak{Z}_1$. On the other hand

$$ egin{gathered} |W_{134}^{-1}(\infty 0^{\infty})| = \mathfrak{Z}_0, \qquad |W_{134}^{-1}(\infty 1^{\infty})| = 1, \\ |W_{134}^{-1}(\infty (01)^{\infty})| = 1, \qquad |W_{134}^{-1}(\infty (01).0^{\infty})| = \mathfrak{Z}_0, \end{gathered} $$

and thus $|W_{134}^{-1}(\mathrm{Per}_1(W_{134}))| = \mathfrak{Z}_0$. Therefore $W_{134}$ and $W_6$ are not conjugate.

### Rules 18 and 126

<figure><img src="image_5.png" /><figcaption>Fig. 4: De Bruijn graphs for $W_{18}$ and $W_{126}$</figcaption></figure>

Both of them have only one fixed point $\infty 0^{\infty}$. From the De Bruijn graphs in Fig. 4, we see that $|W_{18}^{-1}(\mathrm{Per}_1(W_{18}))| = \mathfrak{Z}_1$ and $|W_{126}^{-1}(\mathrm{Per}_1(W_{126}))| = 2$, hence these CA are not conjugate.

### Rules 36 and 72

Because of the horizontal symmetry of the annotated De Bruijn graph in Fig. 5a we see that $\mathrm{Fix}_1(W_{36}) = \emptyset$. On the other hand $\infty(011).(011)^{\infty} \in \mathrm{Fix}_1(W_{72})$.
<figure><img src="image_6.png" /><figcaption>Fig. 5: De Bruijn graphs for $W_{36}$ and $W_{72}$</figcaption></figure>

## Rules 78 and 140

From Fig. 6 we derive that $\infty 1^\infty \in \text{Fix}_1(W_{140})$, while $\text{Fix}_1(W_{78}) = \emptyset$ since $W_{78}^{-1}(\infty 0^\infty) = \{\infty 0^\infty, \infty 1^\infty\}$ and each occurrence of 01010 resp. 10110 might be replaced by 01110 resp. 10010 in fixed points of $W_{78}$ without changing the image.

<figure><img src="image_7.png" /><figcaption>Fig. 6: De Bruijn graphs for $W_{78}$ and $W_{140}$</figcaption></figure>

## Rules 2, 24 and 46

<figure><img src="image_8.png" /><figcaption>Fig. 7: De Bruijn graphs for $W_2$, $W_{24}$ and $W_{46}$</figcaption></figure>
These CA are equivalent to the shift, either $\sigma$ or $\sigma^{-1}$, on their eventual image. For $W_2$ the eventual image is reached in one time step, that is, $W_2(\{0, 1\}^Z) = \omega(W_2)$, while the same is not the case for $W_{24}$ and $W_{46}$.

Now we have a look at the sets $M_{24} := W_{24}^{-1}(\text{Per}_1(W_{24}))$ and $M_{46} := W_{46}^{-1}(\text{Per}_1(W_{46}))$. Both are countable SFTs. $M_{24}$ is generated by $\infty 0.(10)^\infty$ and $\infty 1.(01)^\infty$, while $M_{46}$ is generated by $\infty 1.0^\infty$. Therefore $M_{24}$ has four accumulation points, while $M_{46}$ has only two of them.

### Rules 4, 12, 76 and 200

<figure><img src="image_9.png" /><figcaption>Fig. 8: De Bruijn graphs for $W_4$, $W_{12}$, $W_{76}$ and $W_{200}$</figcaption></figure>

These CA are all equal to the identity on their eventual image, or more specifically $\text{Per}_1(F) = \omega(F) = F(A^Z)$ for $F \in \{W_4, W_{12}, W_{76}, W_{200}\}$. Their eventual images are all homeomorphic to the Cantor set. Notice that $\text{Per}_1(W_4) = \text{Per}_1(W_{12})$.

As a last invariant we look at the possible cardinalities of the preimage of a point and define $\text{PF}(F) := \{|F^{-1}(x)|; x \in A^Z\} \subseteq \mathcal{C}$. Let $\text{Fib}$ be the set of Fibonacci numbers, defined by $a_1 = 1, a_2 = 2, a_{k+2} = a_{k+1} + a_k$ for $k \in \mathbb{N}$. We will show that

$$ \begin{aligned} \text{PF}(W_{200}) &= \text{PF}(W_{12}) \\ &= \mathbb{Z}_1 \cup \{b_1 b_2 \dots b_k; k \in \mathbb{N}, b_i \in \text{Fib} \text{ for } i \in \{1, \dots, k\}\}. \end{aligned} $$

In the case of $W_{200}$ the ambiguity in forming the preimage comes from blocks of the form $110^k 11$, see Fig. 9b. Since isolated 1s are erased by $W_{200}$, the number of preimages of $\infty 1.0^k 1^\infty$ equals the number of words of length $k-2$ containing no two consecutive 1s, which equals $a_{k-1} \in \text{Fib}$. If more then one block of the form $110^k 11$ occurs, one can independently put isolated 1s in these blocks without changing the image, hence the number of the preimages is the product of those for the single blocks. The same is true for $W_{76}$ but here we look at blocks terminated by 11 on each side and containing only isolated 1s, e.g. $11001001010001011$. We can replace $010^k 10$ by $01^{k+2}0$ without changing the image. But since we can not do this for adjacent occurrences of $010^k 10$, again the number of preimages of $\infty 10w01^\infty$ with $w$ containing $\ell$ isolated 1s is $a_\ell$.
<figure><img src="image_10.png" /><figcaption>Fig. 9: Space-Time-Diagrams of $W_{76}$, $W_{200}$ with random initial condition and periodic boundary, black represents 0 and grey represents 1.</figcaption></figure>

On the other hand

$$W_{12}^{-1}(\infty(01).0^{\infty}) = \{\infty(01).1^k 0^{\infty}; k \in \mathbb{N}_0\} \cup \{\infty(01).1^{\infty}\},$$

so $\underline{2}_0 \in \text{PF}(W_{12})$. But $\underline{2}_0 \notin \text{PF}(W_4)$, since any point having infinitely many preimages wrt. $W_4$ must contain infinitely many occurrences of blocks of the form $10^k 1$ with $k \ge 2$ or start resp. end in $\infty 0$ resp. $0^\infty$, thus already having uncountably many predecessors. Consequently $W_{12}$ is not conjugate to any of $W_4$, $W_{76}$ and $W_{200}$.

This leaves us with these three cellular automata. Next we look at $W_4^{-1}(x)$ for

$$x = \infty(01).\underline{000000}(10)^{\infty}).$$

Each element of this set has to coincide with $x$ everywhere except for the underlined block of four consecutive zeros. In this block we only have to ensure that no isolated 1s occur. So we have to determine the number of 0, 1 blocks of length 4 where ones only occur in blocks of length at least two. Therefore there can be only either zero or one block of ones, of length from 2 to 4. This gives $1+3+2+1=7$ possibilities. But 7 is not a product of Fibonacci numbers, hence $W_4$ is not conjugate to either $W_{76}$ or $W_{200}$.

Finally we differentiate between these two CA. Notice that $\text{Fix}_3(W_{200})$ consists of all configuration in $\text{Per}_1(W_{200})$ containing the block 11000011 but no other block of zeros of length greater then two. Hence the closure of $\text{Fix}_3(W_{200})$ is contained in $\text{Fix}_3(W_{200}) \cup \text{Fix}_1(W_{200})$. On the other hand we have $(\infty 0.10^\infty) \in \text{Fix}_3(W_{76})$, hence there is $(x_n)_{n \in \mathbb{N}}$ in $\text{Fix}_3(W_{76})$ with $x_n \to \infty 0^\infty \in \text{Fix}_2(W_{76})$. With that we have finally shown that $W_{200}$ and $W_{76}$ are not topologically conjugate.

Notice however, that $|\text{Fix}_k(W_{76})| = |\text{Fix}_k(W_{200})|$ for all $k \in \mathcal{C}$. Therefore $W_{76}$ and $W_{200}$ are conjugate when $\{0, 1\}^\mathbb{Z}$ is endowed with the discrete topology.

# 8 Conclusion

We showed that there are exactly 83 equivalence classes of topologically conjugate elementary CA. Among them we saw examples of pairs of CA that are

(a) conjugate, but not strongly conjugate, e.g. $W_{170} = \sigma$ and $W_{15} = \sigma \circ \nu$,

(b) not conjugate, but conjugate if one neglects the topology, e.g. $W_{200}$ and $W_{76}$,

(c) not conjugate, but conjugate when restricted to their eventual image, e.g. $W_4$ and $W_{12}$.
Our main tool in differentiating non-conjugate CA was the number of mini-
mally *n*-periodic points. In higher dimensions this is in general not computable,
as already being able to decide if |Per₁(F)| = 0 is equivalent to deciding the
tiling problem. Therefore it would be interesting how far one can get in deciding
conjugacy of higher-dimensional CA with small radius and alphabet size.

A cellular automaton is nilpotent, iff restricted to its eventual image it is
conjugate to the dynamical system whose state space consists of a single point.
This implies that all nilpotent CA are conjugate when restricted to their even-
tual image. Nilpotency is undecidable already in dimension one [4]. Hence it is
undecidable if two CA are topological conjugacy when restricted to their even-
tual image. But this does not immediately imply that topological conjugacy is
undecidable. Therefore we finish with the following conjecture.

*Conjecture 4.* Topological conjugacy of one-dimensional cellular automata is un-
decidable.

References

1. Bang-Jensen, J., Gutin, G.Z.: Digraphs: Theory, Algorithms and Applications. Springer, 2nd edn. (2008)

2. Boyle, M.: Open problems in symbolic dynamics. In: Geometric and Probabilistic Structures in Dynamics, March 15-18, 2008, University of Maryland, College Park, MD. vol. 469, p. 69. American Mathematical Soc. (2008)

3. Cattaneo, G., Formenti, E., Margara, L., Mauri, G.: Transformations of the one-dimensional cellular automata rule space. Parallel Computing 23(11), 1593-1611 (1997)

4. Kari, J.: The Nilpotency Problem of One-Dimensional Cellular Automata. SIAM Journal on Computing 21(3), 571–586 (1992)

5. Kůrka, P.: Topological and symbolic dynamics, vol. 11. Société Mathématique de France (2003)

6. Kůrka, P.: Topological dynamics of cellular automata. Encyclopedia of Complexity and Systems Science pp. 9246–9268 (2009)

7. Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995)

8. Martinez, G.J.: A Note on Elementary Cellular Automata Classification (Jun 2013), http://arxiv.org/abs/1306.5577

9. Ryan, J.P.: The shift and commutativity. Mathematical systems theory 6(1-2), 82–85 (1972)

10. Wolfram, S.: Statistical mechanics of cellular automata. Reviews of Modern Physics 55(3), 601–644 (1983)