![Complex Systems Complex Systems](https://www.complex-systems.com/wp-content/themes/complexsystems/img/ui_logo_small.png)
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.