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. ), 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 ), being of finite type, and primality (there is no nontrivial factor).
1) Prime subshifts exist . 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 ,
whereas in higher dimensions the topological entropy
is `as a rule' infinite (cf. ).
The directional topological entropy in the direction is defined
as the topological entropy of (cf. ).
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 . Therefore, applying cellular automata to palindromic subshifts gives new classes of operators with singular continuous spectrum.