Complex Systems

Formal Language Characterization of Cellular Automaton Limit Sets Download PDF

Lyman P. Hurd
Mathematics Department, Princeton University,
Princeton, NJ 08544, USA


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.