HOME

TheInfoList



OR:

The Curtis–Hedlund–Lyndon theorem is a mathematical
characterization Characterization or characterisation is the representation of persons (or other beings or creatures) in narrative and dramatic works. The term character development is sometimes used as a synonym. This representation may include direct methods ...
of
cellular automata A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
in terms of their
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 (e ...
. It is named after
Morton L. Curtis Morton Landers Curtis (November 11, 1921 – February 4, 1989) was an American mathematician, an expert on group theory and the William Lewis Moody, Jr., W. L. Moody, Jr. Professor of Mathematics at Rice University.
,
Gustav A. Hedlund Gustav Arnold Hedlund (May 7, 1904 – March 15, 1993), an American mathematician, was one of the founders of symbolic dynamics, symbolic and topological dynamics. Biography Hedlund was born May 7, 1904, in Somerville, Massachusetts. He did his ...
, and
Roger Lyndon Roger Conant Lyndon (December 18, 1917 – June 8, 1988) 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 a ...
; 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 In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words that represent the evolution of a discrete system. In fact, shift spaces and '' symbolic dynamical systems'' are often considered synon ...
to itself represents the transition function of a one-dimensional cellular automaton if and only if it is
continuous Continuity or continuous may refer to: Mathematics * Continuity (mathematics), the opposing concept to discreteness; common examples include ** Continuous probability distribution or random variable in probability and statistics ** Continuous ...
(with respect to the Cantor topology) and
equivariant In mathematics, equivariance is a form of symmetry for functions from one space with symmetry to another (such as symmetric spaces). A function is said to be an equivariant map when its domain and codomain are acted on by the same symmetry group, ...
(with respect to the shift map). More generally, it asserts that the
morphism In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms a ...
s 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 lattice In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid l ...
s was soon afterwards published by ,. and it can be even further generalized from lattices to
discrete group In mathematics, a topological group ''G'' is called a discrete group if there is no limit point in it (i.e., for each element in ''G'', there is a neighborhood which only contains that element). Equivalently, the group ''G'' is discrete if and on ...
s. 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 An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
is any finite set of symbols, which may be thought of as the states of the cells in a
cellular automaton A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
. A ''configuration'' is a
bi-infinite sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called t ...
of symbols from the alphabet: :. A ''position'' in a configuration is an
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
, 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 In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words that represent the evolution of a discrete system. In fact, shift spaces and '' symbolic dynamical systems'' are often considered synon ...
is the set of all possible configurations over a given alphabet. It may be given the structure of a
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
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 or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
from configurations to configurations is
continuous Continuity or continuous may refer to: Mathematics * Continuity (mathematics), the opposing concept to discreteness; common examples include ** Continuous probability distribution or random variable in probability and statistics ** 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 In mathematics, and in particular functional analysis, the shift operator also known as translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag operator. Shift ...
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 In mathematics, equivariance is a form of symmetry for functions from one space with symmetry to another (such as symmetric spaces). A function is said to be an equivariant map when its domain and codomain are acted on by the same symmetry group, ...
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 A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
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 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 In mathematics, and more particularly in set theory, a cover (or covering) of a set X is a collection of subsets of X whose union is all of X. More formally, if C = \lbrace U_\alpha : \alpha \in A \rbrace is an indexed family of subsets U_\alpha\s ...
of the shift space. However, the shift space is a
compact space In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
: it is a product of finite topological spaces with the alphabet as their points, so compactness follows from
Tychonoff's theorem In mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact with respect to the product topology. The theorem is named after Andrey Nikolayevich Tikhonov (whose surname sometimes is trans ...
. 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 In mathematics, a topological group ''G'' is called a discrete group if there is no limit point in it (i.e., for each element in ''G'', there is a neighborhood which only contains that element). Equivalently, the group ''G'' is discrete if and on ...
, 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 Action may refer to: * Action (narrative), a literary mode * Action fiction, a type of genre fiction * Action game, a genre of video game Film * Action film, a genre of film * ''Action'' (1921 film), a film by John Ford * ''Action'' (1980 fil ...
of 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 from this space to itself 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 any prior-fixed finite neighborhood.


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. 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..


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 . where it was proved they correspond to continuous shift-equivariant maps.


See also

* Surjunctive group


References

{{DEFAULTSORT:Curtis-Hedlund-Lyndon theorem Theorems in discrete mathematics Articles containing proofs Symbolic dynamics Cellular automata