Topological Dynamics of Cellular Automata

Article Outline

Glossary

Definition of the Subject

Introduction

Topological Dynamics

Symbolic Dynamics

Equicontinuity

Surjectivity

Permutive and Closing Cellular Automata

Expansive Cellular Automata

Attractors

Subshifts and Entropy

Examples

Future Directions

Acknowledgments

Bibliography

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Definition of the Subject

A topological dynamical system is a continuous selfmap ${ F\colon X \to X }$ of a topological space X. Topological dynamics studies iterations ${ F^n\colon X \to X }$, or trajectories ${ (F^n(x))_{n\geq 0} }$. Basic questions are how trajectories depend on initial conditions, whether they are dense in the state space X, whether they have limits, or what are their accumulation points. While cellular automata were introduced in the late 1940s by Neumann [36] as regular infinite networks of finite automata, topological dynamics of cellular automata began in 1969 with Hedlund [19] who viewed one‐dimensional cellular automata in the context of symbolic dynamics as endomorphisms of the shift dynamical systems. In fact, the term “cellular automaton” never appears in his paper. Hedlund's main results are the characterizations of surjective and open cellular automata. In the early 1980s Wolfram [41] produced space-time representations of one‐dimensional cellular automata and classified them informally into four classes using dynamical concepts like periodicity, stability and chaos. Wolfram's classification stimulated mathematical research involving all the concepts of topological and measure‐theoretical dynamics, and several formal classifications were introduced using dynamical concepts.

There are two well-understood classes of cellular automata with remarkably different stability properties. Equicontinuous cellular automata settle into a fixed or periodic configuration depending on the initial condition and cannot be perturbed by fluctuations. This is a paradigm of stability. Positively expansive cellular automata, on the other hand, are conjugated (isomorphic) to one-sided full shifts. They have dense orbits, dense periodic configurations, positive topological entropy, and sensitive dependence on the initial conditions. This is a paradigm of chaotic behavior. Between these two extreme classes there are many distinct types of dynamical behavior which are understood much less. Only some specific classes or particular examples have been elucidated and a general theory is still lacking.

Introduction

Dynamical properties of CA are usually studied in the context of symbolic dynamics. Other possibilities are measurable dynamics (see Pivato Ergodic Theory of Cellular Automata) or non-compact dynamics in Besicovitch or Weyl spaces (see Formenti and Kůrka Dynamics of Cellular Automata in Non-compact Spaces). In symbolic dynamics, the state space is the Cantor space of symbolic sequences. The Cantor space has distinguished topological properties which simplify some concepts of dynamics. This is the case of attractor and topological entropy. Cellular automata can be defined in the context of symbolic dynamics as continuous mappings which commute with the shift map.

Equicontinuous and almost equicontinuous CA can be characterized using the concept of blocking words. While equicontinuous CA are eventually periodic, closely related almost equicontinuous automata, are periodic on a large (residual) subset of the state space. Outside of this subset, however, their behavior can be arbitrarily complex.

A property which strongly constrains the dynamics of cellular automata is surjectivity. Surjective automata preserve the uniform Bernoulli measure, they are bounded-to-one, and their unique subshift attractor is the full space. An important subclass of surjective CA are (left- or right-) closing automata. They have dense sets of periodic configurations. Cellular automata which are both left- and right‐closing are open: They map open sets to open sets, are n‑to-one and have cross-sections. A fairly well-understood class is that of positively expansive automata.A positively expansive cellular automaton is conjugated (isomorphic) to a one-sided full shift. Closely related are bijective expansive automata which are conjugated to two-sided subshifts, usually of finite type.

Another important concept elucidating the dynamics of CA is that of an attractor. With respect to attractors, CA classify into two basic classes. In one class there are CA which have disjoint attractors. They have then countably infinite numbers of attractors and uncountable numbers of quasi‐attractors i. e., countable intersections of attractors. In the other class there are CA that have either a minimal attractor or a minimal quasi‐attractor which is then contained in any attractor. An important class of attractors are subshift attractors—subsets which are both attractors and subshifts. They have always non-empty intersection, so they form a lattice with maximal element.

Factors of CA that are subshifts are useful because factor maps preserve many dynamical properties while they simplify the dynamics. In a special case of column subshifts, they are formed by sequences of words occurring in a column of a space-time diagram. Factor subshifts are instrumental in evaluating the entropy of CA and in characterizing CA with the shadowing property.

A finer classification of CA is provided by quantitative characteristics. Topological entropy measures the quantity of information available to an observer who can see a finite part of a configuration. Lyapunov exponents measure the speed of information propagation. The minimum preimage number provides a finer classification of surjective cellular automata. Sets of left- and right‐expansivity directions provide finer classification for left- and right‐closing cellular automata.

Topological Dynamics

We review basic concepts of topological dynamics as exposed in Kůrka [24]. A Cantor space is any metric space which is compact (any sequence has a convergent subsequence), totally disconnected (distinct points are separated by disjoint clopen, i. e., closed and open sets), and perfect (no point is isolated). Any two Cantor spaces are homeomorphic. A symbolic space is any compact, totally disconnected metric space, i. e., any closed subspace of a Cantor space. A  symbolic dynamical system (SDS) is a pair ${ (X,F) }$ where X is a symbolic space and ${ F\colon X \to X }$ is a continuous map. The nth iteration of F is denoted by F ⁿ.If F is bijective (invertible), the negative iterations are defined by ${ F^{-n}=(F^{-1})^n }$. A set ${ Y \subseteq X }$ is invariant, if ${ F(Y) \subseteq Y }$ and strongly invariant if ${ F(Y) = Y }$.

A homomorphism ${ \varphi \colon (X,F) \to (Y,G) }$ of SDS is a continuous map ${ \varphi \colon X \to Y }$ such that ${ \varphi\circ F = G \circ \varphi }$. A conjugacy is a bijective homomorphism. The systems ${ (X,F) }$ and ${ (Y,G) }$ are conjugated, if there exists a conjugacy between them. If φ is surjective, we say that ${ (Y,G) }$ is a factor of ${ (X,F) }$. If φ is injective, ${ (X,F) }$ is a subsystem of ${ (Y,G) }$. In this case ${ \varphi(X) \subseteq Y }$ is a closed invariant set. Conversely, if ${ Y\subseteq X }$ is a closed invariant set, then ${ (Y,F) }$ is a subsystem of ${ (X,F) }$.

We denote by ${ d \colon X \times X \to [0,\infty) }$ the metric and by ${ B_{\delta}(x) = \{y\in X \colon d(y,x) < \delta\} }$ the ball with center x and radius δ. A finite sequence ${ (x_i \in X)_{0\leq i \leq n} }$ is a δ‑chain from x ₀ to x _n , if ${ d(F(x_i),x_{i+1})<\delta }$ for all ${ i<n }$. A point ${ x\in X }$ ε-shadows a sequence ${ (x_i)_{0\leq i \leq n} }$, if ${ d(F^i(x),x_i)<\varepsilon }$ for all ${ 0\leq i \leq n }$. A SDS ${ (X,F) }$ has the shadowing property , if for every ${ \varepsilon > 0 }$ there exists ${ \delta > 0 }$, such that every δ‑chain is ε-shadowed by some point.

Definition 1

Let ${ (X,F) }$ be a SDS. The orbit relation ${ \mathcal{O}_F }$, the recurrence relation ${ \mathcal{R}_F }$, the non-wandering relation ${ \mathcal{N}_F }$, and the chain relation ${ \mathcal{C}_F }$ are defined by

$$ \begin{aligned} (x,y) \in \mathcal{O}_F &\Longleftrightarrow \exists n > 0, y=F^n(x)\\ (x,y) \in \mathcal{R}_F &\Longleftrightarrow \forall \varepsilon > 0, \exists n > 0, d(y,F^n(x))<\varepsilon\\ (x,y) \in \mathcal{N}_F &\Longleftrightarrow \forall \varepsilon,\delta > 0, \exists n > 0, \exists z\in B_{\delta}(x),\\ &\qquad\qquad\qquad\qquad\qquad d(F^n(z),y)<\varepsilon\\ (x,y) \in \mathcal{C}_F &\Longleftrightarrow \forall \varepsilon > 0,\exists \varepsilon\, - \text{ chain from } x \text{ to } y\:. \end{aligned} $$

We have $\mathcal{O}_F \subseteq \mathcal{R}_F \subseteq \mathcal{N}_F \subseteq \mathcal{C}_F$.The diagonal of a relation $S \subseteq X\times X$ is $|S| :=\{x\in X \colon (x,x)\in S\}$. We denote by $S(x):=\{y\in X \colon (x,y)\in S\}$ the S‑image of a point $x\in X$. The orbit of a point $x\in X$ is $\mathcal{O}_F(x) := \{F^n(x) \colon n > 0\}$. It is an invariant set, so its closure $(\overline{\mathcal{O}_F(x)}, F)$ is a subsystem of $(X,F)$. A point $x \in X$ is periodic with period $n > 0$, if $F^n(x) = x$, i. e., if $x \in |\mathcal{O}_F|$. A point $x \in X$ is eventually periodic, if $F^m(x)$ is periodic for some preperiod $m \geq 0$. The points in $|\mathcal{R}_F|$ are called recurrent, the points in $|\mathcal{N}_F|$ are called non-wandering and the points in $|\mathcal{C}_F|$ are called chain‐recurrent. The sets $|\mathcal{N}_F|$ and $|\mathcal{C}_F|$ are closed and invariant, so $(|\mathcal{N}_F|,F)$ and $(|\mathcal{C}_F|,F)$ are subsystems of $(X,F)$. The set of transitive points is $\mathcal{T}_F := \{x\in X\colon \overline{\mathcal{O}(x)} = X\}$. A system $(X,F)$ is minimal, if $\mathcal{R}_F = X \times X$. This happens if each point has a dense orbit, i. e., if $\mathcal{T}_F=X$. A system is transitive , if $\mathcal{N}_F = X \times X$, i. e., if for any non-empty open sets $U,V \subseteq X$ there exists $n > 0$ such that $F^n(U) \cap V \neq \emptyset$. A system is transitive if it has a transitive point, i. e., if $\mathcal{T}_F \neq \emptyset$. In this case the set of transitive points $\mathcal{T}_F$ is residual, i. e., it contains a countable intersection of dense open sets. An infinite system is chaotic, if it is transitive and has a dense set of periodic points. A system $(X,F)$ is weakly mixing, if $(X\times X,F\times F)$ is transitive. It is strongly transitive, if $(X,F^n)$ is transitive for any $n > 0$. A system $(X,F)$ is mixing , if for every non-empty open sets $U,V \subseteq X$, $F^n(U) \cap V \neq \emptyset$ for all sufficiently large n. A system is chain‐transitive, if $\mathcal{C}_F = X \times X$, and chain‐mixing, if for any $x,y\in X$ and any $\varepsilon > 0$ there exist chains from x to y of arbitrary, large enough length. If a system $(X,F)$ has the shadowing property, then $\mathcal{N}_F = \mathcal{C}_F$. It follows that a chain‐transitive system with the shadowing property is transitive, and a chain‐mixing system with the shadowing property is mixing.

A clopen partition of a symbolic space X is a finite system of disjoint clopen sets whose union is X. The join of clopen partitions $\mathcal U$ and $\mathcal V$ is $\mathcal U \vee \mathcal V = \{U \cap V : U\in \mathcal U, V\in \mathcal V\}$. The inverse image of a clopen partition $\mathcal U$ by F is $F^{-1}(\mathcal U) = \{F^{-1}(U) : U\in \mathcal U\}$. The entropy $H(X,F,\mathcal U)$ of a partition and the entropy $\mathbf{h}(X,F)$ of a system are defined by

$$ \begin{aligned} &H(X,F,\mathcal U) \\[-1ex] &\quad =\lim_{n\to\infty} \frac{\ln |\mathcal U \vee F^{-1}(\mathcal U) \vee \cdots \vee F^{-(n-1)}(\mathcal U)|}{n}\:,\\ &\mathbf{h}(X,F) \\[-1ex] &\quad =\sup \{H(X,F,\mathcal U) \colon \mathcal U \;\text{is a clopen partition of}\; X\}\:.\end{aligned} $$

Symbolic Dynamics

An alphabet is any finite set with at least two elements. The cardinality of a finite set A is denoted by ${ |A| }$. We frequently use alphabet ${ \textbf{2}=\{0,1\} }$ and more generally $\textbf{n} = \{0, \dots,n-1\}$. A word over A is any finite sequence $u = u_0 \dots u_{n-1}$ of elements of A. The length of u is denoted by ${ |u|:=n }$ and the word of zero length is denoted by λ. The set of all words of length n is denoted by A ⁿ. The set of all non-zero words and the set of all words are

$$ A^+ = \bigcup_{n > 0} A^n,\;\; A^* = \bigcup_{n\geq 0} A^n\: .$$

We denote by ℤ the set of integers, by ℕ the set of non-negative integers, by ${ \mathbb{N}^+ }$ the set of positive integers, by ℚ the set of rational numbers, and by ℝ the set of real numbers. The set of one-sided configurations (infinite words) is ${ A^{\mathbb{N}} }$ and the set of two-sided configurations (biinfinite words) is ${ A^{\mathbb{Z}} }$. If u is a finite or infinite word and ${ I = [i,j] }$ is an interval of integers on which u is defined, put ${ u_{[i,j]} = u_i \dots u_j }$. Similarly for open or half-open intervals ${ u_{[i,j)} = u_{i} \dots u_{j-1} }$. We say that v is a subword of u and write ${ v \sqsubseteq u }$, if ${ v = u_I }$ for some interval ${ I \subseteq \mathbb{Z} }$. If ${ u \in A^n }$, then ${ u^{\infty} \in A^{\mathbb{Z}} }$ is the infinite repetition of u defined by ${ (u^{\infty})_{kn+i} = u_i }$. Similarly ${ x=u^{\infty}.v^{\infty} }$ is the configuration satisfying ${ x_{i+k|u|} = u_i }$ for ${ k<0 }$, ${ 0\leq i<|u| }$ and ${ x_{i+k|v|} = v_i }$ for ${ k\geq 0 }$, ${ 0\leq i<|v| }$.On ${ A^{\mathbb{N}} }$ and ${ A^{\mathbb{Z}} }$ we have metrics

