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 tex2html_wrap_inline561 with the product topology. The set A is called the alphabet, tex2html_wrap_inline565 the configuration space, and points in tex2html_wrap_inline565 are called configurations. Let tex2html_wrap_inline501 act on tex2html_wrap_inline565 by translation: tex2html_wrap_inline573 . A cellular automaton tex2html_wrap_inline415 is a continuous map on tex2html_wrap_inline577 such that tex2html_wrap_inline579 for all tex2html_wrap_inline511 . By the Curtis-Hedlund-Lyndon theorem (see e.g. [16]), there is for every cellular automaton tex2html_wrap_inline415 a finite set tex2html_wrap_inline585 such that tex2html_wrap_inline587 only depends on tex2html_wrap_inline589 .

A set tex2html_wrap_inline591 is called invariant if tex2html_wrap_inline593 for all tex2html_wrap_inline511 . A compact invariant subset of tex2html_wrap_inline565 is called a subshift. The orbit of tex2html_wrap_inline599 is the set tex2html_wrap_inline601 and the orbit closure tex2html_wrap_inline603 of x is the closure of tex2html_wrap_inline607 in tex2html_wrap_inline565 . So orbit closures are subshifts. A subshift X is called minimal if tex2html_wrap_inline613 for all tex2html_wrap_inline615 . A probability measure tex2html_wrap_inline617 on (the Borel tex2html_wrap_inline619 -algebra of) tex2html_wrap_inline565 or a subshift is called invariant if tex2html_wrap_inline623 for all measurable G and all tex2html_wrap_inline511 . 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 tex2html_wrap_inline415 maps subshifts to subshifts. Thus the image tex2html_wrap_inline631 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).

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 tex2html_wrap_inline639 (i.e., the eigenfunctions are dense in tex2html_wrap_inline641 , where m is the invariant measure), then tex2html_wrap_inline645 also has discrete spectrum tex2html_wrap_inline647 and tex2html_wrap_inline647 is a subgroup of tex2html_wrap_inline639 . The reason is that the measure theoretical factor tex2html_wrap_inline653 of tex2html_wrap_inline655 is isomorphic to tex2html_wrap_inline657 and that the conditional expectation tex2html_wrap_inline659 of an eigenfunction tex2html_wrap_inline661 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 tex2html_wrap_inline665 is defined as the topological entropy of tex2html_wrap_inline667 (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 tex2html_wrap_inline615 (and hence all tex2html_wrap_inline615 ) contains arbitrary long palindromes. Cellular automata that commute with the involution tex2html_wrap_inline675 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 up previous
Next: Cellular automata on circle Up: Cellular automata with almost Previous: Introduction

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