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

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

Contents 1 Notation for rules 2 A selection of Life-like rules 3 External links 4 References

[edit] Notation for rules

There are three standard notations for describing these rules, that are similar to each other but incompatible. Wolfram & Packard (1985) use the Wolfram code, a decimal number the binary representation of which has bits that correspond to each possible number of neighbors and state of a cell; the bits of this number are zero or one accordingly as a cell with that neighborhood is dead or alive in the next generation. The other two notations unpack the same sequence of bits into a string of characters that is more easily read by a human.

In the notation used by Mirek's Cellebration, a rule is written as a string x/y where each of x and y is a sequence of distinct digits from 0 to 8, in numerical order. The presence of a digit d in the x string means that a live cell with d live neighbors survives into the next generation of the pattern, and the presence of d in the y string means that a dead cell with d live neighbors becomes alive in the next generation. For instance, in this notation, Conway's Game of Life is denoted 23/3.

In the notation used by the Golly open-source cellular automaton package and in the RLE format for storing cellular automaton patterns, a rule is written in the form By/Sx where x and y are the same as in the MCell notation. Thus, in this notation, Conway's Game of Life is denoted B3/S23. The "B" in this format stands for "birth" and the "S" stands for "survival".

In the descriptions below, all rules are specified in Golly/RLE format.

[edit] A selection of Life-like rules

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 Stephen Wolfram and some additional named rules.

Notable Life-like rules

Rule	Name	Description or source
B018/S018		Wolfram & Packard Fig. 13(c); class 2
B0578/S045		Wolfram & Packard Fig. 7(i)
B0578/S12456		Wolfram & Packard Fig. 7(h)
B1/S012345678		Wolfram & Packard Fig. 7(e)
B1/S1	Gnarl	Investigated by Kellie Evans; forms interesting patterns starting even from such simple seeds as a single live cell
B123567/S0238		Wolfram & Packard Fig. 13(f); class 3
B13456/S01356		Wolfram & Packard Fig. 7(d)
B135/S135		Wolfram & Packard Fig. 13(h); class 3
B1357/S1357	Replicator	Edward Fredkin's replicating automaton: every pattern is eventually replaced by multiple copies of itself
B137/S45678		Wolfram & Packard Fig. 7(f)
B2/S	Seeds	Chaotic growth; all patterns are phoenixes. A small collection of complex engineered patterns is known.
B234/S	Serviettes	Lacy patterns
B236/S0468		Wolfram & Packard Figs. 7(a), 13(g); class 3
B257/S27		Wolfram & Packard Fig. 7(b); has spaceships
B3/S012345678	Life without Death	Ladder-like patterns can be used to simulate arbitrary Boolean circuits
B3/S12345	Maze	Forms maze-like designs
B3/S23	Life	Highly complex behavior
B3/S234		Wolfram & Packard Figs. 9(b), 13(b); Class 2. Stable growth; has spaceships
B3/S45678	Coral	Patterns grow slowly forming coral-like textures
B34/S03456		Wolfram & Packard Fig. 7(g)
B34/S34	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
B345/S4567	Assimilation	Forms permanent diamond shaped patterns with partially filled interiors
B345/S5	Long life	Studied by Andrew Trevorrow, has very high period oscillators
B35678/S5678	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
B357/S1358	Amoeba	Well balanced between life and death; forms patterns with chaotic interiors and wildly vacillating boundaries. Has spaceships
B357/S238	Pseudo life	Pattern evolution resembles Life but few patterns from Life work in this rule because the glider is unstable. Has spaceships
B36/S125	2x2	If a pattern is composed of 2x2 blocks, it will continue to evolve in the same form. Has many oscillators and spaceships
B36/S23	HighLife	Similar to Life but with a small self-replicating pattern
B367/S2346		Wolfram & Packard Fig. 9(c). Has spaceships
B3678/S235678	Stains	Patterns quickly stabilize, curiously different from nearby rules. Has spaceships
B3678/S34678	Day & Night	Symmetric under on-off reversal. Has engineered patterns with highly complex behavior
B368/S245	Move	Random patterns tend to stabilize, but has many naturally occurring and engineered spaceships
B378/S012345678		Wolfram & Packard Fig. 9(a)
B378/S235678	Coagulations	Patterns tend to expand forever in contrast to the nearby rule Stains. Has spaceships
B45678/S2345	Walled Cities	Forms centers of activity separated by walls

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.