$$ \begin{aligned} &d(x,y) = 2^{-n} \\ &\qquad\text{where } n = \min\{i \geq 0 : x_i \neq y_i \},\;\; x,y \in A^{\mathbb{N}} \\ &d(x,y) = 2^{-n} \\ &\qquad\text{where } n = \min \{i\geq 0 : x_i \neq y_i \;{or}\; x_{-i} \neq y_{-i} \},\\[-1.5mm] &\qquad x,y \in A^{\mathbb{Z}}\:.\end{aligned} $$

Both ${ A^{\mathbb{N}} }$ and ${ A^{\mathbb{Z}} }$ are Cantor spaces. In ${ A^{\mathbb{N}} }$ and ${ A^{\mathbb{Z}} }$ the cylinder sets of a word ${ u \in A^n }$ are $[u] := \{x \in A^{\mathbb{N}}\colon x_{[0,n)} = u \}$, and $[u]_k := \{x \in A^{\mathbb{Z}} : x_{[k,k+n)} = u \}$, where $k \in \mathbb{Z}$. Cylinder sets are clopen and every clopen set is a finite union of cylinders. The shift maps $\sigma \colon A^{\mathbb{N}} \to A^{\mathbb{N}}$ and $\sigma \colon A^{\mathbb{Z}} \to A^{\mathbb{Z}}$ defined by $\sigma(x)_i = x_{i+1}$ are continuous. While the two-sided shift is bijective, the one-sided shift is not: every configuration has ${ |A| }$ preimages. A  one-sided subshift is any non-empty closed set $\Sigma \subseteq A^{\mathbb{N}}$ which is shift‐invariant, i. e., $\sigma(\Sigma) \subseteq \Sigma$. A two-sided subshift is any non-empty closed set $\Sigma \subseteq A^{\mathbb{Z}}$ which is strongly shift‐invariant, i. e., $\sigma(\Sigma) = \Sigma$.Thus, a subshift Σ represents a SDS ${ (\Sigma,\sigma) }$. Systems $(A^{\mathbb{Z}},\sigma)$ and $(A^{\mathbb{N}},\sigma)$ are called full shifts. Given a set $D\subseteq A^*$ of forbidden words, the set $\mathcal S_D :=\{x\in A^{\mathbb{N}} : \forall u\in D,u\not\sqsubseteq x\}$ is a one-sided subshift, provided it is non-empty. Any one-sided subshift has this form. Similarly, $\mathcal S_D :=\{x\in A^{\mathbb{Z}} : \forall u\in D,u\not\sqsubseteq x\}$ is a two-sided subshift, and any two-sided subshift has this form. A (one- or two-sided) subshift is of finite type (SFT), if the set D of forbidden words is finite. The language of a subshift Σ is the set of all subwords of configurations of Σ,

$$ \begin{aligned} \mathcal L^n(\Sigma) &= \{u \in A^n : \exists x \in \Sigma, u \sqsubseteq x \},\\ \mathcal L(\Sigma) &= \bigcup_{n\geq 0} \mathcal L^n(\Sigma) = \{u \in A^* : \exists x \in \Sigma, u\sqsubseteq x \}\:. \end{aligned} $$

The entropy of a subshift Σ is $\mathbf{h}(\Sigma,\sigma) = \lim_{n\to\infty} \ln |\mathcal L^n(\Sigma)|/n$. A word $w \in \mathcal L(\Sigma)$ is intrinsically synchronizing , if for any $u,v\in A^*$ such that $uw, wv\in \mathcal L(\Sigma)$ we have $uwv \in \mathcal L(\Sigma)$. A subshift is of finite type if all sufficiently long words are intrinsically synchronizing (see Lind and Marcus [29]).

A subshift Σ is sofic , if ${ \mathcal L(\Sigma) }$ is a regular language, i. e., if $\Sigma=\Sigma_{\mathcal G}$ is the set of labels of paths of a  labelled graph $\mathcal G=(V,E,s,t,l)$, where V is a finite set of vertices, E is a finite set of edges, $s,t: E \to V$ are the source and target map, and ${ l \colon E \to A }$ is a labelling function. The labelling function extends to a function $\ell \colon E^{\mathbb{Z}} \to A^{\mathbb{Z}}$ defined by $\ell(x)_i = l(x_i)$. A graph $\mathcal G=(V,E,s,t,l)$ determines a SFT $\Sigma_{|\mathcal G|} = \{u\in E^{\mathbb{Z}}, \forall i\in \mathbb{Z}, t(u_i) = s(u_{i+1})\}$ and $\Sigma_{\mathcal G} = \{\ell(u) : u\in \Sigma_{|\mathcal G|}\}$ so that $\ell \colon (\Sigma_{|\mathcal G|},\sigma) \to (\Sigma_{\mathcal G},\sigma)$ is a factor map. If $\Sigma=\Sigma_{\mathcal G}$, we say that ${ \mathcal G }$ is a presentation of Σ. A graph ${ \mathcal G }$ is right‐resolving, if different outgoing edges of a vertex are labelled differently, i. e., if $l(e)\neq l(e^{\prime})$ whenever $e\neq e^{\prime}$ and $s(e)=s(e^{\prime})$. A word w is synchronizing in ${ \mathcal G }$, if all paths with label w have the same target, i. e., if $t(u)=t(u^{\prime})$ whenever $\ell(u)=\ell(u^{\prime})=w$. If w is synchronizing in ${ \mathcal G }$, then w is intrinsically synchronizing in ${ \Sigma_{\mathcal G} }$. Any transitive sofic subshift Σ has a unique minimal right‐resolving presentation ${ \mathcal G }$ which has the smallest number of vertices. Any word can be extended to a word which is synchronizing in ${ \mathcal G }$ (see Lind and Marcus [29]).

A  deterministic finite automaton (DFA) over an alphabet A is a system $\mathcal A=(Q,\delta,q_0,q_1)$, where Q is a finite set of states, $\delta \colon Q\times A \to Q$ is a transition function and $q_0,q_1$ are the initial and rejecting states. The transition function extends to $\delta \colon Q \times A^* \to Q$ by $\delta(q,\lambda)=q$, $\delta(q,ua) = \delta(\delta(q,u),a)$. The language accepted by ${ \mathcal A }$ is $\mathcal L(\mathcal A) := \{u\in A^* \colon \delta(q_0,u)\neq q_1\}$ (see e. g., Hopcroft and Ullmann [20]). The DFA of a labelled graph $\mathcal G=(V,E,s,t,l)$ is $\mathcal A(\mathcal G) = (\mathcal P(V),\delta,V,\emptyset)$, where ${ \mathcal P(V) }$ is the set of all subsets of V and $\delta(q,a) = \{v\in V \colon \exists u\in q, u\stackrel{a}{\to} v \}$. Then $\mathcal L(\mathcal A(\mathcal G)) = \mathcal L(\Sigma_G)$. We can reduce the size of ${ \mathcal A(\mathcal G) }$ by taking only those states that are accessible from the initial state V.

A  periodic structure ${ \mathbf{n}=(n_i)_{i\geq 0} }$ is a sequence of integers greater than 1. For a given periodic structure n, let ${ X_{\mathbf{n}} := \prod_{i\geq 0} \{0, \dots,n_i-1\} }$ be the product space with metric ${ d(x,y) = 2^{-n} }$ where ${ n =\min\{i\geq 0 : x_i\neq y_i\} }$. Then ${ X_{\mathbf{n}} }$ is a Cantor space. The adding machine (odometer) of n is a SDS ${ (X_{\mathbf{n}},F) }$ given by the formula

$$ F(x)_i = \begin{cases} (x_i+1) \text{ mod } n_i &\text{ if } \forall j<i, x_j=n_j-1 \\ x_i &\text{ if }\ \exists j<i, x_j<n_j-1\:. \end{cases} $$

Each adding machine is minimal and has zero topological entropy.

Definition 2

A map ${ F\colon A^{\mathbb{Z}} \to A^{\mathbb{Z}} }$ is a  cellular automaton (CA) if there exist integers ${ m\leq a }$ (memory and anticipation) and a  local rule ${ f \colon A^{a-m+1} \to A }$ such that for any ${ x\in A^{\mathbb{Z}} }$ and any ${ i\in \mathbb{Z} }$, ${ F(x)_i = f(x_{[i+m,i+a]}) }$. Call $r = \max\{|m|,|a|\} \geq 0$ the radius of F and $d=a-m\geq 0$ its diameter.

By a theorem of Hedlund [19], a map $F\colon A^{\mathbb{Z}} \to A^{\mathbb{Z}}$ is a cellular automaton if it is continuous and commutes with the shift, i. e., $\sigma \circ F = F \circ \sigma$. This means that $F\colon (A^{\mathbb{Z}},\sigma) \to (A^{\mathbb{Z}},\sigma)$ is a homomorphism of the full shift and $(A^{\mathbb{Z}},F)$ is a SDS. We can assume that the local rule acts on a symmetric neighborhood of 0, so $F(x)_i = f(x_{[i-r,i+r]})$, where $f \colon A^{2r+1} \to A$. There is a trade-off between the radius and the size of the alphabet. Any CA is conjugated to a CA with radius 1. Any σ‑periodic configuration of a CA $(A^{\mathbb{Z}},F)$ is F‑eventually periodic. Hence the set of F‑eventually periodic configurations is dense. Thus, a cellular automaton is never minimal, because it has always an F‑periodic configuration. A configuration $x\in A^{\mathbb{Z}}$ is weakly periodic , if there exists $p\in \mathbb{Z}$ and $q\in \mathbb{N}^+$ such that $F^q\sigma^p(x)=x$. A configuration $x\in A^{\mathbb{Z}}$ is jointly periodic , if it is both F‑periodic and σ‑periodic. A CA $(A^{\mathbb{Z}},F)$ is nilpotent, if $F^n(A^{\mathbb{Z}})$ is a singleton for some ${ n > 0 }$.

Equicontinuity

Figure 1

A blocking word

A point ${ x \in X }$ of a SDS ${ (X,F) }$ is equicontinuous , if

$$ \forall \varepsilon > 0, \exists \delta > 0, \forall y \in B_{\delta}(x),\forall n\geq 0,\\ d(F^n(y),F^n(x)) < \varepsilon\: .$$

The set of equicontinuous points is denoted by ${ \mathcal{E}_F }$. A system is equicontinuous, if ${ \mathcal{E}_F=X }$. In this case it is uniformly equicontinuous, i. e.,

$$ \forall \varepsilon > 0,\exists \delta > 0, \forall x,y \in X, (d(x,y)< \delta\enskip \\\Rightarrow\enskip \forall n\geq 0, d(F^n(x),F^n(y)) < \varepsilon)\: . $$

A system ${ (X,F) }$ is almost equicontinuous, if ${ \mathcal{E}_F\neq \emptyset }$. A system is sensitive , if

$$ \exists \varepsilon > 0, \forall x \in X,\forall \delta > 0, \exists y \in B_{\delta}(x),\exists n\geq 0,\\ d(F^n(y),F^n(x)) \geq \varepsilon\: .$$

Clearly, a sensitive system has no equicontinuous points. The converse is not true in general but holds for transitive systems (Akin et al. [2]).

Definition 3

A word ${ u \in A^+ }$ with ${ |u|\geq s\geq 0 }$ is s ‑blocking for a CA ${ (A^{\mathbb{Z}},F) }$, if there exists an offset $k \in [ 0, |u|-s]$ such that

$$ \forall x,y \in [u]_0, \forall n \geq 0, F^n(x)_{[k,k+s)} = F^n(y)_{[k,k+s)}\: .$$

Theorem 4 (Kůrka [27])

Let ${ (A^{\mathbb{Z}},F) }$ be a CA with radius ${ r\geq 0 }$. The following conditions are equivalent.

• (1) ${ (A^{\mathbb{Z}},F) }$ is not sensitive.

• (2) ${ (A^{\mathbb{Z}},F) }$ has an r‑blocking word.

• (3) ${ \mathcal{E}_F }$ is residual, i. e., a countable intersection of dense open sets.

• (4) ${ \mathcal{E}_F \neq \emptyset }$.

For a non-empty set ${ B \subseteq A^* }$ define

$$ \begin{aligned} \mathcal{T}_{\sigma}^n(B) &:= \{x\in A^{\mathbb{Z}} : (\exists j > i > n, x_{[i,j)}\in B) \\ &\qquad\qquad\qquad\quad\text{and}\ (\exists j<i<-n, x_{[j,i)}\in B)\},\\ \mathcal{T}_{\sigma}(B) & := \bigcap_{n\geq 0} \mathcal{T}_{\sigma}^n(B)\: .\end{aligned} $$

Each ${ \mathcal{T}_{\sigma}^n(B) }$ is open and dense, so the set ${ \mathcal{T}_{\sigma}(B) }$ of B ‑recurrent configurations is residual. If B is the set of r‑blocking words, then ${ \mathcal{E}_F = \mathcal{T}_{\sigma}(B) }$.

Theorem 5 (Kůrka [27])

Let ${ (A^{\mathbb{Z}},F) }$ be a CA with radius ${ r\geq 0 }$. The following conditions are equivalent.

• (1) ${ (A^{\mathbb{Z}},F) }$ is equicontinuous, i. e., ${ \mathcal{E}_F = A^{\mathbb{Z}} }$.

• (2) There exists ${ k > 0 }$ such that any ${ u \in A^k }$ is r‑blocking.

• (3) There exists a preperiod ${ q\geq 0 }$ and a period ${ p > 0 }$, such that ${ F^{q+p} = F^q }$.

In particular every CA with radius ${ r=0 }$ is equicontinuous. A configuration is equicontinuous for F if it is equicontinuous for F ⁿ, i. e., ${ \mathcal{E}_F = \mathcal{E}_{F^n} }$. This fact enables us to consider equicontinuity along rational directions ${ \alpha =\frac{p}{q} }$.

