Nonrecursive Cellular Automata Invariant Sets
Lyman P. Hurd
Lab for Plasma Research, University of Maryland,
College Park, MD 20742, USA
Abstract
Languages corresponding to two invariant subshifts, the limit set and periodic set are examined. The complement of the language produced by a cellular automaton limit set is always recursively enumerable (r.e.), and modulo intersection with a regular language and 
-limited homomorphism, all languages with r.e. complements arise this way. The language produced by the periodic set is always r.e.; the closure of the set of languages produced by all cellular automata is the set of all r.e. languages. As a corollary, a specific cellular automaton F is produced whose limit language is not r.e. (although its complement is), and a rule G whose periodic points give rise to a language which is r.e. but not recursive.