There are other cellular automata which are inspired by the Game of Life, but which do not fit the definition of `life-like' given in this article, because their neighbourhoods are larger than the Moore neighbourood, or they are defined on three-dimensional lattices, or they use a different lattice topology. For example:

• Larger than Life is a family of cellular automata studied by Kellie Michele Evans. They have very large radius neighbourhoods, but perform `birth/death' thresholding similar to Conway's life. The LtL CA manifest eerily organic `glider' and `blinker' structures.

• RealLife is the “continuum limit″ of Evan's Larger Than Life CA, in the limit as the neighbourhood radius goes to infinity, while the lattice spacing goes to zero. Technically, they are not cellular automata at all, because the underlying “space” is the continuous Euclidean plane R², not the discrete lattice Z². They have been studied by Marcus Pivato.

• Carter Bays has proposed a variety of generalizations of the Game of Life to three-dimensional CA defined on Z³. Bays has also studied two-dimensional life-like CA with triangular or hexagonal neighbourhoods.

[edit] External links

• David Griffeath. "Totalistic Growth Rules with Moore Neighborhood". The Primordial Soup Kitchen. http://psoup.math.wisc.edu/extras/moore/moore.html. 

• George Maydwell. "Life-Like Cellular Automata Rules". Modern Cellular Automata — Live Color Cellular Automata. http://www.collidoscope.com/modernca/lifelikerules.html. 

• Mirek Wójtowicz. "Cellular Automaton Rules Lexicon — Family: Life". Mirek's Cellebration. http://www.mirwoj.opus.chelm.pl/ca/rullex_life.html. 

[edit] References

• Bays, Carter (2007). "The discovery of glider guns in a game of life for the triangular tessellation.". Journal of Cellular Automata 2 (4): 345–350. 

• Bays, Carter (2006). "A note about the discovery of many new rules for the game of three-dimensional life.". Complex Systems 16 (4): 381–386. 

• Bays, Carter (2005). "A note on the game of life in hexagonal and pentagonal tessellations.". Complex Systems 15 (3): 245–252. 

• Bays, Carter (1994). "Further notes on the game of three-dimensional life". Complex Systems 8 (1): 67–73. 

• Bays, Carter (1992). "A new candidate rule for the game of three-dimensional life". Complex Systems 6 (5): 433–441. 

• Bays, Carter (1991). "A new game of three-dimensional life.". Complex Systems 5 (1): 15–18. 

• Bays, Carter (1990). "The discovery of a new glider for the game of three-dimensional life.". Complex Systems 4 (6): 599–602. 

• Bays, Carter (1989). "A note on the discovery of a new game of three-dimensional life.". Complex Systems 2 (3): 255–258. 

• Bays, Carter (1987). "Candidates for the game of Life in three dimensions.". Complex Systems 1 (3): 373–400. 

• Evans, Kellie Michele (2003). "Larger than Life: threshold-range scaling of Life's coherent structures.". Physica D 183 (1-2): 45–67. doi:10.1016/S0167-2789(03)00155-6. 

• Evans, Kellie Michele (2005). "Is Bosco's rule universal?". Machines, computations, and universality,: 189-199, Berlin: Springer-Verlag. 

• Evans, Kellie Michele (2003). "Replicators and larger-than-life examples". New constructions in cellular automata: 119-159, New York: Oxford University Press. 

• Evans, Kellie Michele (2001). "Larger than life: digital creatures in a family of two-dimensional cellular automata". Discrete models: combinatorics, computation, and geometry: 177-191, Paris: Maison Informatique Mathematique Discrète. 

• Pivato, Marcus (2007). "RealLife: the continuum limit of Larger than Life cellular automata.". Theoretical Computer Science 372 (1): 46–68. doi:10.1016/j.tcs.2006.11.019. http://arxiv.org/abs/math.DS/0503504. 

• Wolfram, Stephen; Packard, N. H. (1985). "Two-dimensional cellular automata". Journal of Statistical Physics 38: 901–946. doi:10.1007/BF01010423.  Reprinted in Cellular Automata and Complexity, pp. 211–249.