Definition 6

The sets of equicontinuous directions and almost equicontinuous directions of a CA ${ (A^{\mathbb{Z}},F) }$ are defined by

$$ \begin{aligned} \mathfrak{E}(F) &= \left\{\frac{p}{q} \colon p\in \mathbb{Z}, q\in \mathbb{N}^+, \mathcal{E}_{F^q\sigma^p} = A^{\mathbb{Z}}\right\},\\ \mathfrak{A}(F) &= \left\{\frac{p}{q} \colon p\in \mathbb{Z}, q\in \mathbb{N}^+, \mathcal{E}_{F^q\sigma^p} \neq \emptyset\right\}\: .\end{aligned} $$

Clearly, ${ \mathfrak{E}(F) \subseteq \mathfrak{A}(F) }$, and both sets ${ \mathfrak{E}(F) }$ and ${ \mathfrak{A}(F) }$ are convex (Sablik [37]): If ${ \alpha_0<\alpha_1 <\alpha_2 }$ and ${ \alpha_0, \alpha_2\in \mathfrak{A}(F) }$, then ${ \alpha_1 \in \mathfrak{A}(F) }$. Sablik [37] considers also equicontinuity along irrational directions.

Proposition 7

Let ${ (A^{\mathbb{Z}},F) }$ be an equicontinuous CA such that there exists ${ 0 \neq \alpha \in \mathfrak{A}(F) }$. Then ${ (A^{\mathbb{Z}},F) }$ is nilpotent.

Proof

We can assume ${ \alpha<0 }$. There exist ${ 0 \leq k<m }$ and ${ w\in A^m }$, such that for all ${ x,y \in A^{\mathbb{Z}} }$ and for all ${ i\in \mathbb{Z} }$ we have

$$ \begin{aligned} &x_{[i,i+m)} = y_{[i,i+m)}\enskip \\&\qquad\Longrightarrow\enskip \forall n\geq 0, F^n(x)_{i+k} = F^n(y)_{i+k},\\ &w = x_{[i,i+m)} = y_{[i,i+m)}\enskip\\ &\qquad \Longrightarrow\enskip\forall n\geq 0, F^n\sigma^{\lfloor n\alpha \rfloor}(x)_{i+k} = F^n\sigma^{\lfloor n\alpha \rfloor}(y)_{i+k}\: .\end{aligned} $$

Take n such that $l:=\lfloor n\alpha\rfloor +m \leq 0$. There exists ${ a\in A }$ such that $F^n\sigma^{\lfloor n\alpha \rfloor}(z)_k = a$ for every $z\in [w]_0$. Let $x\in A^{\mathbb{Z}}$ be arbitrary. For a given $i\in \mathbb{Z}$, take a configuration $y \in [x_{[i,i+m)}]_i \cap [w]_{i-l+m}$. Then $z:= \sigma^{i-\lfloor n\alpha \rfloor}(y) = \sigma^{i-l+m}(y)\in [w]_0$ and $F^n(x)_{i+k} = F^n(y)_{i+k} = F^n\sigma^{\lfloor n\alpha \rfloor}(z)_k = a$. Thus, $F^n(x) = a^{\infty}$ for every $x\in A^{\mathbb{Z}}$, and $F^{n+t}(x) = F^n(F^t(x)) = a^{\infty}$ for every ${ t\geq 0 }$, so $(A^{\mathbb{Z}},F)$ is nilpotent (see also Sablik [38]).□

Theorem 8

Let ${ (A^{\mathbb{Z}},F) }$ be a CA with memory m and anticipation a, i. e., ${ F(x)_i = f(x_{[i+m,i+a]}) }$. Then exactly one of the following conditions is satisfied.

• (1) ${ \mathfrak{E}(F)= \mathfrak{A}(F) = \mathbb{Q} }$. This happens if ${ (A^{\mathbb{Z}},F) }$ is nilpotent.

• (2) ${ \mathfrak{E}(F)=\emptyset }$ and there exist real numbers ${ \alpha_0 < \alpha_1 }$ such that

  $$ (\alpha_0,\alpha_1) \subseteq \mathfrak{A}(F) \subseteq [\alpha_0,\alpha_1] \subseteq [-a,-m]\: . $$

• (3) There exists ${ -a \leq \alpha \leq -m }$ such that $\mathfrak{A}(F) = \mathfrak{E}(F) = \{\alpha\}$.

• (4) There exists ${ -a \leq \alpha \leq -m }$ such that ${ \mathfrak{A}(F) = \{\alpha\} }$ and ${ \mathfrak{E}(F) = \emptyset }$.

• (5) ${ \mathfrak{A}(F) = \mathfrak{E}(F) = \emptyset }$.

This follows from Theorems II.2 and II.5 in Sablik [37] and from Proposition 7. The zero CA of Example 1 belongs to class (1). The product CA of Example 4 belongs to class (2). The identity CA of Example 2 belongs to class (3). The Coven CA of Example 18 belongs to class (4). The sum CA of Example 11 belongs to class (5).

Sensitivity can be expressed quantitatively by Lyapunov exponents which measure the speed of information propagation. Let ${ (A^{\mathbb{Z}},F) }$ be a CA. The left and right perturbation sets of ${ x\in A^{\mathbb{Z}} }$ are

$$ \begin{aligned} W_s^-(x) &= \{y\in A^{\mathbb{Z}} : \forall i\leq s, y_i=x_i\}\:,\\[1.5mm] W_s^+(x) &= \{y\in A^{\mathbb{Z}} : \forall i\geq s, y_i=x_i\}\:.\end{aligned} $$

The left and right perturbation speeds of ${ x\in A^{\mathbb{Z}} }$ are

$$ \begin{aligned} &I_n^-(x) \\ &\quad=\min\{s\geq 0 : \forall i\leq n, F^i(W_s^-(x)) \subseteq W_0^-(F^i(x))\}\:,\\ &I_n^+(x)\\ &\quad= \min\{s\geq 0 : \forall i\leq n, F^i(W_{-s}^+(x)) \subseteq W_0^+(F^i(x))\}\:.\end{aligned} $$

Figure 2

Perturbation speeds

Thus, ${ I_n^-(x) }$ is the minimum distance of a perturbation of the left part of x which cannot reach the zero site by time n. Both ${ I_n^-(x) }$ and ${ I_n^+(x) }$ are non-decreasing. If ${ 0<s<t }$, and if ${ x_{[s,t]} }$ is an r‑blocking word (where r is the radius), then ${ \lim_{n\to\infty} I_n^-(x)\leq t }$. Similarly, if ${ s<t<0 }$ and if ${ x_{[s,t]} }$ is an r‑blocking word, then ${ \lim_{n\to\infty} I_n^+(x)\leq |s| }$. In particular, if ${ x\in \mathcal{E}_F }$, then both ${ I_n^-(x) }$ and ${ I_n^+(x) }$ have finite limit. If ${ (A^{\mathbb{Z}},F) }$ is sensitive, then ${ \lim_{n\to\infty} (I_n^-(x)+I_n^+(x)) = \infty }$ for every ${ x\in A^{\mathbb{Z}} }$.

Definition 9

The left and right Lyapunov exponents of a CA ${ (A^{\mathbb{Z}},F) }$ and ${ x\in A^{\mathbb{Z}} }$ are

$$ \lambda_F^-(x) = \liminf_{n\to\infty} \frac{I_n^-(x)}{n}\:,\quad \lambda_F^+(x) = \liminf_{n\to\infty} \frac{I_n^+(x)}{n}\: .$$

If F has memory m and anticipation a, then $\lambda_F^-(x) \leq \max\{a,0\}$ and $\lambda_F^+(x) \leq \max\{-m,0\}$ for all $x\in A^{\mathbb{Z}}$. If $x\in \mathcal{E}_F$, then $\lambda_F^+(x)=\lambda_F^-(x)=0$. If F is right‐permutive (see Sect. “Permutive and Closing Cellular Automata”) with ${ a > 0 }$, then ${ \lambda_F^-(x) = a }$ for every $x\in A^{\mathbb{Z}}$. If F is left‐permutive with ${ m<0 }$, then ${ \lambda_F^+(x) = -m }$ for every ${ x\in A^{\mathbb{Z}} }$.

Theorem 10 (Bressaud and Tisseur [9])

For a positively expansive CA (see Sect. “Expansive Cellular Automata”) there exists a constant ${ c > 0 }$, such that for all ${ x\in A^{\mathbb{Z}} }$, ${ \lambda^-(x)\geq c }$ and ${ \lambda^+(x)\geq c }$.

Conjecture 11 (Bressaud and Tisseur [9])

Any sensitive CA has a configuration x such that ${ \lambda^-(x) > 0 }$ or ${ \lambda^+(x) > 0 }$.

Surjectivity

Let ${ (A^{\mathbb{Z}},F) }$ be a CA with diameter ${ d \geq 0 }$ and a local rule ${ f \colon A^{d+1} \to A }$. We extend the local rule to a function ${ f \colon A^* \to A^* }$ by ${ f(u)_i = f(u_{[i,i+d]}) }$ for ${ i < |u| - d }$, so ${ |f(u)| = \max\{|u|-d,0\} }$. A  diamond for f (Fig. 3 left) consists of words ${ u,v \in A^{d} }$ and distinct ${ w,z \in A^+ }$ of the same length, such that ${ f(uwv) = f(uzw) }$.

Theorem 12 (Hedlund [19], Moothathu [33])

Let $(A^{\mathbb{Z}}, F)$ be a CA with local rule ${ f \colon A^{d+1} \to A }$. The following conditions are equivalent.

• (1) ${ F\colon A^{\mathbb{Z}} \to A^{\mathbb{Z}} }$ is surjective.

• (2) For each ${ x\in A^{\mathbb{Z}} }$, ${ F^{-1}(x) }$ is finite or countable.

• (3) For each ${ x\in A^{\mathbb{Z}} }$, ${ F^{-1}(x) }$ is a finite set.

• (4) For each ${ x\in A^{\mathbb{Z}} }$, ${ |F^{-1}(x)|\leq |A|^d }$.

• (5) ${ f \colon A^* \to A^* }$ is surjective.

• (6) For each ${ u \in A^+ }$, ${ |f^{-1}(u)| = |A|^{d} }$.

• (7) For each ${ u \in A^+ }$ with ${ |u|\leq d\cdot\log_2|A|\cdot(2d+|A|^{2d}) }$, ${ |f^{-1}(u)| = |A|^{d} }$.

• (8) There exists no diamond for f.

It follows that any injective CA is surjective and hence bijective. Although (6) asserts equality, the inequality in (4) may be strict. Another equivalent condition states that the uniform Bernoulli measure is invariant for F. In this form, Theorem 12 has been generalized to CA on mixing SFT (see Theorem 2B.1 in Pivato Ergodic Theory of Cellular Automata).

Figure 3

A diamond (left) and a magic word (right)

Theorem 13 (Blanchard and Tisseur [5])

• (1) Any configuration of a surjective CA is non-wandering, i. e., ${ |\mathcal{N}_F| = A^{\mathbb{Z}} }$.

• (2) Any surjective almost equicontinuous CA has a dense set of F‑periodic configurations.

• (3) If ${ (A^{\mathbb{Z}},F) }$ is an equicontinuous and surjective CA, then there exists ${ p > 0 }$ such that ${ F^p = \mathrm{Id} }$. In particular, F is bijective.

Theorem 14 (Moothathu [32])

Let ${ (A^{\mathbb{Z}},F) }$ be a surjective CA.

• (1) ${ |\mathcal{R}_F| }$ is dense in ${ A^{\mathbb{Z}} }$.

• (2) F is semi‐open, i. e., F(U) has non-empty interior for any open ${ U\neq \emptyset }$.

• (3) If ${ (A^{\mathbb{Z}},F) }$ is transitive, then it is weakly mixing, and hence totally transitive and sensitive.

Conjecture 15

Every surjective CA has a dense set of F‑periodic configurations.

Proposition 16 (Acerbi et al. [1])

If every mixing CA has a dense set of F‑periodic configurations, then every surjective CA has a dense set of jointly periodic configurations.

Definition 17

Let ${ (A^{\mathbb{Z}},F) }$ be a CA with local rule ${ f \colon A^{d+1} \to A }$.

• (1) The minimum preimage number (Fig. 3 right) ${ \mathbf{p}(F) }$ is defined by

  $$ \begin{aligned} p(F,w) &= \min_{t\leq |w|} |\{u \in A^d : \exists v \in f^{-1}(w), v_{[t,t+d)} = u \}|,\\ \mathbf{p}(F) &= \min \{p(F,w) : w \in A^+\}\: .\end{aligned} $$

• (2) A word ${ w \in A^+ }$ is magic , if ${ p(F,w)=\mathbf{p}(F) }$.

Recall that ${ \mathcal{T}_{\sigma}(w) }$ is the (residual) set of configurations which contain an infinite number of occurrences of w both in ${ x_{(-\infty,0)} }$ and in ${ x_{(0,\infty)} }$.Configurations ${ x,y \in A^{\mathbb{Z}} }$ are d ‑separated, if ${ x_{[i,i+d)} \neq y_{[i,i+d)} }$ for all ${ i\in \mathbb{Z} }$.

Theorem 18 (Hedlund [19], Kitchens [23])

Let ${ (A^{\mathbb{Z}},F) }$ be a surjective CA with diameter d and minimum preimage number ${ \mathbf{p}(F) }$.

• (1) If ${ w\in A^+ }$ is a magic word, then any ${ z \in \mathcal{T}_{\sigma}(w) }$ has exactly ${ \mathbf{p}(F) }$ preimages. These preimages are pairwise d‑separated.

• (2) Any configuration ${ z \in A^{\mathbb{Z}} }$ has at least ${ \mathbf{p}(F) }$ pairwise d‑separated preimages.

• (3) If every ${ y\in A^{\mathbb{Z}} }$ has exactly ${ \mathbf{p}(F) }$ preimages, then all long enough words are magic.

Theorem 19

