The ergodic theory of cellular automata

Abstract

Ergodic theory is the study of how a dynamical system transforms the information encoded in an invariant probability measure. This article reviews the major recent results in the ergodic theory of cellular automata.

Keywords:

• cellular automata
• ergodic theory
• invariant measure
• rigidity
• entropy

Notes

1. Many of the results in this paper hold when M is any amenable group (even nonabelian). But for simplicity, we will confine attention to the case .

2. In fact, if A^M is given a natural metric structure, then topological entropy is closely related to the box-counting dimension of X.

3. See Shereshevsky and Afraĭmovich (1992/93, Theorem 1) or Kleveland (1997, Corollary 7.3) or Fagnani and Margara (1998, Theorem 3.2).

4. Here, , where is as defined above. Meanwhile, h(ν, Ψ) is defined in Section 4 below.

5. The natural extension of the MPDS (A ^M, μ, Φ) is defined as follows. First, define . That is, a point in consists of a point in along with any possible infinite ‘Φ-history’ of a ₀. Now define by . Then v;[vtilde] is invertible and the original system (A^M,Φ) is a factor of the system via the projection . If Φ is actually invertible, then this map is actually an isomorphism between (A^M, Φ) and . Otherwise, provides a way to ‘convert’ a noninvertible system (A^M,Φ) into an invertible one. For any measurable B ⊂ A^M, and for all T ∈ ℕ, we define . Let be the sigma-algebra on generated by all such sets, and let be the measure defined by for any B ∈ B and T ∈ ℕ. Then the MPDS is the natural extension of the MPDS .

6. There is also a version of this result when (X, ν, Ψ) is not invertible.

7. For the case on A^Z, see Maass (1996, Theorem 4.9). For the case on A^ℕ, see Blanchard and Maass (1997, Corollary 3.10) or Maass (1996, Theorem 4.8(5)).

8. Actually, Willson only proved the case D = 2 and A = Z_/2, but his proof technique easily generalizes to any extremally permutative CA on any alphabet, and any D ≥ 1. (Also, Willson concludes Φ is ‘ergodic’, but he actually proves that Φ is mixing.)

9. Special cases of this result were earlier proved by Miyamoto (1979), Lind (1984), Cai and Luo (1993), Maass and Martínez (1998), Ferrari, Maass, Martínez and Ney (2000) and Pivato and Yassawi (2002).