Next: Cellular automata on circle Up: Cellular automata with almost Previous: Introduction

# Cellular automata on subshifts

Let A be a finite set and consider the space with the product topology. The set A is called the alphabet, the configuration space, and points in are called configurations. Let act on by translation: . A cellular automaton is a continuous map on such that for all . By the Curtis-Hedlund-Lyndon theorem (see e.g. [16]), there is for every cellular automaton a finite set such that only depends on .

A set is called invariant if for all . A compact invariant subset of is called a subshift. The orbit of is the set and the orbit closure of x is the closure of in . So orbit closures are subshifts. A subshift X is called minimal if for all . A probability measure on (the Borel -algebra of) or a subshift is called invariant if for all measurable G and all . A subshift is called uniquely ergodic if there exists only one invariant probability measure on it; it is called strictly ergodic if it is uniquely ergodic and minimal.

A cellular automaton maps subshifts to subshifts. Thus the image is what is called a topological factor of X. This implies that certain properties of subshifts are invariant under cellular automata. Examples are: topological transitivity (i.e., there is a dense orbit), minimality (i.e., every orbit is dense), unique ergodicity (see Proposition 3.11 in [4]), being of finite type, and primality (there is no nontrivial factor).

Remarks.
1) Prime subshifts exist [7]. If we apply a cellular automaton to a prime subshift, then every subshift in the orbit of the cellular automaton is topologically conjugated to the subshift one started with unless one reaches a fixed point consisting of a constant sequence.

2) If X is uniquely ergodic with invariant measure m and has discrete spectrum (i.e., the eigenfunctions are dense in , where m is the invariant measure), then also has discrete spectrum and is a subgroup of . The reason is that the measure theoretical factor of is isomorphic to and that the conditional expectation of an eigenfunction is again an eigenfunction.

3) A cellular automaton does not increase the topological entropy of a subshift. This observation, however, is of limited practical importance since for d=1 subshifts generically (w.r.t.\ the Hausdorff metric) have topological entropy zero [31], whereas in higher dimensions the topological entropy is `as a rule' infinite (cf. [27]). The directional topological entropy in the direction is defined as the topological entropy of (cf. [27]). Directional topological entropy does not increase either.

4) The fact that cellular automata leave classes of subshifts invariant was our motivation to look at them. Call a minimal subshift X palindromic, if an element (and hence all ) contains arbitrary long palindromes. Cellular automata that commute with the involution map the set of palindromic subshifts into itself. Discrete Schrödinger operators with palindromic subshifts as potential have a generic set in their hull for which the spectrum is purely singular continuous [19]. Therefore, applying cellular automata to palindromic subshifts gives new classes of operators with singular continuous spectrum.

Next: Cellular automata on circle Up: Cellular automata with almost Previous: Introduction

Oliver Knill
Fri Jun 26 16:29:39 CDT 1998