Let ${ (A^{\mathbb{Z}},F) }$ be a CA and ${ \Sigma \subseteq A^{\mathbb{Z}} }$ a sofic subshift. Then both ${ F(\Sigma) }$ and ${ F^{-1}(\Sigma) }$ are sofic subshifts. In particular, the first image subshift ${ F(A^{\mathbb{Z}}) }$ is sofic.

See e. g., Formenti and Kůrka [16] for a proof. The first image graph of a local rule $f \colon A^{d+1} \to A$ is $\mathcal G(f)=(A^d,A^{d+1},s,t,f)$, where $s(u) = u_{[0,d)}$ and $t(u) = u_{[1,d]}$. Then $F(A^{\mathbb{Z}}) = \Sigma_{\mathcal G(f)}$. It is algorithmically decidable whether a given CA is surjective. One decision procedure is based on the Moothathu result in Theorem 12(7). Another procedure is based on the construction of the DFA $\mathcal A(\mathcal G(f))$ (see Sect. “Symbolic Dynamics”). A CA with local rule $f \colon A^{d+1} \to A$ is surjective if the rejecting state ∅ cannot be reached from the initial state A ^d in $\mathcal A(\mathcal G(f))$. See Morita Reversible Cellular Automata for further information on bijective CA.

Permutive and Closing Cellular Automata

Definition 20

Let ${ (A^{\mathbb{Z}},F) }$ be a CA, and let ${ f \colon A^{d+1} \to A }$ be the local rule for F with smallest diameter.

• (1) F is left‐permutive if $\forall u\in A^d, \forall b\in A, \exists ! a\in A, f(au) = b$.

• (2) F is right‐permutive if $\forall u\in A^d, \forall b\in A, \exists ! a\in A, f(ua) = b$.

• (3) F is permutive if it is either left‐permutive or right‐permutive.

• (4) F is bipermutive if it is both left- and right‐permutive.

Permutive CA can be seen in Examples 8, 10, 11, 18.

Definition 21

Let ${ (A^{\mathbb{Z}},F) }$ be a CA.

• (1) Configurations $x,y \in A^{\mathbb{Z}}$ are left‐asymptotic, if $\exists n, x_{(-\infty,n)} = y_{(-\infty,n)}$.

• (2) Configurations ${ x,y \in A^{\mathbb{Z}} }$ are right‐asymptotic, if $\exists n, x_{(n,\infty)} = y_{(n,\infty)}$.

• (3) ${ (A^{\mathbb{Z}},F) }$ is right‐closing if ${ F(x)\neq F(y) }$ for any left‐asymptotic ${ x\neq y \in A^{\mathbb{Z}} }$.

• (4) ${ (A^{\mathbb{Z}},F) }$ is left‐closing if ${ F(x)\neq F(y) }$ for any right‐asymptotic ${ x\neq y \in A^{\mathbb{Z}} }$.

• (5) A CA is closing if it is either left- or right‐closing.

Proposition 22

• (1) Any right‐permutive CA is right‐closing.

• (2) Any right‐closing CA is surjective.

• (3) A CA $(A^{\mathbb{Z}},F)$ is right‐closing if there exists $m > 0$ such that for any $x,y\in A^{\mathbb{Z}}$, $x_{[-m,0)} = y_{[ -m, 0)} \text{and}\ F(x)_{[-m,m]} = F(y)_{[-m,m]} \;\Longrightarrow\; x_0 = y_0$ (see Fig. 4 left).

See e. g., Kůrka [24] for a proof. The proposition holds with obvious modification for left‐permutive and left‐closing CA. The multiplication CA from Example 14 is both left- and right‐closing but neither left‐permutive nor right‐permutive. The CA from Example 15 is surjective but not closing.

Figure 4

Closingness

Proposition 23

Let ${ (A^{\mathbb{Z}},F) }$ be a right‐closing CA. For all sufficiently large ${ m > 0 }$, if ${ u \in A^{m} }$, ${ v \in A^{2m} }$, and if ${ F([u]_{-m}) \cap [v]_{-m} \neq \emptyset }$, then (Fig.4 right)

$$ \forall b \in A, \exists ! a \in A, F([ua]_{-m}) \cap [vb]_{-m} \neq \emptyset\: .$$

See e. g., Kůrka [24] for a proof.

Theorem 24 (Boyle and Kitchens [6])

Any closing CA ${ (A^{\mathbb{Z}},F) }$ has a dense set of jointly periodic configurations.

Theorem 25 (Coven, Pivato and Yassawi [14])

Let F be a left‐permutive CA with memory 0.

• (1) If ${ \mathcal{O}(x) }$ is infinite and ${ x_{[0,\infty)} }$ is fixed, i. e., if ${ F(x)_{[0,\infty)} = x_{[0,\infty)} }$, then ${ (\overline{\mathcal{O}(x)},F) }$ is conjugated to an adding machine.

• (2) If F is not bijective, then the set of configurations such that ${ (\overline{\mathcal{O}(x)},F) }$ is conjugated to an adding machine is dense.

A SDS ${ (X,F) }$ is open , if F(U) is open for any open ${ U \subseteq X }$. A  cross section of a SDS ${ (X,F) }$ is any continuous map ${ G \colon X \to X }$ such that ${ F\circ G = \mathrm{Id} }$. If F has a cross section, it is surjective. In particular, any bijective SDS has a cross section.

Theorem 26 (Hedlund [19])

Let ${ (A^{\mathbb{Z}},F) }$ be a CA. The following conditions are equivalent.

• (1) ${ (A^{\mathbb{Z}},F) }$ is open.

• (2) ${ (A^{\mathbb{Z}},F) }$ is both left- and right‐closing.

• (3) For any ${ x \in A^{\mathbb{Z}} }$, ${ |F^{-1}(x)| = \mathbf{p}(F) }$

• (4) There exist cross sections $G_1, \dots,G_{\mathbf{p}(F)} \colon A^{\mathbb{Z}} \to A^{\mathbb{Z}}$, such that for any $x \in A^{\mathbb{Z}}$, $F^{-1}(x) = \{G_1(x), \dots, G_{\mathbf{p}(F)}(x)\}$ and $G_i(x) \neq G_j(x)$ for $i \neq j$.

In general, the cross sections G _i are not CA as they need not commute with the shift. Only when ${ \mathbf{p}(F)=1 }$, i. e., when F is bijective, the inverse map ${ F^{-1} }$ is a CA. Any CA which is open and almost equicontinuous is bijective (Kůrka [24]).

Expansive Cellular Automata

Definition 27

Let ${ (A^{\mathbb{Z}},F) }$ be a CA.

• (1) F is left‐expansive, if there exists ${ \varepsilon > 0 }$ such that if ${ x_{(-\infty,0]} \neq y_{(-\infty,0]} }$, then ${ d(F^n(x),F^n(y))\geq \varepsilon }$ for some ${ n\geq 0 }$.

• (2) F is right‐expansive, if there exists ${ \varepsilon > 0 }$ such that if ${ x_{[0,\infty)} \neq y_{[0,\infty)} }$, then ${ d(F^n(x),F^n(y))\geq \varepsilon }$ for some ${ n\geq 0 }$.

• (3) F is positively expansive, if it is both left- and right‐expansive, i. e., if there exists ${ \varepsilon > 0 }$ such that for all ${ x\neq y \in A^{\mathbb{Z}} }$, ${ d(F^n(x),F^n(y)) \geq \varepsilon }$ for some ${ n > 0 }$.

Any left‐expansive or right‐expansive CA is sensitive and (by Theorem 12) surjective, because it cannot contain a diamond. A bijective CA is expansive , if

$$ \exists \varepsilon > 0, \forall x\neq y \in A^{\mathbb{Z}}, \exists n\in \mathbb{Z}, d(F^n(x),F^n(y)) \geq \varepsilon\: .$$

Proposition 28

Let ${ (A^{\mathbb{Z}},F) }$ be a CA with memory m and anticipation a.

• (1) If ${ m<0 }$ and if F is left‐permutive, then F is left‐expansive.

• (2) If ${ a > 0 }$ and if F is right‐permutive, then F is right‐expansive.

• (3) If ${ m<0<a }$ and if F is bipermutive, then F is positively expansive.

See e. g., Kůrka [24] for a proof.

Theorem 29 (Nasu [34,35])

• (1) Any positively expansive CA is conjugated to a one-sided full shift.

• (2) A bijective expansive CA with memory 0 is conjugated to a two-sided SFT.

Conjecture 30

Every bijective expansive CA is conjugated to a two-sided SFT.

Definition 31

Let ${ (A^{\mathbb{Z}},F) }$ be a CA. The left- and right-expansivity direction sets are defined by

$$ \begin{aligned} &\mathfrak{X}^-(F)\\ &\quad= \bigg\{\frac{p}{q} \colon p\in \mathbb{Z}, q\in \mathbb{N}^+,\; F^q\sigma^p \ \text{is left-expansive}\bigg\},\\ &\mathfrak{X}^+(F)\\ &\quad= \bigg\{\frac{p}{q} \colon p\in \mathbb{Z}, q\in \mathbb{N}^+,\; F^q\sigma^p \;\ \text{is right-expansive}\bigg\},\\ &\mathfrak{X}(F) = \mathfrak{X}^-(F) \cap \mathfrak{X}^+(F)\: .\end{aligned} $$

All these sets are convex and open. Moreover, ${ \mathfrak{X}^-(F) \cap \mathfrak{A}(F) = \mathfrak{X}^+(F) \cap \mathfrak{A}(F) = \emptyset }$ (Sablik [37]).

Theorem 32 (Sablik [37])

Let ${ (A^{\mathbb{Z}},F) }$ be a CA with memory m and anticipation a.

• (1) If F is left‐permutive, then ${ \mathfrak{X}^-(F) = (-\infty,-m) }$.

• (2) If F is right‐permutive, then ${ \mathfrak{X}^+(F) = (-a,\infty) }$.

• (3) If ${ \mathfrak{X}^-(F)\neq \emptyset }$ then there exists ${ \alpha \in \mathbb{R} }$ such that ${ \mathfrak{X}^-(F) = (-\infty,\alpha) \subseteq (-\infty,-m) }$.

• (4) If ${ \mathfrak{X}^+(F)\neq \emptyset }$ then there exists ${ \alpha \in \mathbb{R} }$ such that ${ \mathfrak{X}^+(F) = (\alpha,\infty) \subseteq (-a,\infty) }$.

• (5) If ${ \mathfrak{X}(F)\neq \emptyset }$ then there exists ${ \alpha_0,\alpha_1 \in \mathbb{R} }$ such that ${ \mathfrak{X}(F) = (\alpha_0,\alpha_1) \subseteq (-a,-m) }$.

Theorem 33

Let ${ (A^{\mathbb{Z}},F) }$ be a cellular automaton.

• (1) F is left‐closing if ${ \mathfrak{X}^-(F) \neq \emptyset }$.

• (2) F is right‐closing if ${ \mathfrak{X}^+(F) \neq \emptyset }$.

• (3) If ${ \mathfrak{A}(F) }$ is an interval, then F is not surjective and ${ \mathfrak{X}^-(F)=\mathfrak{X}^+(F)=\emptyset }$.

Proof

(1) The proof is the same as the following proof of (2).

(2⇐) If F is not right‐closing and ${ \varepsilon=2^{-n} }$, then there exist distinct left‐asymptotic configurations such that ${ x_{(-\infty,n]} = y_{(-\infty,n]} }$ and ${ F(x)=F(y) }$. It follows that ${ d(F^i(x),F^i(y))<\varepsilon }$ for all ${ i\geq 0 }$, so F is not right‐expansive. The same argument works for any ${ F^q\sigma^p }$, so ${ \mathfrak{X}^+(F)=\emptyset }$.

(2⇒) Let F be right‐closing, and let ${ m > 0 }$ be the constant from Proposition 23. Assume that

$$ F^n(x)_{[-m+(m+1)n,m+(m+1)n]}\\ = F^n (y)_{[-m+(m+1)n,m+(m+1)n]} $$

for all ${ n\geq 0 }$. By Proposition 23,

$$ F^{n-1}(x)_{m+(m+1)(n-1)+1}\\ = F^{n-1}(y)_{m+(m+1)(n-1)+1}\:. $$

By induction we get $x_{[-m,m+n]} = y_{[-m,m+n]}$. This holds for every ${ n > 0 }$, so $x_{[0,\infty)} = y_{[0,\infty)}$. Thus, ${ F\sigma^{m+1} }$ is right‐expansive, and therefore $\mathfrak{X}^+(F) \neq \emptyset$.

(3) If there are blocking words for two different directions, then the CA has a diamond and therefore is not surjective by Theorem 12.□

Corollary 34

Let ${ (A^{\mathbb{Z}},F) }$ be an equicontinuous CA. There are three possibilities.

• (1) If F is surjective, then ${ \mathfrak{A}(F)=\mathfrak{E}(F)=\{0\} }$, $\mathfrak{X}^-(F)=(-\infty,0)$, $\mathfrak{X}^+(F)=(0,\infty)$.

• (2) If F is neither surjective nor nilpotent, then $\mathfrak{A}(F)=\mathfrak{E}(F)=\{0\}$, $\mathfrak{X}^-(F)=\mathfrak{X}^+(F)=\emptyset$.

• (3) If F is nilpotent, then $\mathfrak{A}(F)=\mathfrak{E}(F)=\mathcal{R}$, $\mathfrak{X}^-(F)=\mathfrak{X}^+(F)=\emptyset$.

The proof follows from Proposition 7 and Theorem 13 (see also Sablik [38]). The identity CA is in class (1). The product CA of Example 3 is in class (2). The zero CA of Example 1 is in class (3).

Attractors

