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 Zn (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 Zn. 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 SN 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 Zn, 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 common to refer to it as the "Life family" or to simply use phrases like "similar to Life".
A common notation used to describe these automata is referred to as "S/B". 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.
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/1 | Wolfram Fig. 7(e) | |
| 012345678/3 | Flakes, Life without Death | Ladder-like patterns can be used to simulate arbitrary Boolean circuits |
| 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 | Investigated by Kellie Evans; forms interesting patterns starting even from such simple seeds as a single live cell |
| 12345/3 | Maze | Forms maze-like designs |
| 12456/0578 | Wolfram Fig. 7(h) | |
| 125/36 | 2x2 | If a pattern is composed of 2x2 blocks, it will continue to evolve in the same form. Has many oscillators and spaceships |
| 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 | Well balanced between life and death; forms patterns with chaotic interiors and wildly vacillating boundaries. Has spaceships |
| 23/3 | Life | 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 | Patterns tend to expand forever in contrast to the nearby rule Stains |
| 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 | Was initially thought to be a stable alternative to Life, until computer simulation found that larger patterns tend to explode. Has many small oscillators and spaceships |
| 34678/3678 | Day & Night | Symmetric under on-off reversal. Has engineered patterns with highly complex behavior |
| 4567/345 | Assimilation | Forms permanent diamond shaped patterns with partially filled interiors |
| 45678/137 | Wolfram Fig. 7(f) | |
| 45678/3 | Coral | Patterns grow slowly forming coral-like textures |
| 5/345 | Long life | Studied by Andrew Trevorrow, has very high period oscillators |
| 5678/35678 | Diamoeba | Forms large diamonds with chaotically oscillating boundaries, first studied by Dean Hickerson. Gravner and Griffeath posed the existence of quadratic growth patterns as an open problem, later solved by Hickerson |
External links
- Cellular automaton at the Life Lexicon