Curtis–Hedlund–Lyndon theorem

The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlund credited Curtis and Lyndon as co-discoverers. It has been called "one of the fundamental results in symbolic dynamics".

The theorem states that a function from a shift space to itself represents the transition function of a one-dimensional cellular automaton if and only if it is continuous (with respect to the Cantor topology) and equivariant (with respect to the shift map). More generally, it asserts that the morphisms between any two shift spaces (i.e., continuous mappings that commute with the shift) are exactly those mappings which can be defined uniformly by a local rule.

The version of the theorem in Hedlund's paper applied only to one-dimensional finite automata, but a generalization to higher dimensional integer lattices was soon afterwards published by Richardson (1972), and it can be even further generalized from lattices to discrete groups. One important consequence of the theorem is that, for reversible cellular automata, the reverse dynamics of the automaton can also be described by a cellular automaton.

An alphabet is any finite set of symbols, which may be thought of as the states of the cells in a cellular automaton. A configuration is a bi-infinite sequence of symbols from the alphabet:

...
Wikipedia