Let ${ (X,F) }$ be a SDS. The limit set of a clopen invariant set ${ V \subseteq X }$ is ${ \Omega_F(V) := \bigcap_{n\geq 0} F^n(V) }$. A set ${ Y \subseteq X }$ is an attractor , if there exists a non-empty clopen invariant set V such that ${ Y = \Omega_F(V) }$. We say that Y is a finite time attractor, if ${ Y=\Omega_F(V)= F^n(V) }$ for some ${ n > 0 }$ (and a clopen invariant set V). There exists always the largest attractor ${ \Omega_F := \Omega_F(X) }$. Finite time maximal attractors are also called stable limit sets in the literature. The number of attractors is at most countable. The union of two attractors is an attractor. If the intersection of two attractors is non-empty, it contains an attractor. The basin of an attractor ${ Y \subseteq X }$ is the set ${ \mathcal B(Y) = \{x\in X;\; \lim_{n\to\infty} d(F^n(x),Y) = 0 \} }$. An attractor ${ Y \subseteq X }$ is a minimal attractor, if no proper subset of Y is an attractor. An attractor is a minimal attractor if it is chain‐transitive. A periodic point ${ x \in X }$ is attracting if its orbit ${ \mathcal{O}(x) }$ is an attractor. Any attracting periodic point is equicontinuous. A quasi‐attractor is a non-empty set which is an intersection of a countable number of attractors.

Theorem 35 (Hurley [22])

• (1) If a CA has two disjoint attractors, then any attractor contains two disjoint attractors and an uncountably infinite number of quasi‐attractors.

• (2) If a CA has a minimal attractor, then it is a subshift, it is contained in any other attractor, and its basin of attraction is a dense open set.

• (3) If ${ x \in A^{\mathbb{Z}} }$ is an attracting F‑periodic configuration, then ${ \sigma(x) = x }$ and ${ F(x) = x }$.

Corollary 36

For any CA, exactly one of the following statements holds.

• (1) There exist two disjoint attractors and a continuum of quasi‐attractors.

• (2) There exists a unique quasi‐attractor. It is a subshift and it is contained in any attractor.

• (3) There exists a unique minimal attractor contained in any other attractor.

Both equicontinuity and surjectivity yield strong constraints on attractors.

Theorem 37 (Kůrka [24])

• (1) A surjective CA has either a unique attractor or a pair of disjoint attractors.

• (2) An equicontinuous CA has either two disjoint attractors or a unique attractor which is an attracting fixed configuration.

• (3) If a CA has an attracting fixed configuration which is a unique attractor, then it is equicontinuous.

We consider now subshift attractors of CA, i. e., those attractors which are subshifts. Let ${ (A^{\mathbb{Z}},F) }$ be a CA. A clopen F‑invariant set ${ U\subseteq A^{\mathbb{Z}} }$ is spreading , if there exists ${ k > 0 }$ such that ${ F^k(U) \subseteq \sigma^{-1}(U) \cap \sigma(U) }$. If U is a clopen invariant set, then ${ \Omega_F(U) }$ is a subshift iff U is spreading (Kůrka [25]). Recall that a language is recursively enumerable, if it is a domain (or a range) of a recursive function (see e. g., Hopcroft and Ullmann [20]).

Theorem 38 (Formenti and Kůrka [17])

Let ${ \Sigma \subseteq A^{\mathbb{Z}} }$ be a subshift attractor of a CA ${ (A^{\mathbb{Z}},F) }$.

• (1) ${ A^* \setminus \mathcal L(\Sigma) }$ is a recursively enumerable language.

• (2) Σ contains a jointly periodic configuration.

• (3) ${ (\Sigma,\sigma) }$ is chain‐mixing.

Theorem 39 (Formenti and Kůrka [17])

• (1) The only subshift attractor of a surjective CA is the full space.

• (2) A subshift of finite type is an attractor of a CA if it is mixing.

• (3) Given a CA ${ (A^{\mathbb{Z}},F) }$, the intersection of all subshift attractors of all ${ F^q\sigma^p }$, where ${ q\in \mathbb{N}^+ }$ and ${ p\in \mathbb{Z} }$, is a non-empty F‑invariant subshift called the small quasi‐attractor ${ \mathcal Q_F. (\mathcal Q_F,\sigma) }$ is chain‐mixing and ${ F\colon \mathcal Q_F \to \mathcal Q_F }$ is surjective.

The system of all subshift attractors of a given CA forms a lattice with join ${ \Sigma_0 \cup \Sigma_1 }$ and meet $\Sigma_0 \wedge \Sigma_1 := \Omega_F(\Sigma_0 \cap \Sigma_1)$. There exist CA with infinite number of subshift attractors (Kůrka [26]).

Proposition 40 (Di Lena [28])

The basin of a subshift attractor is a dense open set.

By a theorem of Hurd [21], if Ω _F is SFT, then it is stable, i. e., ${ \Omega_F = F^n(A^{\mathbb{Z}}) }$ for some ${ n > 0 }$. We generalize this theorem to subshift attractors.

Theorem 41

Let U be a spreading set for a CA ${ (A^{\mathbb{Z}},F) }$.

• (1) There exists a spreading set ${ W \subseteq U }$ such that ${ \Omega_F(W) = \Omega_F(U) }$ and ${ \widetilde{\Omega}_{\sigma}(W) := \bigcap_{i\in\mathbb{Z}} \sigma^i(W) }$ is a mixing subshift of finite type.

• (2) If ${ \Omega_F(W) }$ is a SFT, then ${ \Omega_F(W)= F^n(\widetilde{\Omega}_{\sigma}(W)) }$ for some ${ n\geq 0 }$.

Proof

• (1) See Formenti and Kůrka [17].

• (2) Let D be a finite set of forbidden words for ${ \Omega_F(W) }$. For each ${ u\in D }$ there exists ${ n_u > 0 }$ such that ${ u\not\in \mathcal L(F^{n_u}(\widetilde{\Omega}_{\sigma})) }$. Take ${ n:=\max\{n_u \colon u\in D\} }$.□

By Theorem 5, every equicontinuous CA has a finite time maximal attractor.

Definition 42

Let ${ \Sigma \subseteq A^{\mathbb{Z}} }$ be a mixing sofic subshift, let ${ \mathcal G=(V,E,s,t,l) }$ be its minimal right‐resolving presentation with factor map ${ \ell \colon (\Sigma_{|\mathcal G|},\sigma) \to (\Sigma,\sigma) }$.

• (1) A homogenous configuration ${ a^{\infty} \in \Sigma }$ is receptive, if there exist intrinsically synchronizing words ${ u,v\in \mathcal L(\Sigma) }$ and ${ n\in \mathbb{N} }$ such that ${ ua^mv \in \mathcal L(\Sigma) }$ for all ${ m > n }$.

• (2) Σ is almost of finite type (AFT), if ${ \ell \colon \Sigma_{|\mathcal G|} \to \Sigma }$ is one-to-one on a dense open set of ${ \Sigma_{|G|} }$.

• (3) Σ is near‐Markov, if ${ \{x\in \Sigma : |\ell^{-1}(x)| > 1\} }$ is a finite set of σ‑periodic configurations.

(3) is equivalent to the condition that ℓ is left‐closing, i. e., that ${ \ell(u)\neq\ell(v) }$ for distinct right‐asymptotic paths ${ u,v\in E^{\mathbb{Z}} }$. Each near‐Markov subshift is AFT.

Theorem 43 (Maass [30])

Let ${ \Sigma \subseteq A^{\mathbb{Z}} }$ be a mixing sofic subshift with a receptive configuration ${ a^{\infty} \in \Sigma }$.

• (1) If Σ is either SFT or AFT, then there exists a CA ${ (A^{\mathbb{Z}},F) }$ such that ${ \Sigma = \Omega_F = F(A^{\mathbb{Z}}) }$.

• (2) A near‐Markov subshift cannot be an infinite time maximal attractor of a CA.

On the other hand, a near‐Markov subshift can be a finite time maximal attractor (see Example 21). The language ${ \mathcal L(\Omega_F) }$ can have arbitrary complexity (see Culik et al. [15]). A CA with non-sofic mixing maximal attractor has been constructed in Formenti and Kůrka [17].

Definition 44

Let ${ f \colon A^{d+1} \to A }$ be a local rule of a cellular automaton. We say that a subshift ${ \Sigma \subseteq A^{\mathbb{Z}} }$ has decreasing preimages , if there exists ${ m > 0 }$ such that for each ${ u\in A^*\setminus\mathcal L(\Sigma) }$, each ${ v\in f^{-m}(u) }$ contains as a subword a word ${ w\in A^*\setminus\mathcal L(\Sigma) }$ such that ${ |w|<|u| }$.

Proposition 45 (Formenti and Kůrka [16])

If ${ (A^{\mathbb{Z}},F) }$ is a CA and ${ \Sigma\subseteq A^{\mathbb{Z}} }$ has decreasing preimages, then ${ \Omega_F \subseteq \Sigma }$.

For more information about attractor‐like objects in CA see Sect. “Invariance of Maxentropy Measures” of Pivato Ergodic Theory of Cellular Automata.

Subshifts and Entropy

Definition 46

Let ${ F\colon A^{\mathbb{Z}} \to A^{\mathbb{Z}} }$ be a cellular automaton.

• (1) Denote by ${ \mathcal{S}_{(p,q)}(F) := \{x\in A^{\mathbb{Z}} : F^q\sigma^p(x) = x \} }$ the set of all weakly periodic configurations of F with period ${ (p,q)\in \mathbb{Z} \times \mathbb{N}^+ }$.

• (2) A  signal subshift is any non-empty ${ \mathcal{S}_{(p,q)}(F) }$.

• (3) The speed subshift of F with speed ${ \alpha =\frac{p}{q}\in \mathbb{Q} }$ is ${ \displaystyle\mathcal{S}_{\alpha}(F) = \overline{\bigcup_{n > 0} \mathcal{S}_{(np,nq)}(F)} }$.

Note that both ${ \mathcal{S}_{(p,q)}(F) }$ and ${ \mathcal{S}_{\alpha}(F) }$ are closed and σ‑invariant. However, ${ \mathcal{S}_{(p,q)}(F) }$ can be empty, so it need not be a subshift.

Theorem 47

Let ${ (A^{\mathbb{Z}},F) }$ be a cellular automaton with memory m and anticipation a, so ${ F(x)_i = f(x_{[i+m,i+a]}) }$.

• (1) If ${ \mathcal{S}_{(p,q)}(F) }$ is non-empty, then it is a subshift of finite type.

• (2) If ${ \mathcal{S}_{(p,q)}(F) }$ is infinite, then ${ -a\leq p/q\leq -m }$.

• (3) If ${ p_0/q_0 < p_1/q_1 }$, then $\mathcal{S}_{(p_0,q_0)}(F) \cap \mathcal{S}_{(p_1,q_1)}(F) \subseteq \{x\in A^{\mathbb{Z}} : \sigma^p(x)=x\}$, where $p=q(p_1/q_1 - p_0/q_0)$ and $q=\textbf{lcm}(q_0,q_1)$ (the least common multiple).

• (4) ${ \mathcal{S}_{(p,q)}(F) \subseteq \mathcal{S}_{\frac{p}{q}}(F) \subseteq \Omega_F }$ and ${ \mathcal{S}_{\frac{p}{q}}(F) \neq \emptyset }$.

• (5) If ${ \mathfrak{X}(F)\neq \emptyset }$ or if ${ (A^{\mathbb{Z}},F) }$ is nilpotent, then F has no infinite signal subshifts.

Proof

(1), (2) and (3) have been proved in Formenti and Kůrka [16].

(4) Since F is bijective on each signal subshift, we get ${ \mathcal{S}_{(p,q)}(F) \subseteq \Omega_F }$, and therefore ${ \mathcal{S}_{p/q}(F) \subseteq \Omega_F }$. Since every ${ F^q\sigma^p }$ has a periodic point, we get ${ \mathcal{S}_{p/q}(F)\neq \emptyset }$.

(5) It has been proved in Kůrka  [25], that a positively expansive CA has no signal subshifts. This property is preserved when we compose F with a power of the shift map. If ${ (A^{\mathbb{Z}},F) }$ is nilpotent, then each ${ \mathcal{S}_{(p,q)}(F) }$ contains at most one element.□

The Identity CA has a unique infinite signal subshift ${ \mathcal{S}_{(0,1)}(\mathrm{Id}) = A^{\mathbb{Z}} }$. The CA of Example 17 has an infinite number of infinite signal subshifts of the same speed. A CA with infinitely many infinite signal subshifts with infinitely many speeds has been constructed in Kůrka [25]. In some cases, the maximal attractor can be constructed from signal subshifts (see Theorem 49).

Definition 48

Given an integer ${ c\geq 0 }$, the c -join ${ \Sigma_0 \stackrel{_c}{\vee} \Sigma_1 }$ of subshifts ${ \Sigma_0,\Sigma_1 \subseteq A^{\mathbb{Z}} }$ consists of all configurations ${ x\in A^{\mathbb{Z}} }$ such that either ${ x\in \Sigma_0 \cup \Sigma_1 }$, or there exist integers ${ b, a }$ such that ${ b-a\geq c }$, ${ x_{(-\infty,b)} \in \mathcal L(\Sigma_0) }$, and ${ x_{[a,\infty)} \in \mathcal L(\Sigma_1) }$.

The operation of join is associative, and the c‑join of sofic subshifts is sofic.

Theorem 49 (Formenti, Kůrka [16])

Let $(A^{\mathbb{Z}},F)$ be a CA and let $\mathcal{S}_{(p_1,q_1)}(F)$, ${ \dots }$, $\mathcal{S}_{(p_n,q_n)}(F)$ be signal subshifts with decreasing speeds, i. e., $p_i/q_i > p_j/q_j$ for $i<j$. Set $q:=\textbf{lcm}\{q_1, \dots q_n\}$ (the least common multiple). There exists $c\geq 0$ such that for $\Sigma := \mathcal{S}_{(p_1,q_1)}(F) \stackrel{_c}{\vee} \cdots \stackrel{_c}{\vee} \mathcal{S}_{(p_n,q_n)}(F)$ we have $\Sigma \subseteq F^q(\Sigma)$ and therefore $\Sigma \subseteq \Omega_F$. If moreover $F^{nq}(\Sigma)$ has decreasing preimages for some $n\geq 0$, then $F^{nq}(\Sigma) = \Omega_F$.

