Cellular automaton
Cellular automata (CA) are a certain class of mathematical objects of which Conway's Game of Life is an example.
Informally, a cellular automaton consists of:
 A space of cells.
 A set of allowed states for each cell. An assignment of an state to every cell is called a “configuration” or “pattern” (the first term is more common in mathematical discussion and the later in informal discussions).
 A neighbourhood which defines which cells are considered to pass information to a given cell.
 A transition rule which specifies how given a cell and the states of its neighbours, a new state is produced.
The state of the cellular automaton evolves in discrete time, with the state of each cell at time t+1 being determined by the state of its neighbourhood at time t in accordance with the transition rule.
There are some variations on the above definition. It is common to require that there be a quiescent state (i.e., a state such that if the whole universe is in that state at generation 0 then it will remain so in generation 1). In Conway's Game of Life, the "OFF" state is quiescent, but the "ON" state is not. Other variations allow spaces other than ℤ^{n}, neighbourhoods that vary over space and/or time, probabilistic or other nondeterministic transition rules, and so on.
One approach of the study of cellular automata focus on properties that are common to all or many (most often infinitely many) cellular automata, without regard to specific examples. Another approach studies a single or a small finite set of cellular automata for which an explicit description is given.
Formal definition
Let us denote the set of integers by ℤ and the length of any tuple x by x. For any tuples of integers x and y such that x=y we denote their elementwise addition by x+y.
A cellular automaton is a tuple (ℤ^{n},S,N,f) such that the dimension n is at least 1, the set of states S is finite, the neighbourhood N is a tuple of elements of ℤ^{n} and f:S^{N}→S is the transition function.
A configuration of the cellular automaton (ℤ^{n},S,N,f) is any function ℤ^{n}→S.
The global transition function F of the cellular automaton (ℤ^{n},S,N,f) is a function from configurations to configurations F:(ℤ^{n}→S)→(ℤ^{n}→S) such that for any configuration c and element a∈ℤ^{n} we have F(c)(a)=f(a+N).
Let c be a configuration. When the cellular automata is clear from the context, then by c^{n} where n is a nonnegative integer we denote the configuration F^{n}(c) where F is the corresponding global transition function.
Let c and c′ be configurations, then we say that c′ is a translation of c if there exist an a∈ℤ^{n} such that for any x∈ℤ^{n} it holds that c′(a+x)=c(x). We say that the translation is proper if the condition holds for some ntuple whose elements are not all 0.
For any configuration c, if there exists a n≥1 such that c^{n} = c we call c an oscillator. If c is an oscillator and n is the least positive integer such that c^{n} = c then we call n the period of c. If c is an oscillator with period 1 then we call c a still life. If c is an oscillator and is not a still life we call c a proper oscillator.
A glider is a configuration c such that c^{n} is a proper translation of c for some n>0.
Our definition of cellular automaton is a simple derivative of the one given in Codd (1968). The only difference in scope is that Codd only allows grids of dimension 2 and requires the presence of a quiescent state, that is, a state v_{0} such that f(v_{0},...,v_{0})=v_{0}. Moreover, Codd only allows configurations in which finitely many cells are nonquiescent, while our definition of configuration allows any assignment of states to cells.
Common dimensions and neighborhoods
It has been requested that parts of this section be moved into neighborhood. 
In the approach that studies a small set of automata which are explicitly described the most common space is by far ℤ^{2}. This space can be easily represented in a computer screen or in print, is easy to manipulate, and geometric intuition is applicable. Some explicitly described cellular automata on ℤ^{1} and ℤ^{3} have also been studied. A disadvantage of ℤ^{1} is that information transfer requires many path crossings. In ℤ^{3} path crossings can be entirely avoided, but is harder to represent than ℤ^{1} and ℤ^{2}. The most common neighbourhoods of CA in ℤ^{2} are shown below.

For each dimension n≥1 and radius r≥0 we define the corresponding neighbourhoods:
 The generalized von Neumann neighbourhood is the set {x∈ℤ^{n}(MAX_{0≤i≤n1}x_{i})<r}.
 The generalized Moore neighbourhood is the set {x∈ℤ^{n}(Σ_{0≤i≤n1}x_{i})<r}.
 The Euclidean neighbourhood is the set {x∈ℤ^{n}(√Σ_{0≤i≤n1}x_{i}^{2})<r}.
