Formal Language Characterization of Cellular Automaton Limit Sets
Lyman P. Hurd
Mathematics Department, Princeton University,
Princeton, NJ 08544, USA
Abstract
A formal language description of one-dimensional cellular automata limit sets is given, and a series of examples illustrating several degrees of complexity are constructed. The undecidability of membership of a string in the limit set of a cellular automaton rule is proven.