Definition 50

Let ${ (A^{\mathbb{Z}},F) }$ be a CA.

• (1) The k ‑column homomorphism $\varphi_k \colon (A^{\mathbb{Z}},F) \to ((A^k)^{\mathbb{N}},\sigma)$ is defined by $\varphi_k(x)_i = F^i(x)_{[0,k)}$.

• (2) The k th column subshift is $\Sigma_k(F) = \varphi_k(A^{\mathbb{Z}}) \subseteq (A^k)^{\mathbb{N}}$.

• (3) If ${ \psi \colon (A^{\mathbb{Z}},F) \to (\Sigma,\sigma) }$ is a factor map, where Σ is a one-sided subshift, we say that Σ is a  factor subshift of ${ (A^{\mathbb{Z}},F) }$.

Thus, each ${ (\Sigma_k(F),\sigma) }$ is a factor of ${ (A^{\mathbb{Z}},F) }$ and each factor subshift is a factor of some ${ \Sigma_k(F) }$. Any positively expansive CA ${ (A^{\mathbb{Z}},F) }$ with radius ${ r > 0 }$ is conjugated to ${ (\Sigma_{2r+1}(F),\sigma) }$. This is an SFT which by Theorem 29 is conjugated to a full shift.

Proposition 51 (Shereshevski and Afraimovich [39])

Let ${ (A^{\mathbb{Z}},F) }$ be a CA with negative memory and positive anticipation ${ m<0<a }$. Then ${ (A^{\mathbb{Z}},F) }$ is bipermutive if it is positively expansive and ${ \Sigma_{a-m+1}(F) = (A^{a-m+1})^{\mathbb{N}} }$ is the full shift.

Theorem 52 (Blanchard and Maass [4], Di Lena [28])

Let ${ (A^{\mathbb{Z}},F) }$ be a CA with radius r and memory m.

• (1) If ${ m\geq 0 }$ and ${ \Sigma_r(F) }$ is sofic, then any factor subshift of ${ (A^{\mathbb{Z}},F) }$ is sofic.

• (2) If ${ \Sigma_{2r+1}(F) }$ is sofic, then any factor subshift of ${ (A^{\mathbb{Z}},F) }$ is sofic.

If ${ (x_i)_{i\geq 0} }$ is a ${ 2^{-m} }$-chain in a CA ${ (A^{\mathbb{Z}},F) }$, then for all i, ${ F(x_i)_{[ -m,m]} = (x_{i+1})_{[ -m,m]} }$, so ${ u_i = (x_i)_{[ -m,m]} }$ satisfy ${ F([u_i]_{-m}) \cap [u_{i+1}]_{-m} \neq \emptyset }$. Conversely, if a sequence ${ (u_i \in A^{2m+1})_{i\geq 0} }$ satisfies this property and ${ x_i \in [u_i]_{-m} }$, then ${ (x_i)_{i\geq 0} }$ is a ${ 2^{-m} }$-chain.

Theorem 53 (Kůrka [27])

Let ${ (A^{\mathbb{Z}},F) }$ be a CA.

• (1) If ${ \Sigma_{k}(F) }$ is an SFT for any ${ k > 0 }$, then ${ (A^{\mathbb{Z}},F) }$ has the shadowing property.

• (2) If ${ (A^{\mathbb{Z}},F) }$ has the shadowing property, then any factor subshift is sofic.

Any factor subshift of the Coven CA from Example 18 is sofic, but the CA does not have the shadowing property (Blanchard and Maass [4]). A CA with shadowing property whose factor subshift is not SFT has been constructed in Kůrka  [24].

Proposition 54

Let ${ (A^{\mathbb{Z}},F) }$ be a CA.

• (1) ${ \mathbf{h}(A^{\mathbb{Z}},F) = \lim_{k\to\infty} \mathbf{h}(\Sigma_k(F),\sigma) }$.

• (2) If F has radius r, then

  $$ \mathbf{h}(A^{\mathbb{Z}},F) \leq 2 \cdot \mathbf{h}(\Sigma_r(F),\sigma)\\ \leq 2r \cdot \mathbf{h}(\Sigma_1(F),\sigma) \leq 2r \cdot \ln |A|. $$

• (3) If ${ 0\leq m\leq a }$, then ${ \mathbf{h}(A^{\mathbb{Z}},F) = \mathbf{h}(\Sigma_a(F),\sigma) }$.

See e. g., Kůrka [24] for a proof.

Conjecture 55

If ${ (A^{\mathbb{Z}},F) }$ is a CA with radius r, then ${ \mathbf{h}(A^{\mathbb{Z}},F) = \mathbf{h}(\Sigma_{2r+1}(F),\sigma) }$.

Conjecture 56 (Moothathu [32])

Any transitive CA has positive topological entropy.

Definition 57

The directional entropy of a CA ${ (A^{\mathbb{Z}},F) }$ along a rational direction ${ \alpha = p/q }$ is $\mathbf{h}_{\alpha}(A^{\mathbb{Z}}, F) := \mathbf{h}(A^{\mathbb{Z}}, F^q\sigma^p)/q$.

The definition is based on the equality $\mathbf{h}(X, F^n) = n\cdot \mathbf{h}(X,F)$ which holds for every SDS. Directional entropies along irrational directions have been introduced in Milnor [31].

Proposition 58 (Courbage and Kamiński [11], Sablik [37])

Let ${ (A^{\mathbb{Z}},F) }$ be a CA with memory m and anticipation a.

• (1) If ${ \alpha\in \mathcal{E}(F) }$, then ${ \mathbf{h}_{\alpha}(F) = 0 }$.

• (2) If ${ \alpha \in \mathfrak{X}^-(F) \cup \mathfrak{X}^+(F) }$, then ${ \mathbf{h}_{\alpha}(F) > 0 }$.

• (3) ${ \mathbf{h}_{\alpha}(F) \leq (\max(a+\alpha,0)-\min(m+\alpha,0))\cdot \ln |A| }$.

• (4) If F is bipermutive, then $\mathbf{h}_{\alpha}(F) = (\max\{a+\alpha,0\}-\min\{m+\alpha,0\})\cdot \ln|A|$.

• (5) If F is left‐permutive, and ${ \alpha<-a }$, then $\mathbf{h}_{\alpha}(F)=|m+\alpha|\cdot \ln|A|$.

• (6) If F is right‐permutive, and ${ \alpha > -m }$, then $\mathbf{h}_{\alpha}(F)=(a+\alpha)\cdot \ln|A|$.

The directional entropy is not necessarily continuous (see Smillie [40]).

Theorem 59 (Boyle and Lind [8])

The function $\alpha \mapsto \mathbf{h}_{\alpha}(A^{\mathbb{Z}},F)$ is convex and continuous on $\mathfrak{X}^-(F) \cup \mathfrak{X}^+(F)$.

Examples

Cellular automata with binary alphabet ${ \textbf{2}=\{0,1\} }$ and radius ${ r=1 }$ are called elementary (Wolfram [42]). Their local rules are coded by numbers between 0 and 255 by

$$ f(000) + 2\cdot f(001) + 4\cdot f(010) + \cdots\\ + 32\cdot f(101) + 64\cdot f(110) + 128\cdot f(111)\:. $$

Example 1 (The zero rule ECA0)

${ F(x) = 0^{\infty} }$.

The zero CA is an equicontinuous nilpotent CA. Its equicontinuity directions are ${ \mathfrak{E}(F) = \mathfrak{A}(F) = (-\infty,\infty) }$.

Example 2 (The identity rule ECA204)

${ \mathrm{Id}(x) = x }$.

The identity is an equicontinuous surjective CA which is not transitive. Every clopen set is an attractor and every configuration is a quasi‐attractor. The equicontinuity and expansivity directions are ${ \mathfrak{A}(\mathrm{Id}) = \mathfrak{E}(\mathrm{Id}) = \{0\} }$, ${ \mathfrak{X}^-(\mathrm{Id}) = (-\infty,0) }$, ${ \mathfrak{X}^+(\mathrm{Id}) = (0,\infty) }$. The directional entropy is ${ h_{\alpha}(\mathrm{Id}) = |\alpha| }$.

Example 3 (An equicontinuous rule ECA12)

$F(x)_i=(1-x_{i-1})x_i$.

$$ 000:0, \quad 001:0, \quad 010:1, \quad 011:1, \quad 100:0,\\ \quad 101:0, \quad 110:0, \quad 111:0.$$

The ECA12 is equicontinuous: the preperiod and period are ${ m=p=1 }$. The automaton has finite time maximal attractor ${ \Omega_F = F(A^{\mathbb{Z}}) = \Sigma_{\{11\}} = \mathcal{S}_{(0,1)}(F) }$ which is called the golden mean subshift.

Example 4 (A product rule ECA128)

${ F(x)_i = x_{i-1}x_ix_{i+1} }$.

The ECA128 is almost equicontinuous and 0 is a 1‑blocking word. The first column subshift is ${ \Sigma_1(F) = \mathcal S_{\{01\}} }$. Each column subshift ${ \Sigma_k(F) }$ is an SFT with zero entropy, so F has the shadowing property and zero entropy. The nth image

$$ F^n(\textbf{2}^{\mathbb{Z}}) = \{x\in \textbf{2}^{\mathbb{Z}} : \forall m \in [1,2n], 10^m1 \not\sqsubseteq x \}\: $$

is a SFT. The first image graph can be seen in Fig. 10 left. The maximal attractor $\Omega_F= \mathcal S_{\{10^n1 : n > 0\}}$ is a sofic subshift and has decreasing preimages. The only other attractor is the minimal attractor $\{0^{\infty}\} = \Omega_F([0]_0)$, which is also the minimal quasi‐attractor. The equicontinuity directions are $\mathfrak{E}(F) = \emptyset$ and $\mathfrak{A}(F) = [-1,1]$. For Lyapunov exponents we have $\lambda_F^-(0^{\infty}) = \lambda_F^+(0^{\infty}) = 0$ and $\lambda_F^-(1^{\infty}) = \lambda_F^+(1^{\infty}) = 1$. The only infinite signal subshifts are non-transitive subshifts $\mathcal{S}_{(1,1)}(F)=\mathcal S_{\{10\}}$ and $\mathcal{S}_{(-1,1)}(F)=\mathcal S_{\{01\}}$. The maximal attractor can be constructed using the join construction $\Omega_F = F(\mathcal{S}_{(1,1)}(F) \smash{\stackrel{_2}{\vee}} \mathcal{S}_{(-1,1)}(F))$ (Fig. 6).

Figure 5

ECA12

Figure 6

Signal subshifts of ECA128

Figure 7

ECA136

Example 5 (A product rule ECA136)

${ F(x)_i = x_i x_{i+1} }$.

The ECA136 is almost equicontinuous since 0 is a 1‑blocking word. As in Example 4, we have $\Omega_F = \mathcal S_{\{10^k1 : k > 0\}}$. For any $m \in \mathbb{Z}$, ${ [0]_m }$ is a clopen invariant set, which is spreading to the left but not to the right. Thus, $Y_m = \Omega_F([0]_m) = \{x \in \Omega_F \colon \forall i \leq m, x_i = 0 \}$ is an attractor but not a subshift. We have ${ Y_{m+1} \subset Y_m }$ and ${ \bigcap_{m\geq0} Y_m = \{0^{\infty}\} }$ is the unique minimal quasi‐attractor. Since ${ F^2\sigma^{-1}(x)_i = x_{i-1}x_ix_{i+1} }$ is the ECA128 which has a minimal subshift attractor ${ \{0^{\infty}\} }$, F has the small quasi‐attractor ${ \mathcal Q_F = \{0^{\infty}\} }$. The almost equicontinuity directions are ${ \mathfrak{A}(F)=[-1,0] }$.

Figure 8

A unique attractor ${ F(x)_i=x_{i+1}x_{i+2} }$

Example 6 (A unique attractor)

$(\textbf{2}^{\mathbb{Z}},F)$ where $F(x)_i = x_{i+1}x_{i+2}$.

The system is sensitive and has a unique attractor $\Omega_F = \mathcal S_{\{10^k1 : k > 0\}}$ which is not F‑transitive. If $x \in [10]_0 \cap \Omega_F(\textbf{2}^{\mathbb{Z}})$, then $x_{[0,\infty)} = 10^{\infty}$, so for any ${ n > 0 }$, $F^n(x) \not\in [11]_0$. However, $(A^{\mathbb{Z}},F)$ is chain‐transitive, so it does not have the shadowing property. The small quasi‐attractor is $\mathcal Q_F = \{0^{\infty}\}$. The topological entropy is zero. The factor subshift $\Sigma_1(F) = \{x \in \textbf{2}^{\mathbb{N}} : \forall n\geq 0, (x_{[n,n+1]} = 10 \;\Longrightarrow\; x_{[n,2n+1]} = 10^{n+1}) \}$ is not sofic (Gilman [18]).

Figure 9

The majority rule ECA232

Example 7 (The majority rule ECA232)

$F(x)_i = \lfloor (x_{i-1}+x_i+x_{i+1})/2 \rfloor$.

$$ 000:0, \quad 001:0, \quad 010:0, \quad 011:1, \quad 100:0,\\ \quad 101:1, \quad 110:1, \quad 111:1.$$

The majority rule has 2‑blocking words 00 and 11, so it is almost equicontinuous. More generally, let $E = \{u \in \textbf{2}^* : |u|\geq 2, u_0=u_1, u_{|u|-2} = u_{|u|-1}, 010 \not\sqsubseteq u, 101\not\sqsubseteq u \}$. Then for any $u \in E$ and for any $i\in \mathbb{Z}$, $[u]_i$ is a clopen invariant set, so its limit set $\Omega_F([u]_i)$ is an attractor. These attractors are not subshifts. There exists a subshift attractor given by the spreading set $U:=\textbf{2}^{\mathbb{Z}}\setminus ([010]_0 \cup [101]_0)$. We have $\Omega_F(U) = \mathcal{S}_{(0,1)}(F) = \mathcal S_{\{010,101\}}$. There are two more infinite signal subshifts $\mathcal{S}_{(-1,1)}(F) = \mathcal S_{\{001,110\}}$ and $\mathcal{S}_{(1,1)}(F) = \mathcal S_{\{011,100\}}$. The maximal attractor is $\Omega_F = \mathcal{S}_{(1,0)}(F) \cup (\mathcal{S}_{(1,1)}(F) \smash{\stackrel{_3}{\vee}} \mathcal{S}_{(-1,1)}(F)) = \mathcal S_{\{010^k1, 10^k10, 01^k01, 101^k0, : k > 1\}}$. All column subshifts are SFT, for example $\Sigma_1(F) = \mathcal S_{\{001,110\}}$ and the entropy is zero. The equicontinuity directions are $\mathfrak{E}(F)=\emptyset$, $\mathfrak{A}(F) = \{0\}$.