See Gallery of neighbourhoods illustrations of some instances in ℤ^{2}.
The third proper regular tiling of twodimensional space, the triangular tiling,^{[1]} has been investigated; it can be simulated on the square grid using 4 states that divide each cell into two right triangles.^{[2]} It can be divided into at least two major neighbourhoods, the triangular Moore neighbourhood and triangular von Neumann neighbourhood.
Threedimensional rules use the cubic honeycomb, which gives rise to many potential neighbourhoods, such as the cubic Moore and cubic Von Neumann neighbourhoods, among others.
Fourdimensional rules most commonly use the tesseractic honeycomb (with a tesseractic Moore and tesseractic von Neumann neighbourhood). While fourdimensional space also admits the 16cell honeycomb and 24cell honeycomb, these do not seem to have been used as of yet.
Irregular tesselations, such as the Cairo pentagonal tesselation, have been investigated.
Generalizations and topological characterization
Our definition is enough to describe most of the cellular automata in which explicitly described configurations are studied. In particular it handles as expected the elementary cellular automata, CA on the Euclidean square tessellation (including all lifelike CA and all nontotalistic CA) and the Euclidean hexagonal tessellation. Furthermore, CA on the Euclidean triangular tessellation can be handled when proper care is taken. However, there exist objects which are cellular automata according to our informal description, but can not be defined as such in our formal definition. An example is cellular automata in hyperbolic tessellations (Margenstern, 2013). A very general definition of cellular automata is given in Moriceau (2011) and a further generalization is given in Wacker (2016). Interestingly, Wacker's definition uses amenable groups. Both amenable groups and cellular automata were introduced by the same man: John von Neumann.
A remarkable result, the CurtisHedlundLyndonRichardson (CHLR) theorem, relates cellular automata theory with topology and dynamical system theory. An informal statement is given as follows: Let the set of states be given the discrete topology and the configuration space be given the Tikhonov topology; then the global transition functions of the cellular automata over the configuration space are exactly those functions which are continuous and commute with the translations of the cellular space. In particular, the CHLR theorem holds for our definition of CA. Informally we state that the CHLR theorem holds for definitions of CA where the set of states is required to be finite, but if the set of states is allowed to be infinite, the set of allowable neighborhoods must be expanded or a further constraint must be imposed on continuous functions so that an analogous result holds (CeccheriniSilberstein 2010; Sobottka 2015). Generally when a novel definition of cellular automaton is presented a corresponding version of the CHLR theorem is proved in the same treatise.
The CHLR theorem was demonstrated independently by Hedlund (1969) (in this paper credit is given to Curtis and Lyndon in addition to the author) and Richardson (1972). Neither of these papers use the term “cellular automaton”. Nonetheless the systems they study are, respectively, 2dimensional deterministic cellular automata and ndimensional nondeterministic cellular automata.
Block cellular automata
 Main article: Block cellular automaton
