Life-like cellular automaton

From Wikipedia, the free encyclopedia

A cellular automaton (CA) is Life-like (in the sense of being similar to Conway's Game of Life) if it meets the following criteria:

The CA has two dimensions.
The CA has two states (called OFF and ON).
The neighborhood is the Moore neighborhood; it consists of the eight adjacent cells to the one under consideration and (possibly) the cell itself.
The new state of the cell in the next generation can be expressed as a function of the number of adjacent cells that are in the ON state and the cell's own state; that is, the rule is outer totalistic (sometimes called semitotalistic).

There is a notation used to describe these automata. It is written in the form S/B. S (for survival) is a list of all the numbers of states that cause an ON cell to remain ON. B (for birth) is a list of all the numbers of states 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.

As an example, the Seeds rule is described as /2. Thus every ON cell dies in every generation, since the survival list is empty. All OFF cells that had exactly two adjacent ON cells then turn on.

This class of cellular automata is named for the Game of Life (23/3), the most famous cellular automaton. Many different terms are used to describe this class. It is common to refer to it as the "Life family" or to simply use phrases like "similar to Life".

1 A selection of Life-like rules
2 Examples of patterns
- 2.1 125/36
- 2.2 245/3 (245/36)
3 External links
4 References

[edit] A selection of Life-like rules

Chaotic diamonds in the Diamoeba (5678/35678) rule

Exploding chaos in the Seeds (/2) rule

Conway's Game of Life (23/3)

There are far too many possible Life-like rules to list them all here. The following table combines notable rules compiled as part of Mirek's Cellebration with the rules mentioned by Wolfram and some additional named rules.

Notable Life-like rules
Rule	Name	Description or source
/2	Seeds	Chaotic growth; all patterns are phoenixes
/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 on cell
12345/3	Maze	Forms maze-like designs
12456/0578		Wolfram Fig. 7(h)
125/36	2x2	Patterns composed of 2x2 blocks in which all cells have the same state 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
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
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

Note that any automaton of the above form that contains the element /1 (e.g. 78/17, or 34/145) will always be explosive for any finite pattern: at any step, consider the cell (x,y) that has minimum x-coordinate among cells that are on, and among such cells the one with minimum y-coordinate. Then the cell (x-1,y-1) must have exactly one neighbor, and will become on in the next step. Similarly, the pattern must grow at each step in each of the four diagonal directions. Thus, any nonempty starting pattern leads to explosive growth.