Cellular automaton

From LifeWiki
Revision as of 19:12, 3 March 2009 by Nathaniel (talk | contribs) (→Life-like cellular automata: added more info, generally cleaned up)
Jump to navigation Jump to search

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