In the above definitions of cellular automata, the transition function takes the state of a set of possibly many cells and gives the next state for a single cell. A block cellular automaton differs in that the universe is partitioned into nonoverlapping blocks of finite size, and the transition rule is applied to a whole block at a time rather than a single cell. A motivation to study block cellular automata is the ease with which reversible global transition functions can be generated.
Selfreplicating configurations
Informally, a configuration that creates a copy of itself after some number of generations is called a replicator.
John von Neumann investigated the possibility of building a selfreplicating machine. He originally considered a mechanical approach, but decided that this was too hard to control. With the help of Stanislaw Ulam, he designed a new mathematical abstraction, the cellular automaton, in order to create a replicator. His CA was made in the late 1940s and is complex. It operates on the Von Neumann neighbourhood (a cell and its four orthogonally connected neighbours), and has 29 states. It is described in von Neumann, Burks (1966).
Subsequent to the von Neumann's cellular automaton new cellular automata have been produced capable of selfreplication and universal computation with fewer states and using the same (von Neumann) neighborhood. Results include Codd (1968) with 8 states, Banks (1971) with 4 states and Serizawa (1987) with 3 states. As of 2017, Serizawa's CA appears to be the simplest (in terms of neighborhood size×number of states) cellular automaton known to have a nontrivial replicator.
Langton (1984) constructed a cellular automaton and a replicator. His cellular automaton is a simplification of Codd's. However, Langton's CA was not intended to support universal computation. The simplicity of the configuration is possible because of a novel method of selfreplication. The replicator consists of a loop with circulating cell states that encode instructions to construct a new arm, then turn 90° and repeat until a new loop is formed. The new loop is then filled with the same circulating information and the connection between it and the loop that generated it is severed. The parent loop continues to build copies until no more space is available, then it becomes a still life. Later variants of the loop added construction capabilities to it, and the most advanced versions granted it properties akin to a living organism, including a finite "lifespan", an approximation of evolution via natural selection, and sexual reproduction.
Nehaniv (2002) presented a method that allows the transformation of conventional (synchronous) cellular automata to an equivalent asynchronous cellular automata (a case not covered by our definition above). In the same paper, a selfreproducing configuration is presented which is based on the described procedure applied to Langton's CA.
Conway's Game of Life is known to be universal, with 2 states and the Moore neighbourhood. Conway did not design Life for this purpose, unlike von Neumann's, Codd's, Banks' and Serizawa's rules, but he did deliberately choose a set of rules known to exhibit sufficiently complex behavior that selfreplication was likely to be possible. In other words, when the rules of Life were first chosen, it was not a foregone conclusion that replicators would be constructible  but it can't be said that the existence of replicators in the rule is purely coincidental.
The Spartan universal computerconstructor could replicate, given a sufficient program tape. The Gemini spaceship constructs a complete copy of its own circuitry, but is not considered to be a replicator because its instruction tape is never duplicated. Between 2010 and 2017 much more efficient construction mechanisms have been developed that can be used for selfreplication, but to date only a limited onedimensional example has actually been completed (the linear propagator).
Formal definition
There are several possible nonequivalent definitions of selfreplicators. Moore (1962) proposed a simple definition which does not attempt to exclude trivial cases (although Moore wrote “selfreproduction”, we assume that it synonymous with “selfreplication”). However, his definitions of selfreplicator is limited to the same cellular automata and configurations allowed by the definition of Codd (1968). Our definition is a slight generalization of Moore's definition to cover all the configurations allowed by our definition.
Not all of the selfreplicators mentioned above meet our formal definition. Langton's selfreplicating loop and the classical HighLife replicator meet our definition. Typically, a configuration does not meet our definition if each copy generates only one "child" copy of itself, and does not return to its initial state after finishing construction of the child copy.
A slight complication not covered below is the case of a highperiod replicator pattern that creates its child copies in a different phase from the parent. For example, a replicator may contain oscillating components such as a moving "tape" of gliders for information storage. Parent and child copies of the configuration may not match exactly at any given time  but a future state of the child copy will precisely match the current state of the parent copy, and vice versa.
It seems reasonable to consider such parent/child pairs to be valid copies of each other for the purposes of the definitions below, even if they are not phasematched. In most cases it can be shown that after a sufficient number of replication cycles have passed, an arbitrarily large number of phasematched descendants of a parent pattern will inevitably be present.
Definition: Let (ℤ^{n},S,N,f) be a cellular automaton. Let c be a configuration such that for some s∈S the set X={a∈ℤ^{n}c(a)≠s} is finite. We say that c is a finite configuration, s is a background state of c and X is a support of c.
Theorem: Let c be a finite configuration, then there is a unique background state and support of c.
 Let v and v′ be background states of c. Let X be the set of all cells a such that c(a)≠v and respectively for X′ and v′. The set ℤ^{n}\(X∪X′) is nonempty because ℤ^{n} is infinite and X∪X′ is finite. Let x∈ℤ^{n}\(X∪X′). By the properties of set union and complement we have x∈ℤ^{n}\X and x∈ℤ^{n}\X′; by definition of X and X′ we have x=v and x=v′; therefore v=v′. Again from the definition of X and X′ it follows that X=X′.
Definition: Let c be a finite configuration. We write bg(c) for the background state of c and we write su(c) for the support of c.
Definition: Let c and c′ be finite configurations such that bg(c)=bg(c′). If su(c)∩su(c′)=∅ we say that c is disjoint from c′. If su(c)⊂su(c′) and for all a∈su(c) we have c(a)=c′(a) then we say that c′ contains c.
Definition: Let c and c′ be configurations. We say that c′ contains at least n copies if c if there exist a set X of pairwise disjoint translations of c and for each x∈X, c contains x.
Definition: A configuration c is called a selfreplicator if for any n≥1 there exist a t≥0 such that c_{t} contains at least n disjoint copies of c.
Definition: Let c and c be a configuration. Let n≥0 be an integer. If c′ contains at least n copies of c and for any integer k>n it is not the case that c′ contains at least k copies of c then we say that c′ contains exactly n copies of c.
Lifelike cellular automata
 Main article: Lifelike cellular automaton
