The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics.
[2] 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).
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),[3] and it can be even further generalized from lattices to discrete groups.
An alphabet is any finite set of symbols, which may be thought of as the states of the cells in a cellular automaton.
The function f that uses this rule to map a configuration of the cellular automaton into its successor configuration is necessarily equivariant with respect to the shift map, by the assumption that all positions use the same update rule.
It is also necessarily continuous in the Cantor topology: if p is a fixed pattern, defining a fundamental open set P, then f−1(P) is defined by a finite set of patterns, the assignments to cells in the neighborhood of p that cause f to produce p. The Curtis–Hedlund–Lyndon theorem states that these two properties are sufficient to define cellular automata: every continuous equivariant function is the update rule of a cellular automaton.
It follows by a compactness argument that the function mapping each configuration to its predecessor is itself continuous in the shift space, and it is clearly also shift-invariant.
[5][6] One can generalize the definition of cellular automaton to those maps that are defined by rules for computing the new value of each position in a configuration based on the values of cells in a finite but variable neighborhood surrounding the position.
In this case, as in the classical definition, the local rule is the same for all cells, but the neighborhood is also a function of the configuration around the position.
Generalized cellular automata were proposed by Sobottka & Gonçalves (2017) [7] where it was proved they correspond to continuous shift-equivariant maps.