Figure 10

First image subshift of ECA128 (left) and ECA106 (right)

Example 8 (A right‐permutive rule ECA106)

$F(x)_{i} = (x_{i-1}x_{i}+ x_{i+1})\,\mathrm{mod}\, 2$.

$$ 000:0, \quad 001:1, \quad 010:0, \quad 011:1, \quad 100:0,\\ \quad 101:1, \quad 110:1, \quad 111:0.$$

The ECA106 is transitive (see Kůrka [24]). The first image graph is in Fig. 10 right. The minimum preimage number is ${ \mathbf{p}_F=1 }$ and the word ${ u=0101 }$ is magic. Its preimages are ${ f^{-1}(0101)=\{010101,100101,000101,111001\} }$ and for every ${ v\in f^{-1}(u) }$ we have ${ v_{[4,5]}=01 }$. This can be seen in Fig. 11 bottom left, where all paths in the first image graph with label 0101 are displayed. Accordingly, ${ (01)^{\infty} }$ has a unique preimage ${ F^{-1}((01)^{\infty}) = \{(10)^{\infty}\} }$. On the other hand ${ 0^{\infty} }$ has two preimages ${ F^{-1}(0^{\infty}) = \{0^{\infty}, 1^{\infty}\} }$ (Fig. 11 bottom right) and ${ 1^{\infty} }$ has three preimages ${ F^{-1}(1^{\infty}) = \{(011)^{\infty}, (110)^{\infty}, (101)^{\infty}\} }$. We have ${ \mathfrak{X}^-(F)=\emptyset }$ and ${ \mathfrak{X}^+(F) = (-1,\infty) }$ and there are no equicontinuity directions. For every x we have ${ \lambda_F^-(x)=1 }$. On the other hand the right Lyapunov exponents are not constant. For example, $\lambda_F^+(0^{\infty}) = 0$ while $\lambda_F^+((01)^{\infty}) = 1$. The only infinite signal subshift is the golden mean subshift ${ \mathcal{S}_{(-1,1)}(F) = \mathcal S_{\{11\}} }$.

Example 9 (The shift rule ECA170)

${ \sigma(x)_i = x_{i+1} }$.

The shift rule is bijective, expansive and transitive. It has a dense set of periodic configurations, so it is chaotic. Its only signal subshift is ${ \mathcal{S}_{(-1,1)}(\sigma) = \textbf{2}^{\mathbb{Z}} }$. The equicontinuity and expansivity directions are ${ \mathfrak{E}(\sigma) = \mathfrak{A}(\sigma) = \{-1\} }$, ${ \mathfrak{X}^-(\sigma)=(-\infty,-1) }$, ${ \mathfrak{X}^+(\sigma) = (-1,\infty) }$. For any ${ x\in \textbf{2}^{\mathbb{Z}} }$ we have ${ \lambda_{\sigma}^-(x)=0 }$, ${ \lambda_{\sigma}^+(x)=1 }$.

Figure 11

Preimages in ECA106

Figure 12

ECA102

Example 10 (A bipermutive rule ECA102)

$F(x)_i = (x_{i} + x_{i+1}) \,\mathrm{mod}\, 2$.

$$ 000:0, \quad 001:1, \quad 010:1, \quad 011:0, \quad 100:0,\\ \quad 101:1, \quad 110:1, \quad 111:0.$$

The ECA102 is bipermutive with memory 0, so it is open but not positively expansive. The expansivity directions are ${ \mathfrak{X}^-(F)=(-\infty,0) }$, ${ \mathfrak{X}^+(F) = (-1,\infty) }$, ${ \mathfrak{X}(F) = (-1,0) }$. If ${ x\in Y:= W_0^+(0^{\infty}.10^{\infty}) }$, i. e., if ${ x_0=1 }$ and ${ x_i=0 }$ for all ${ i > 0 }$, then ${ (\overline{\mathcal{O}(x)},F) = (Y,F) }$ is conjugated to the adding machine with periodic structure ${ \mathbf{n}=(2,2,2, \dots) }$. If ${ -2^n<i\leq -2^{n-1} }$, then ${ (F^m(x)_i)_{m\geq 0} }$ is periodic with period ${ 2^n }$. There are no signal subshifts. The minimum preimage number is ${ \mathbf{p}_F=2 }$ and the two cross sections ${ G_0,G_1 }$ are uniquely determined by the conditions ${ G_0(x)_0=0 }$, ${ G_1(x)_0=1 }$. The entropy is ${ \mathbf{h}(A^{\mathbb{Z}},F) = \ln 2 }$.

Example 11 (The sum rule ECA90)

$F(x)_i = (x_{i-1} + x_{i+1}) \,\mathrm{mod}\, 2$.

$$ 000:0, \quad 001:1, \quad 010:0, \quad 011:1, \quad 100:1,\\ \quad 101:0, \quad 110:1, \quad 111:0.$$

The sum rule is bipermutive with negative memory and positive anticipation. Thus it is open, positively expansive and mixing. It is conjugated to the full shift on four symbols ${ \Sigma_2(F) = \{00,01,10,11\}^{\mathbb{N}} }$. It has four cross-sections ${ G_0,G_1,G_2,G_3 }$ which are uniquely determined by the conditions ${ G_0(x)_{[0,1]} = 00 }$, ${ G_1(x)_{[0,1]} = 01 }$, ${ G_2(x)_{[0,1]} = 10 }$, and ${ G_3(x)_{[0,1]} = 11 }$. For every ${ x\in \textbf{2}^{\mathbb{Z}} }$ we have ${ \lambda_F^-(x)=\lambda_F^+(x)=1 }$. The system has no almost equicontinuous directions and ${ \mathfrak{X}^-(F)=(-\infty,1) }$, ${ \mathfrak{X}^+(F) = (-1,\infty) }$. The directional entropy is continuous and piecewise linear (Fig. 13).

Figure 13

Directional entropy of ECA90

Figure 14

The traffic rule ECA184

Example 12 (The traffic rule ECA184)

${ F(x)_i = 1 }$ if $x_{[i-1,i]} = 10$ or $x_{[i,i+1]} = 11$.

$$ 000:0 \quad 001:0 \quad 010:0 \quad 011:1 \quad 100:1\\\shoveright{\quad 101:1 \quad 110:0 \quad 111:0\:.}\\[-6.4mm]$$

The ECA184 has three infinite signal subshifts

$$ \mathcal{S}_{(1,1)}(F) = \mathcal S_{\{11\}}\cup \{1^{\infty}\},\quad \mathcal{S}_{(0,1)}(F) = \mathcal S_{\{10\}},\quad\\ \mathcal{S}_{(-1,1)}(F) = \mathcal S_{\{00\}}\cup \{0^{\infty}\} $$

and a unique F‑transitive attractor $\Omega_F = \mathcal{S}_{(1,1)}(F) \stackrel{_2}{\vee} \mathcal{S}_{(-1,1)}(F) = \mathcal S_{\{1(10)^n0 : n > 0 \}}$ which is sofic. The system has neither almost equicontinuous nor expansive directions. The directional entropy is continuous, but neither piecewise linear nor convex (Smillie [40]).

Figure 15

ECA 62 and its signal subshifts

Example 13 (ECA62)

${ F(x)_i=x_{i-1}(x_i+1) + x_ix_{i+1} }$.

$$ 000:0, \quad 001:1, \quad 010:1, \quad 011:1, \quad 100:1,\\ \quad 101:1, \quad 110:0, \quad 111:0.$$

There exists a spreading set $U = A^{\mathbb{Z}} \setminus([0^6]_2 \cup [1^7]_1 \cup \bigcup_{v\in f^{-1}(1^7)} [v]_0)$ and ${ \Omega_F(U) }$ is a subshift attractor which contains σ‑transitive infinite signal subshifts $\mathcal{S}_{(1,2)}(F)$ and $\mathcal{S}_{(0,3)}(F)$ as well as their join. It follows $\mathcal Q_F = \Omega_F(U) = F^2(\mathcal{S}_{(1,2)}(F) \stackrel{_3}{\vee} \mathcal{S}_{(0,3)}(F))$. The only other infinite signal subshifts are $\mathcal{S}_{(4,4)}(F)$ and $\mathcal{S}_{(-1,1)}(F)$ and

$$ \Omega_F = F^2(\mathcal{S}_{(4,4)}(F) \stackrel{_3}{\vee} \mathcal{S}_{(1,2)}(F) \stackrel{_3}{\vee} \mathcal{S}_{(0,3)}(F) \stackrel{_3}{\vee} \mathcal{S}_{(-1,1)}(F))\: .$$

In the space-time diagram in Fig. 15, the words 00, 111 and 010, which do not occur in the intersection ${ \mathcal{S}_{(1,2)}(F) \cap \mathcal{S}_{(0,3)}(F) = \{(110)^{\infty},(101)^{\infty}, (011)^{\infty}\} }$ are displayed in grey (Kůrka [25]).

Figure 16

The multiplication CA

Example 14 (A multiplication rule)

${ (\textbf{4}^{\mathbb{Z}},F) }$, where

$$ \begin{aligned} F(x)_{i} &= \left (2x_i + \left\lfloor \frac{x_{i+1}}{2} \right\rfloor \right) \,\mathrm{mod}\, 4\\ &= 2x_i + \left\lfloor \frac{x_{i+1}}{2} \right\rfloor - 4 \left\lfloor \frac{x_i}{2} \right\rfloor \:. \end{aligned} $$

00	01	02	03	10	11	12	13	20	21	22	23	30	31	32	33
0	0	1	1	2	2	3	3	0	0	1	1	2	2	3	3

We have

$$ \begin{aligned} F^2(x)_i &= \left(4x_i + 2\cdot \left\lfloor \frac{x_{i+1}}{2} \right\rfloor +(x_{i+1}) \,\mathrm{mod}\, 4 \right) \,\mathrm{mod}\, 2\\ &= x_{i+1} = \sigma(x)_i\:. \end{aligned} $$

Thus, the CA is a “square root” of the shift map. It is bijective and expansive, and its entropy is ${ \ln 2 }$. The system expresses multiplication by two in base four. If ${ x \in A^{\mathbb{Z}} }$ is left‐asymptotic with ${ 0^{\infty} }$, then ${ \varphi(x) = \sum_{i=-\infty}^{i=\infty} x_i 4^{-i} }$ is finite and ${ \varphi(F(x)) = 2 \varphi(x) }$.

Example 15 (A surjective rule)

${ (\textbf{4}^{\mathbb{Z}},F) }$, ${ m=0 }$, ${ a=1 }$, and the local rule is

00	11	22	33	01	02	12	21	03	10	13	30	20	23	31	32
0	0	0	0	1	1	1	1	2	2	2	2	3	3	3	3

The system is surjective but not closing. The first image automaton is in Fig. 17 top.We see that $F(\textbf{4}^{\mathbb{Z}})$ is the full shift, so F is surjective. The configuration $0^{\infty}.1^{\infty}$ has left‐asymptotic preimages $0^{\infty}.(21)^{\infty}$ and $0^{\infty}.(12)^{\infty}$, so F is not right‐closing. This configuration has also right‐asymptotic preimages $0^{\infty}.(12)^{\infty}$ and $2^{\infty}.(12)^{\infty}$, so F is not left‐closing (Fig. 17 bottom). Therefore, $\mathfrak{X}^-(F) = \mathfrak{X}^+(F) = \emptyset$.

Figure 17

Asymptotic configurations

Example 16

($\textbf{2}^\mathbb{Z} \times \textbf{2}^\mathbb{Z},\mathrm{Id} \times \sigma),i.\,e.,F(x,y)_i = (x_{i},y_{i+1}$).

The system is bijective and sensitive but not transitive. ${ \mathfrak{A}(F) = \mathfrak{E}(F)=\emptyset }$, ${ \mathfrak{X}^-(F)=(-\infty,1) }$, ${ \mathfrak{X}^+(F) = (0,\infty) }$. There are infinite signal subshifts

$$ \mathcal{S}_{(0,n)} = \textbf{2}^{\mathbb{Z}} \times |\mathcal{O}^n_{\sigma}|,\quad \mathcal{S}_{(-n,n)} = |\mathcal{O}^n_{\sigma}| \times \textbf{2}^{\mathbb{Z}} $$

where ${ |\mathcal{O}^n_{\sigma}| = \{x\in \textbf{2}^{\mathbb{Z}} : \sigma^n(x)=x\} }$, so the speed subshifts are ${ \mathcal{S}_0(F) = \mathcal{S}_{-1}(F) = A^{\mathbb{Z}} }$.

Figure 18

A bijective almost equicontinuous CA

Example 17 (A bijective CA)

${ (A^{\mathbb{Z}},F) }$, where $A = \{000,001,010,011,100\}$, and

$$ F(x,y,z)_i = (x_i, (1+x_i)y_{i+1} +x_{i-1}z_i,\\ (1+x_i)z_{i-1}+ x_{i+1}y_i) \,\mathrm{mod}\, 2\:.$$