A cellular automaton is said to be Lifelike if it meets the following four criteria:
 It has two dimensions (i.e., n=2).
 It has two states, usually called OFF and ON (i.e., S=2).
 It uses the Moore neighbourhood.
 The new state of a cell in the next generation can be expressed as a function of the number of cells in its neighbourhood that are in the ON state and the cell's own state; that is, the rule is outer totalistic (also called semitotalistic).
This class of cellular automata is named for Conway's Game of Life, the most famous cellular automaton, which meets all four criteria above.
Cyclic cellular automaton
Cyclic cellular automata are a class of cellular automata commonly known for producing spiral patterns.
Partitioned cellular automaton
Partitioned cellular automata (PCA) are a class of cellular automata investigated due to their capability for reversibility. They have been researched on square and triangular grids.
Rockpaperscissors cellular automaton
Rockpaperscissors cellular automata are a class of cellular automata based on the classic game of rockpaperscissors as well as variations thereof.^{[3]}
See also
References
 ↑ Brian Prentice (May 20, 2017). Re: Thread for basic questions (discussion thread) at the ConwayLife.com forums
 ↑ Tim Hutton (June 28, 2015). "The Rules". Golly Rule Table Repository. Retrieved on August 30, 2017.
 ↑ https://softologyblog.wordpress.com/2018/03/23/rockpaperscissorscellularautomata/
Books and articles
 Banks, E. R. (1971) Information processing and transmission in cellular automata.
 CeccheriniSilberstein, T.; Coornaert, M. (2010) Cellular Automata and Groups. DOI: 10.1007/9783642140341. ISBN: 9783642140334, 9783642140341.
 Codd, E. F. (1968) Cellular Automata. No ISBN. WorldCat OCLC number: 637978742.
 Hedlund, G. A. (1969) Endomorphisms and Automorphisms of the Shift Dynamical System. DOI: 10.1007/BF01691062.
 Langton, C. G. (1984) Selfreproduction in cellular automata. DOI: 10.1016/01672789(84)902562.
 Margenstern, M. (2013) Small Universal Cellular Automata in Hyperbolic Spaces: A Collection of Jewels.
 Moore, E. F. (1962) Machine models of selfreproduction in Mathematical Problems in the Biological Sciences. DOI: 10.1090/psapm/014/9961.
 Moriceau, S. (2011) Cellular automata on a Gset. arXiv: 1105.5335 [math.DS].
 Nehaniv, C. E. (2002) SelfReproduction in Asynchronous Cellular Automata in Proceedings 2002 NASA/DoD Conference on Evolvable Hardware. DOI: 10.1109/eh.2002.1029854.
 Richardson, D. (1972) Tessellation with Local Transformations. DOI: 10.1016/S00220000(72)800096.
 Serizawa, T. (1987) ThreeState Neighbor Cellular Automata Capable of Constructing SelfReproducing Machines. DOI: 10.1002/scj.4690180404.
 Sobottka, M.; Gonçalves, D. (2015) A note on the definition of siding block codes and the CurtisHedlundLyndon Theorem. arXiv: 1507.02180 [math.DS].
 von Neumann, J.; Burks, A. W. (1966) Theory of SelfReproducing Automata. No ISBN. WorldCat OCLC number: 7298386.
 Wacker, S. (2016) Cellular Automata on Group Sets and the Uniform CurtisHedlundLyndon Theorem. DOI: 10.1007/9783319393001_15. In Cellular Automata and Discrete Complex Systems. AUTOMATA 2016.
External links
 Cellular automaton at Wikipedia
 Cyclic cellular automaton at Wikipedia
 Rock paper scissors at Wikipedia
 Partitioned Cellular Automata (discussion thread) at the ConwayLife.com forums
 Cellular automata rules lexicon at Mirek Wójtowicz's Cellebration page
 Cellular automaton at the Life Lexicon
 Cellular Automaton at Wolfram Mathworld
 Totalistic Cellular Automaton at Wolfram Mathworld
 Golly Rule Table Repository