|
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.