The dynamics is conveniently described as movement of three types of particles, ${ 1 = 001 }$, ${ 2=010 }$ and ${ 4=100 }$. Letter ${ 0=000 }$ corresponds to an empty cell and ${ 3=011 }$ corresponds to a cell occupied by both ${ 1=001 }$ and ${ 2=010 }$. The particle ${ 4=100 }$ is a wall which neither moves nor changes. Particle 1 goes to the left and when it hits a wall 4, it changes to 2. Particle 2 goes to the right and when it hits a wall, it changes to 1. Clearly 4 is a 1‑blocking word, so the system is almost equicontinuous. It is bijective and its inverse is

$$ F^{-1}(x,y,z)_i = (x_i, (1+x_i)y_{i-1}+x_{i+1}z_i,\\ (1+x_i)z_{i+1} + x_{i-1}y_i) \,\mathrm{mod}\, 2\:.$$

The first column subshift is ${ \Sigma_1(F) = \{0,1,2,3\}^{\mathbb{N}} \cup \{4^{\infty}\} }$. We have infinite signal subshifts ${ \mathcal{S}_{(-1,1)}(F) = \{0,1\}^{\mathbb{Z}} }$, ${ \mathcal{S}_{(1,1)}(F)=\{0,2\}^{\mathbb{Z}} }$, ${ \mathcal{S}_{(0,1)}(F) = \{0,4\}^{\mathbb{Z}} }$. For ${ q > 0 }$ we get

$$ \mathcal{S}_{(0,q)}(F) = \{x\in A^{\mathbb{Z}} : \forall u\in \textbf{4}^*, (4u4\sqsubseteq x \Longrightarrow\\ (\exists m, 2m|u|=q) \;{or}\; u\in\{0\}^*)\}\: $$

so the speed subshift is ${ \mathcal{S}_0(F) = A^{\mathbb{Z}} }$. The equicontinuity directions are ${ \mathfrak{A}(F)=\{0\} }$, ${ \mathfrak{E}(F)=\emptyset }$. The expansivity directions are ${ \mathfrak{X}^-(F) = (-\infty,-1) }$, ${ \mathfrak{X}^+(F) = (1,\infty) }$.

Figure 19

The Coven CA

Example 18 (The Coven CA, Coven and Hedlund [13], Coven [12])

$(\textbf{2}^{\mathbb{Z}},F)$ where $F(x)_i = x_i + x_{i+1}(x_{i+2}+1) \,\mathrm{mod}\, 2$.

The CA is left‐permutive with zero memory. It is not right‐closing, since it does not have a constant number of preimages: ${ F^{-1}(0^{\infty}) = \{0^{\infty}\} }$, ${ F^{-1}(1^{\infty}) = \{(01)^{\infty},(10)^{\infty}\} }$. It is almost equicontinuous with 2‑blocking word 000 with offset 0. It is not transitive but it is chain‐transitive and its unique attractor is the full space (Blanchard and Maass [4]). While ${ \Sigma_1(F) = \textbf{2}^{\mathbb{Z}} }$, the two‐column factor subshift

$$ \Sigma_2(F) = \{10,11\}^{\mathbb{N}} \cup \{11,01\}^{\mathbb{N}} \cup \{01,00\}^{\mathbb{N}}\: $$

is sofic but not SFT and the entropy is ${ \mathbf{h}(A^{\mathbb{Z}},F) = \ln 2 }$. For any ${ a,b \in \textbf{2} }$ we have ${ f(1a1b) = 1c }$ where ${ c = a+b+1 }$ (here f is the local rule and the addition is modulo 2). Define a CA ${ (\textbf{2}^{\mathbb{Z}},G) }$ by ${ G(x)_i = (x_i + x_{i+1} + 1) \,\mathrm{mod}\, 2 }$ and a map ${ \varphi \colon \textbf{2}^{\mathbb{Z}} \to \textbf{2}^{\mathbb{Z}} }$ by ${ \varphi(x)_{2i} = 1 }$, ${ \varphi(x)_{2i+1} = x_i }$. Then ${ \varphi \colon (\textbf{2}^{\mathbb{Z}},G) \to (\textbf{2}^{\mathbb{Z}},F) }$ is an injective morphism and ${ (\textbf{2}^{\mathbb{Z}},G) }$ is a transitive subsystem of ${ (\textbf{2}^{\mathbb{Z}},F) }$. If ${ x_i=0 }$ for all ${ i > 0 }$ and ${ x_{2i}=1 }$ for all ${ i\leq 0 }$, then ${ (\overline{\mathcal{O}(x)},F) }$ is conjugated to the adding machine with periodic structure ${ \mathbf{n}=(2,2,2, \dots) }$, and ${ I_n^+((10)^{\infty}) = 2 }$. We have ${ \mathfrak{E}(F)=\emptyset }$, ${ \mathfrak{A}(F)=\{0\} }$, ${ \mathfrak{X}^-(F) = (-\infty,0) }$ and ${ \mathfrak{X}^+(F) = \emptyset }$. We have ${ \mathcal{S}_0(F) = \textbf{2}^{\mathbb{Z}} }$ and there exists an increasing sequence of non‐transitive infinite signal subshifts ${ \mathcal{S}_{(0,2^n)}(F) }$:

$$ \begin{aligned} \mathcal{S}_{(0,1)}(F) &= \mathcal S_{\{10\}} \subset \mathcal{S}_{(0,2)}(F)\\ &= \mathcal S_{\{1010,1110\}} \subset \mathcal{S}_{(0,4)}(F) \subset \cdots\:. \end{aligned} $$

Figure 20

Directional entropy of Gliders and walls

Example 19 (Gliders and Walls, Milnor [31])

The alphabet is ${ A=\{0,1,2,3\} }$, ${ F(x)_i =f(x_{[i-1,i+1]}) }$, where the local rule is

$$ x3x:3, \quad 12x:3, \quad 1x2:3, \quad x12:3, \quad 1xx:1,\\ \quad x1x:0, \quad xx2:2, \quad x2x0.$$

Directional entropy has discontinuity at ${ \alpha=0 }$ (see Fig. 20).

Figure 21

ECA132

Example 20 (Golden mean subshift attractor: ECA132)

 

$$ 000:0, \quad 001:0, \quad 010:1, \quad 011:0, \quad 100:0,\\[-1mm] \quad 101:0, \quad 110:0, \quad 111:1.$$

While the golden mean subshift $\mathcal S_{\{11\}}$ is the finite time maximal attractor of ECA12 (see Example 3), it is also an infinite time subshift attractor of ECA132. The clopen set $U:=[00]_0 \cup [01]_0 \cup[10]_0$ is spreading and $\Omega_F = \mathcal S_{\{11\}} = \mathcal{S}_{(0,1)}$. There exist infinite signal subshifts $\mathcal{S}_{(1,1)}(F) = \mathcal S_{\{10\}}$, $\mathcal{S}_{(-1,1)}(F) = \mathcal S_{\{01\}}$ and the maximal attractor is their join $\Omega_F = \mathcal{S}_{(1,1)}(F) \stackrel{_2}{\vee} \mathcal{S}_{(0,1)}(F) \stackrel{_2}{\vee} \mathcal{S}_{(-1,1)}(F) = \mathcal S_{\{11\}} \cup (\mathcal{S}_{(1,1)}(F) \stackrel{_2}{\vee} \mathcal{S}_{(-1,1)}(F))$.

Figure 22

The first image graph and the even subshift

Example 21 (A finite time sofic maximal attractor)

${ (\textbf{2}^{\mathbb{Z}},F) }$, where ${ m=-1 }$, ${ a=2 }$ and the local rule is

$$ \begin{aligned} &0000:0, \quad 0001:0, \quad 0010:0, \quad 0011:1, \quad \\[-1mm] &0100:1, \quad 0101:0, \quad 0110:1, \quad 0111:1,\\[1mm] &1000:1, \quad 1001:1, \quad 1010:0, \quad 1011:1, \quad \\[-1mm] &1100:1, \quad 1101:0, \quad 1110:0, \quad 1111:0.\end{aligned} $$

Figure 23

Logarithmic perturbation speeds

Figure 24

Sensitive system with logarithmic perturbation speeds

The system has finite time maximal attractor $\Omega_F = F(\textbf{2}^{\mathbb{Z}}) = \mathcal S_{\{01^{2n+1}0:\; n\geq 0\}}$ (Fig. 22 left). This is the even subshift whose minimal right‐resolving presentation is in Fig. 22 right. We have $E=\{a,b,c\}$, ${l(a)=l(b)=1}$, ${ l(c)=0 }$. A word is synchronizing in ${ \mathcal G }$ (and intrinsically synchronizing) if it contains 0. The factor map ℓ is right‐resolving and also left‐resolving. Thus ℓ is left‐closing and the even subshift is AFT. We have $\ell^{-1}(1^{\infty}) = \{(ab)^{\infty}, (ba)^{\infty}\}$, and $|\ell^{-1}(x)|=1$ for each $x\neq 1^{\infty}$. Thus, the even subshift is near‐Markov, and it cannot be an infinite time maximal attractor.

Example 22 (Logarithmic perturbation speeds)

${ (\textbf{4}^{\mathbb{Z}},F) }$ where ${ m=0 }$, ${ a=1 }$, and the local rule is

$$ \begin{aligned} &00:0, \quad 01:0, \quad 02:1, \quad 03:1, \quad 10:1, \quad 11:1,\\[-1mm] &12:2, \quad 13:2,\\[1mm] &20:0, \quad 21:0, \quad 22:1, \quad 23:1, \quad 30:3, \quad 31:3,\\[-1mm] &32:3, \quad 33:3\:.\end{aligned} $$

The letter 3 is a 1‑blocking word. Assume ${ x_i=3 }$ for ${ i > 0 }$ and ${ x_i\neq 3 }$ for ${ i\leq 0 }$. If ${ \varphi(x) = \sum_{i=1}^{\infty} x_{-i}\cdot 2^{i} }$ is finite, then ${ \varphi(F(x)) = \varphi(x)+1 }$. Thus, ${ (\overline{\mathcal{O}(x)},F) }$ is conjugated to the adding machine with periodic structure ${ \mathbf{n} = (2,2,2, \dots) }$, although the system is not left‐permutive. If ${ x = 0^{\infty}.3^{\infty} }$, then for any ${ i<0 }$, ${ (F^n(x)_i)_{n\geq 0} }$ has preperiod ${ -i }$ and period ${ 2^{-i} }$. For the zero configuration we have

$$ \begin{aligned} &n < 2^{s}+s \Longrightarrow F^n(W_s^-(0^{\infty})) \subseteq W_0^-(0^{\infty})\\ &2^{s-1}+s-1\leq n < 2^s + s \Longrightarrow I_n^-(0^{\infty}) = s\: \end{aligned} $$

and therefore ${\log_2 n - 1 < I_n^-(0^{\infty}) < \log_2 n + 1}$. More generally, for any $x\in \{0,1,2\}^{\mathbb{Z}}$ we have $\lim_{n\to\infty} I_n^-(x)/\log_2 n = 1$.

Example 23 (A sensitive CA with logarithmic perturbation speeds)

${ (\textbf{4}^{\mathbb{Z}},F) }$ where ${ m=0 }$, ${ a=2 }$ and the local rule is

$$ \begin{aligned} &33x:0, \quad 032:0, \quad 132:1, \quad 232:0, \quad 02x:1,\\[-1mm] &03x:1,\\[1mm] &12x:2, \quad 13x:2, \quad 20x:0, \quad 21x:0, \quad 22x:1,\\[-1mm] &23x:1\:.\end{aligned} $$

A similar system is constructed in Bressaud and Tisseur [9]. If ${ i<j }$ are consecutive sites with ${ x_i=x_j=3 }$, then ${ F^n(x)_{(i,j)} }$ acts as a counter machine whose binary value is increased by one unless ${ x_{j+1}=2 }$:

$$ \begin{aligned} B_{ij}(x) &= \sum_{k=1}^{j-i-1} x_{i+k}\cdot 2^{j-i-1-k} \\ B_{ij}(F(x)) &= B_{ij}(x) + 1 - \xi_2(x_{j+1}) - 2^{j-i-1}\cdot\: \xi_2(x_{i+1}) \end{aligned} $$

Here ${ \xi_2(2)=1 }$ and ${ \xi_2(x)=0 }$ for ${ x\neq 2 }$. If ${ x\in \{0,1,2\} }$, then ${ \lim_{n\to\infty} I^-_n(x)/\log_2(n) = 1 }$. For periodic configurations which contain 3, Lyapunov exponents are positive. We have ${ \lambda^-((30^n)^{\infty}) \approx 2^{-n} }$.

Future Directions

There are two long‐standing problems in topological dynamics of cellular automata. The first is concerned with expansivity. A positively expansive CA is conjugated to a one-sided full shift (Theorem 29). Thus, the dynamics of this class is completely understood. An analogous assertion claims that bijective expansive CA are conjugated to two-sided full shifts or at least to two-sided subshifts of finite type (Conjecture 30). Some partial results have been obtained in Nasu [35].

Another open problem is concerned with chaotic systems. A dynamical system is called chaotic, if it is topologically transitive, sensitive, and has a dense set of periodic points. Banks et al. [3] proved that topological transitivity and density of periodic points imply sensitivity, provided the state space is infinite. In the case of cellular automata, transitivity alone implies sensitivity (Codenotti and Margara [10] or a stronger result in Moothathu [32]). By Conjecture 15, every transitive CA (or even every surjective CA) has a dense set of periodic points. Partial results have been obtained by Boyle and Kitchens [6], Blanchard and Tisseur [5], and Acerbi et al. [1]. See Boyle and Lee [7] for further discussion.

Interesting open problems are concerned with topological entropy. For CA with non‐negative memory, the entropy of a CA can be obtained as the entropy of the column subshift whose width is the radius (Proposition 54). For the case of negative memory and positive anticipation, an analogous assertion would say that the entropy of the CA is the entropy of the column subshift of width ${ 2r+1 }$ (Conjecture 55). Some partial results have been obtained in Di Lena [28]. Another aspect of information flow in CA is provided by Lyapunov exponents which have many connections with both topological and measure‐theoretical entropies (see Bressaud and Tisseur [5] or Pivato Ergodic Theory of Cellular Automata). Conjecture 11 states that each sensitive CA has a configuration with a positive Lyapunov exponent.