Curtis-Hedlund-Lyndon Theorem

The Curtis-Hedlund-Lyndon theorem is a foundational result in symbolic dynamics, named for Morton L. Curtis, Gustav A. Hedlund and Roger Lyndon, stating that a function from a shift space to itself is the transition rule of a one-dimensional cellular automaton exactly when it is continuous with respect to the Cantor topology on the shift space and equivariant with respect to the shift map. Hedlund's 1969 paper gave the theorem its formal statement and credited Curtis and Lyndon as co-discoverers of the underlying idea; Richardson generalized the result to higher-dimensional integer lattices in 1972, and later work extended it further from lattices to discrete groups in general. One consequence of the theorem is that a reversible cellular automaton's inverse dynamics can also always be described by a cellular automaton rule.