Английская Википедия: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.[1] It has been called "one of the fundamental results in 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). More generally, it asserts that the morphisms between any two shift spaces (that is, 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 Шаблон:Harvtxt,[3] 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.
Definitions
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:
A position in a configuration is an integer, the index of one of the symbols in the sequence; the positions may be thought of as the cells of a cellular automaton. A pattern is a finite set of positions and an assignment of symbols to each of these positions.
The shift space is the set of all possible configurations over a given alphabet. It may be given the structure of a topological space according to the Cantor topology, in which the fundamental open sets are the sets of configurations that match any single pattern and the open sets are arbitrary unions of fundamental open sets. In this topology, a function Шаблон:Mvar from configurations to configurations is continuous if, for any fixed pattern Шаблон:Mvar defining a fundamental open set Шаблон:Mvar, the set Шаблон:Math of configurations mapped by Шаблон:Mvar into Шаблон:Mvar can itself be described by a (possibly infinite) set Шаблон:Mvar of patterns, with the property that a configuration belongs to Шаблон:Math if and only if it matches a pattern in Шаблон:Mvar.
The shift map is a particular continuous function Шаблон:Mvar on the shift space that transforms a configuration Шаблон:Mvar into a new configuration Шаблон:Mvar in which each symbol is shifted one position over from its previous position: that is, for every integer Шаблон:Mvar, Шаблон:Math. A function Шаблон:Mvar is equivariant under the shift map if the transformation on configurations described by Шаблон:Mvar commutes with the shift map; that is, for every configuration Шаблон:Mvar, it must be the case that Шаблон:Math. Intuitively, this means that every position of the configuration is updated by Шаблон:Mvar using the same rule as every other position.
A cellular automaton is defined by a rule for computing the new value of each position in a configuration based only on the values of cells in a prior-fixed finite neighborhood surrounding the position, with all positions of the configuration being updated simultaneously based on the same update rule. That is, the new value of a position is a function only of the values of the cells in its neighborhood rather than depending more generally on an unbounded number of cells of the previous configuration. The function Шаблон:Mvar 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 Шаблон:Mvar is a fixed pattern, defining a fundamental open set Шаблон:Mvar, then Шаблон:Math is defined by a finite set of patterns, the assignments to cells in the neighborhood of Шаблон:Mvar that cause Шаблон:Mvar to produce Шаблон:Mvar. 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.
Proof
Ceccherini-Silberstein and Coornaert provide the following proof of the Curtis–Hedlund–Lyndon theorem.[4]
Suppose Шаблон:Mvar is a continuous shift-equivariant function on the shift space. For each configuration Шаблон:Mvar, let Шаблон:Mvar be the pattern consisting of the single symbol that appears at position zero of Шаблон:Math. By continuity of Шаблон:Mvar, there must exist a finite pattern Шаблон:Mvar in Шаблон:Mvar such that, if the positions outside Шаблон:Mvar are changed arbitrarily but the positions within Шаблон:Mvar are fixed to their values in Шаблон:Mvar, then the result of applying Шаблон:Mvar remains the same at position zero. Equivalently, there must exist a fundamental open set Шаблон:Mvar such that Шаблон:Mvar belongs to Шаблон:Mvar and such that for every configuration Шаблон:Mvar in Шаблон:Mvar, Шаблон:Math and Шаблон:Math have the same value at position zero. These fundamental open sets Шаблон:Mvar (for all possible configurations Шаблон:Mvar) form an open cover of the shift space. However, the shift space is a compact space: it is a product of finite topological spaces with the alphabet as their points, so compactness follows from Tychonoff's theorem. By compactness, every open cover has a finite subcover. The finite set of positions appearing in this finite subcover may be used as the neighborhood of position zero in a description of Шаблон:Mvar as a cellular automaton rule.
The same proof applies more generally when the set of integer positions is replaced by any discrete group Шаблон:Mvar, the space of configurations is replaced by the set of functions from Шаблон:Mvar to a finite alphabet, and shift-equivariance is replaced by equivariance under the action of Шаблон:Mvar on itself. In particular, it applies to cellular automata defined on an integer grid of any dimension.
Counterexample for infinite alphabets
Consider the space of bi-infinite sequences of integers, and define a function <math>f</math> from this space to itself according to the rule that, if Шаблон:Math, then for every position Шаблон:Mvar, Шаблон:Math. This rule is the same for each position, so it is shift-equivariant. And it can be shown to be continuous according to the Cantor topology: for each finite pattern Шаблон:Mvar in Шаблон:Mvar, there is a pattern in Шаблон:Mvar with at most twice as many positions that forces <math>f</math> to generate Шаблон:Mvar, consisting of the cells in Шаблон:Mvar together with the cells whose values are copied into Шаблон:Mvar. However, despite being continuous and equivariant, <math>f</math> is not a cellular automaton rule, because the value of any cell can potentially depend on the value of any other cell rather than only depending on the cells in any prior-fixed finite neighborhood.[4]
Application to reversible cellular automata
A cellular automaton is said to be reversible when every configuration of the automaton has exactly one predecessor. 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. Therefore, by the Curtis–Hedlund–Lyndon theorem, the time-reversed dynamics of the cellular automaton may itself be generated using a different cellular automaton rule.[3] However, the neighborhood of a cell in the reverse automaton may be significantly larger than the neighborhood of the same cell in the forward automaton.[5][6]
Generalization
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.
The counterexample given above for a continuous and shift-equivariant map which is not a classical cellular automaton, is an example of a generalized cellular automaton. When the alphabet is finite, the definition of generalized cellular automata coincides with the classical definition of cellular automata due to the compactness of the shift space.
Generalized cellular automata were proposed by Шаблон:Harvtxt [7] where it was proved they correspond to continuous shift-equivariant maps.
See also
References
