Expansive Cellular Automata
by
Emily Gamber
UNC Chapel Hill

Let X be a subshift space, that is, a closed, shift-invariant subset of the full D-dimensional shift space over the alphabet A. A cellular automaton, CA, is a continuous self-map of X which commutes with the action of the shift. As part of our continuing topological classification of CA's, we examine expansive CA's. A dynamical system is expansive if there exists an expansive constant so that for all distinct points, x and y, some iterate of x and y are separated by at least the expansive constant. A result of Shereshevsky is that no expansive CA exist on a full shift space in dimension 2 or higher; this is due to the fact that the entropy of the underlying shift is positive. We show that there exist subshift spaces in every dimension where there are expansive CA, by constructing a D-dimensional subshift space from the action of a particular (D-1)-dimensional CA. Further, we show that all subshift spaces constructed in this way, from a CA in dimension (D-1), have entropy 0 with respect to the D-dimensional shift action, so that expansive CA's may exist on such a space.

Date received: March 7, 2006