Curtis–Hedlund–Lyndon theorem
Encyclopedia
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.
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 morphism
s 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 lattice
s was soon afterwards published by , 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.
. 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
from configurations to configurations is continuous
if, for any fixed pattern defining a fundamental open set , the set of configurations mapped by into can itself be described by a (possibly infinite) set of patterns, with the property that a configuration belongs to if and only if it matches a pattern in .
The shift map is a particular continuous function on the shift space that transforms a configuration into a new configuration in which each symbol is shifted one position over from its previous position: that is, for every integer , . A function is equivariant
under the shift map if the transformation on configurations described by commutes with the shift map; that is, for every configuration , it must be the case that . Intuitively, this means that every position of the configuration is updated by 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 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 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 is a fixed pattern, defining a fundamental open set , then is defined by a finite set of patterns, the assignments to cells in the neighborhood of that cause to produce . 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.
Suppose is a continuous shift-equivariant function on the shift space. For each configuration , let be the pattern consisting of the single symbol that appears at position zero of .
By continuity of , there must exist a finite pattern in such that, if the positions outside are changed arbitrarily but the positions within are fixed to their values in , then the result of applying remains the same at position zero. Equivalently, there must exist a fundamental open set such that belongs to and such that for every configuration in , and have the same value at position zero. These fundamental open sets (for all possible configurations ) 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 as a cellular automaton rule.
The same proof applies more generally when the set of integer positions is replaced by any discrete group
, the space of configurations is replaced by the set of functions from to a finite alphabet, and shift-equivariance is replaced by equivariance under the action
of on itself. In particular, it applies to cellular automata defined on an integer grid of any dimension.
according to the rule that, if , then for every position , . 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 in , there is a pattern in with at most twice as many positions that forces to generate , consisting of the cells in together with the cells whose values are copied into . However, despite being continuous and equivariant, 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 a finite neighborhood.
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. 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.
Characterization (mathematics)
In mathematics, the statement that "Property P characterizes object X" means, not simply that X has property P, but that X is the only thing that has property P. It is also common to find statements such as "Property Q characterises Y up to isomorphism". The first type of statement says in...
of cellular automata in terms of their symbolic dynamics
Symbolic dynamics
In mathematics, symbolic dynamics is the practice of modeling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics given by the shift operator...
. It is named after Morton L. Curtis
Morton L. Curtis
Morton Landers Curtis was an American mathematician, an expert on group theory and the W. L. Moody, Jr. Professor of Mathematics at Rice University....
, Gustav A. Hedlund
Gustav A. Hedlund
Gustav Arnold Hedlund , an American mathematician, was one of the founders of symbolic and topological dynamics.-Biography:Hedlund was born May 7, 1904, in Somerville, Massachusetts. He did his undergraduate studies at Harvard University, earned a masters degree from Columbia University, and...
, and Roger Lyndon
Roger Lyndon
Roger Conant Lyndon was an American mathematician, for many years a professor at the University of Michigan. He is known for Lyndon words, the Curtis–Hedlund–Lyndon theorem, Craig–Lyndon interpolation and the Lyndon–Hochschild–Serre spectral sequence.-Biography:Lyndon was born on December 18, 1917...
; in his 1969 paper stating the theorem, Hedlund credited Curtis and Lyndon as co-discoverers.
The theorem states that a function from a shift space
Shift space
In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words representing the evolution of a discrete system. In fact, shift spaces and symbolic dynamical systems are often considered synonyms....
to itself represents the transition function
Transition function
In mathematics, a transition function has several different meanings:* In topology, a transition function is a homeomorphism from one coordinate chart to another...
of a one-dimensional cellular automaton if and only if it is continuous
Continuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
(with respect to the Cantor topology) and equivariant (with respect to the shift map). More generally, it asserts that the morphism
Morphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...
s 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 lattice
Integer lattice
In mathematics, the n-dimensional integer lattice , denoted Zn, is the lattice in the Euclidean space Rn whose lattice points are n-tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid lattice. Zn is the simplest example of a root lattice...
s was soon afterwards published by , and it can be even further generalized from lattices to discrete groups. One important consequence of the theorem is that, for reversible cellular automata
Reversible cellular automaton
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. Several methods of constructing reversible cellular automata are known, including the block cellular automaton and second-order cellular automaton methods...
, 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 automatonCellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
. A configuration is a bi-infinite sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
of symbols from the alphabet:
- .
A position in a configuration is an integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
, 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
Shift space
In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words representing the evolution of a discrete system. In fact, shift spaces and symbolic dynamical systems are often considered synonyms....
is the set of all possible configurations over a given alphabet. It may be given the structure of a topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
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
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
from configurations to configurations is continuous
Continuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
if, for any fixed pattern defining a fundamental open set , the set of configurations mapped by into can itself be described by a (possibly infinite) set of patterns, with the property that a configuration belongs to if and only if it matches a pattern in .
The shift map is a particular continuous function on the shift space that transforms a configuration into a new configuration in which each symbol is shifted one position over from its previous position: that is, for every integer , . A function is equivariant
Equivariant
In mathematics, an equivariant map is a function between two sets that commutes with the action of a group. Specifically, let G be a group and let X and Y be two associated G-sets. A function f : X → Y is said to be equivariant iffor all g ∈ G and all x in X...
under the shift map if the transformation on configurations described by commutes with the shift map; that is, for every configuration , it must be the case that . Intuitively, this means that every position of the configuration is updated by using the same rule as every other position.
A cellular automaton
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
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 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 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 is a fixed pattern, defining a fundamental open set , then is defined by a finite set of patterns, the assignments to cells in the neighborhood of that cause to produce . 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.Suppose is a continuous shift-equivariant function on the shift space. For each configuration , let be the pattern consisting of the single symbol that appears at position zero of .
By continuity of , there must exist a finite pattern in such that, if the positions outside are changed arbitrarily but the positions within are fixed to their values in , then the result of applying remains the same at position zero. Equivalently, there must exist a fundamental open set such that belongs to and such that for every configuration in , and have the same value at position zero. These fundamental open sets (for all possible configurations ) form an open cover of the shift space. However, the shift space is a compact space
Compact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
: it is a product of finite topological spaces with the alphabet as their points, so compactness follows from Tychonoff's theorem
Tychonoff's theorem
In mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact. The theorem is named after Andrey Nikolayevich Tychonoff, who proved it first in 1930 for powers of the closed unit interval and in 1935 stated the full theorem along with the...
. 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 as a cellular automaton rule.
The same proof applies more generally when the set of integer positions is replaced by any discrete group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
, the space of configurations is replaced by the set of functions from to a finite alphabet, and shift-equivariance is replaced by equivariance under the action
Group action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
of on itself. In particular, it applies to cellular automata defined on an integer grid of any dimension.
Counterexample for infinite alphabets
It is not possible to generalize the Curtis–Hedlund–Lyndon theorem to infinite alphabets. For example, consider the space of bi-infinite sequences of integers, and define a function from this space to itselfaccording to the rule that, if , then for every position , . 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 in , there is a pattern in with at most twice as many positions that forces to generate , consisting of the cells in together with the cells whose values are copied into . However, despite being continuous and equivariant, 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 a finite neighborhood.
Application to reversible cellular automata
A cellular automaton is said to be reversibleReversible cellular automaton
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. Several methods of constructing reversible cellular automata are known, including the block cellular automaton and second-order cellular automaton methods...
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. 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.