A Topological Classification of D-Dimensional Cellular Automata

We give a classification of cellular automata in arbitrary dimensions and on arbitrary subshift spaces from the point of view of symbolic and topological dynamics. A cellular automaton is a continuous, shift-commuting map on a subshift space; these objects were first investigated from a purely mathematical point of view by Hedlund in 1969. In the 1980's, Wolfram categorized one-dimensional cellular automata based on features of their asymptotic behavior which could be seen on a computer screen. Gilman's work in 1987 and 1988 was the first attempt to mathematically formalize these characterizations of Wolfram's, using notions of equicontinuity, expansiveness, and measure-theoretic analogs of each. We introduce a topological classification of cellular automata in dimensions two and higher based on the one-dimensional classification given by Kurka. We characterize equicontinuous cellular automata in terms of periodicity, investigate the occurrence of blocking patterns as related to points of equicontinuity, demonstrate that topologically transitive cellular automata are both surjective and have sensitive dependence on initial conditions, and construct subshift spaces in all dimensions on which there exists an expansive cellular automaton. We provide numerous examples throughout and conclude with two diagrams illustrating the interaction of topological properties in all dimensions for the cases of an underlying full shift space and of an underlying subshift space with dense shift-periodic points