Recursive Cellular Automata Invariant Sets
Lyman P. Hurd
Lab for Plasma Research, University of Maryland,
College Park, MD 20742, USA
Abstract
Subshifts of bi-infinite words give rise to languages in a natural way. Three invariant subshifts associated with cellular automata dynamics are considered: the periodic set, non-wandering set, and limit set. Examples have been given (see [8,12]) of cellular automata whose invariant sets give rise to nonrecursive languages. In this paper, examples are given of cellular automata whose invariant sets correspond to regular, context-free, and context-sensitive languages. It is proved that a cellular automaton has a subshift of finite type limit set only if its images stabilize. As a corollary, only mixing subshifts of finite type can occur as cellular automaton limit sets.
