Cellular automaton

A cellular automaton is a certain class of mathematical objects of which Conway's Game of Life is an example. It consists of a number of things:

• A positive integer n which is the dimension of the cellular automaton
• A finite set of states S, with at least two members
• A state for the whole cellular automaton is obtained by assigning an element of S to each point of the n-dimensional lattice Zⁿ (where Z is the set of all integers), known as cells
• The concept of a neighbourhood. The neighbourhood N of the origin is some finite (nonempty) subset of Zⁿ. The neighbourhood of any other cell is obtained in the obvious way by translating that of the origin.
• A transition rule, which is a function from S^N to S (that is to say, for each possible state of the neighbourhood the transition rule specifies some cell state).

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 Zⁿ, neighbourhoods that vary over space and/or time, probabilistic or other non-deterministic transition rules, and so on.

It is common for the neighbourhood of a cell to be the 3×...×3 hypercube centred on that cell, which is known as its Moore neighbourhood.

Life-like cellular automata

A cellular automaton is said to be Life-like 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).
• The neighborhood used is the Moore neighborhood; it consists of the eight (orthogonally and diagonally) adjacent cells to the one under consideration and (possibly) the cell itself.
• 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 (or semitotalistic).

This class of cellular automata is named for Conway's Game of Life, the most famous cellular automaton, which Life-like cellular automata mimic. Many different terms are used to describe this class of cellular automata; it is also common to refer to it as the "Life family" or to simply use phrases like "similar to Life".

Rules

A common notation used to describe these automata is referred to as "S/B", which is known as its rule (or rulestring). S (for survival) is a list of all the numbers of ON cells that cause an ON cell to remain ON. B (for birth) is a list of all the numbers of ON cells that cause an OFF cell to turn on. If 0 is in the list, then blank regions of the universe will turn on in one generation. S/B is often referred to as the rule or rulestring of the given cellular automata.

As an example, the seeds rulestring is /2. All OFF cells that have exactly two adjacent ON cells will turn on in the next generation, while every ON cell dies in every generation, since the survival list is empty. The rulestring of Conway's Game of Life is 23/3.

Other notations are sometimes used to describe the rules of the given Life-like cellular automaton. The most common other format is "B{number list}/S{number list}", where the number lists are the numbers of neighbours that cause a dead cell to be born and cause an alive cell to stay alive, respectively. In this format, Conway's Game of Life would have the rulestring B3/S23.

Well-known Life-like cellular automata

There are 262144 distinct Life-like rules, which is far too many to list here. The following table lists rules that are particularly well-known or well-studied.

Rulestring	Name	Description
/2	Seeds	Chaotic growth; all patterns are phoenixes. Has spaceships
/234	Serviettes	Lacy patterns
012345678/3	Flakes, Life without death	An expanding rule that produces complex flakes. It also has important ladder-like patterns.
012345678/378		Wolfram Fig. 9(a)
01356/13456		Wolfram Fig. 7(d)
018/018		Wolfram Fig. 13(c); class 2
0238/123567		Wolfram Fig. 13(f); class 3
03456/34		Wolfram Fig. 7(g)
045/0578		Wolfram Fig. 7(i)
0468/236		Wolfram Figs. 7(a), 13(g); class 3
1/1	Gnarl	A simple exploding rule that forms complex patterns from even a single live cell.
12345/3	Maze	Forms maze-like designs
12456/0578		Wolfram Fig. 7(h)
125/36	2x2	A chaotic rule with many simple still lifes, oscillators and spaceships. Its name comes from the fact that it sends patterns made up of 2x2 blocks to patterns made up of 2x2 blocks.
135/135		Wolfram Fig. 13(h); class 3
1357/1357	Replicator	Edward Fredkin's replicating automaton: every pattern is eventually replaced by multiple copies of itself
1358/357	Amoeba	A chaotic rules that is well balanced between life and death; it forms patterns with chaotic interiors and wildly moving boundaries.
23/3	Conway's Life	A chaotic rule that is by far the most well-known and well-studied. It exhibits highly complex behavior.
23/36	HighLife	Similar to Life but with a small self-replicating pattern
234/3		Wolfram Figs. 9(b), 13(b); Class 2. Has spaceships Stable growths.
2345/45678	Walled Cities	Forms centers of activity separated by walls
2346/367		Wolfram Fig. 9(c). Has spaceships
235678/3678	Stains	Patterns quickly stabilize, curiously different from nearby rules
235678/378	Coagulations	An exploding rule in which patterns tend to expand forever, producing a thick "goo" as it does so.
238/357	Pseudo life	Pattern evolution resembles Life but few patterns from Life work in this rule because the glider is unstable.
245/368	Move	Random patterns tend to stabilize, but has many naturally occurring and engineered spaceships
27/257		Wolfram Fig. 7(b); has spaceships
34/34	34 Life	An exploding rule that was initially thought to be a stable alternative to Conway's Life, until computer simulation found that most patterns tend to explode. It has many small oscillators and a simple period 3 orthogonal spaceship.
34678/3678	Day & Night	A stable rule that is symmetric under on-off reversal. Many patterns exhibiting highly complex behavior have been found for it.
4567/345	Assimilation	A very stable rule that forms permanent diamond-shaped patterns with partially filled interiors.
45678/137		Wolfram Fig. 7(f)
45678/3	Coral	An exploding rule in which patterns grow slowly and form coral-like textures.
5/345	Long life	Studied by Andrew Trevorrow, has very high period oscillators
5678/35678	Diamoeba	A chaotic pattern that forms large diamonds with chaotically oscillating boundaries. Known to have quadratically-growing patterns.

External links

• Cellular automaton at the Life Lexicon