# Life-like cellular automaton

Life-like cellular automaton

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 array of cells of the automaton has two dimensions.
• Each cell of the automaton has two states (conventionally referred to as "alive" and "dead", or alternatively "on" and "off")
• The neighborhood of each cell is the Moore neighborhood; it consists of the eight adjacent cells to the one under consideration and (possibly) the cell itself.
• In each time step of the automaton, the new state of a cell can be expressed as a function of the number of adjacent cells that are in the alive state and of 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 (B3/S23), the most famous cellular automaton, which meets all of these criteria. 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".

## 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.[1] 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.[2][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".[4]

## A selection of Life-like rules

Chaotic diamonds in the Diamoeba (B35678/S5678) rule
Exploding chaos in the Seeds (B2/S) rule
Conway's Game of Life (B3/S23)

There are 218 = 262,144 possible Life-like rules, only a small fraction of which have been studied in any detail. In the descriptions below, all rules are specified in Golly/RLE format.

Notable Life-like rules
Rule Name Description and sources
B1357/S1357 Replicator Edward Fredkin's replicating automaton: every pattern is eventually replaced by multiple copies of itself.[2][3][4]
B2/S Seeds All patterns are phoenixes, meaning that every live cell immediately dies, and many patterns lead to explosive chaotic growth. However, some engineered patterns with complex behavior are known.[2][5][6]
B25/S4 This rule supports a small self-replicating pattern which, when combined with a small glider pattern, causes the glider to bounce back and forth in a pseudorandom walk.[4][7]
B3/S012345678 Life without Death Also known as Inkspot or Flakes. Cells that become alive never die. It combines chaotic growth with more structured ladder-like patterns that can be used to simulate arbitrary Boolean circuits.[2][4][8][9]
B3/S23 Life Highly complex behavior.[10][11]
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.[2][12][13]
B35678/S5678 Diamoeba Forms large diamonds with chaotically fluctuating boundaries. First studied by Dean Hickerson, who in 1993 offered a \$50 prize to find a pattern that fills space with live cells; the prize was won in 1999 by David Bell.[2][4][14]
B36/S125 2x2 If a pattern is composed of 2x2 blocks, it will continue to evolve in the same form; grouping these blocks into larger powers of two leads to the same behavior, but slower. Has complex oscillators of high periods as well as a small glider.[2][15]
B36/S23 HighLife Similar to Life but with a small self-replicating pattern.[2][4][16]
B3678/S34678 Day & Night Symmetric under on-off reversal. Has engineered patterns with highly complex behavior.[2][4][17]
B368/S245 Morley Named after Stephen Morley; also called Move. Supports very high-period and slow spaceships.[2][4][18]

Several more rules are listed and described in the MCell rule list[2] and by Eppstein (2010), including some rules with B0 in which the background of the field of cells alternates between live and dead at each step.[4]

Any automaton of the above form that contains the element B1 (e.g. B17/S78, or B145/S34) 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.[4]

## Generalizations

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. These automata have eerily organic `glider' and `blinker' structures.[19]
• 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 R2, not the discrete lattice Z2. They have been studied by Marcus Pivato.[20]
• Carter Bays has proposed a variety of generalizations of the Game of Life to three-dimensional CA defined on Z3.[21] Bays has also studied two-dimensional life-like CA with triangular or hexagonal neighbourhoods.[22][23]

## References

1. ^ Wolfram, Stephen; Packard, N. H. (1985), "Two-dimensional cellular automata", Journal of Statistical Physics 38 (5–6): 901–946, doi:10.1007/BF01010423  Reprinted in Wolfram, Stephen (1994), Cellular Automata and Complexity, Westview Press, pp. 211–249, ISBN 9780201626643 .
2. ^ a b c d e f g h i j k  .
3. ^ a b Wuensche, Andrew (2011), "16.10 The game-of-Life and other Life-like rules – rcode", Exploring Discrete Dynamics: The DDLAB manual, Luniver Press, pp. 145–146, ISBN 9781905986316 .
4. ^ a b c d e f g h i j Eppstein, David (2010), "Growth and decay in life-like cellular automata", in Adamatzky, Andrew, Game of Life Cellular Automata, Springer, pp. 71–98, arXiv:0911.2890, doi:10.1007/978-1-84996-217-9_6, ISBN 978-1-84996-216-2 .
5. ^ Silverman, Brian, "Changing the Rules", The Virtual Computer, Mathematical Association of America .
6. ^ Patterns for Seeds collected by Jason Summers.
7. ^ Nivasch, Gabriel (2007), The photon/XOR system .
8. ^ Toffoli, Tommaso; Margolus, Norman (1987), "1.2 Animate-by-numbers", Cellular Automata Machines: A New Environment for Modeling, MIT Press, pp. 6–7 .
9. ^ Griffeath, David; Moore, Cristopher (1996), "Life without Death is P-complete", Complex Systems 10: 437–447 .
10. ^ Gardner, Martin (October 1970), "Mathematical Games - The fantastic combinations of John Conway's new solitaire game "life"", Scientific American 223: 120–123 .
11. ^ Berlekamp, E. R.; Conway, John Horton; Guy, R.K. (2004), Winning Ways for your Mathematical Plays (2nd ed.), A K Peters Ltd .
12. ^ Poundstone, William (1985), The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge, Contemporary Books, p. 134, ISBN 9780809252022 .
13. ^ Eisenmann, Jack, 34 LIFE .
14. ^ Gravner, Janko; Griffeath, David (1998), "Cellular automaton growth on Z2: theorems, examples, and problems", Advances in Applied Mathematics 21 (2): 241–304, doi:10.1006/aama.1998.0599, MR1634709 .
15. ^ Johnston, Nathaniel (2010), "The B36/S125 “2x2” Life-Like Cellular Automaton", in Adamatzky, Andrew, Game of Life Cellular Automata, Springer, pp. 99–114, doi:10.1007/978-1-84996-217-9_7, ISBN 978-1-84996-216-2 .
16. ^  .
17. ^  .
18. ^ Morley, Stephen (2005), b368s245 Guns .
19. ^ 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 .
20. ^ Pivato, Marcus (2007), "RealLife: the continuum limit of Larger than Life cellular automata", Theoretical Computer Science 372 (1): 46–68, arXiv:math.DS/0503504, doi:10.1016/j.tcs.2006.11.019 .
21. ^ 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 .
22. ^ 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 .
23. ^ Bays, Carter (2005), "A note on the game of life in hexagonal and pentagonal tessellations", Complex Systems 15 (3): 245–252 .

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Cellular automaton — A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, theoretical biology and microstructure modeling. It consists of a regular grid of cells , each in one of a finite number of states …   Wikipedia

• Rake (cellular automaton) — A rake in a cellular automaton is a puffer that, instead of leaving behind a trail of debris, emits a stream of spaceships. [ [http://www.argentum.freeserve.co.uk/lex r.htm#rake Rake, Life lexicon] .… …   Wikipedia

• Spaceship (cellular automaton) — In a cellular automaton, a finite pattern is called a spaceship if it reappears after a certain number of generations in the same orientation but in a different position. The smallest such number of generations is called the period of the… …   Wikipedia

• Quantum dot cellular automaton — Quantum Dot Cellular Automata (sometimes referred to simply as quantum cellular automata, or QCA) Any device designed to represent data and perform computation, regardless of the physics principles it exploits and materials used to build it, must …   Wikipedia

• Asynchronous cellular automaton — Cellular automata, as with other multi agent system models, usually treat time as discrete and state updates as occurring synchronously. The state of every cell in the model is updated together, before any of the new states influence other cells …   Wikipedia

• Block cellular automaton — The Margolus neighborhood for a two dimensional block cellular automaton. The partition of the cells alternates between the set of 2 × 2 blocks indicated by the solid blue lines, and the set of blocks indicated by the dashed red lines. A block… …   Wikipedia

• Seeds (cellular automaton) — Seeds is a cellular automaton in the same family as the Game of Life, initially investigated by Brian Silverman and named by Mirek Wójtowicz. It consists of infinite two dimensional grid of cells, each of which may be in one of two states: on or… …   Wikipedia

• Gun (cellular automaton) — In a cellular automaton, a gun is a pattern of which the main part repeats periodically, like an oscillator and which also periodically emits spaceships. There are then two periods that may be considered. There is the period of the spaceship… …   Wikipedia

• Conway's Game of Life — Conway game , which redirects to here, can also refer to games as defined by surreal numbers, which John Conway also developed …   Wikipedia

• History of artificial life — The idea of human artifacts being given life has fascinated mankind for as long as men have been recording their myths and stories. Whether Pygmalion or Frankenstein, mankind has been fascinated with the idea of artificial life. Pre computer… …   Wikipedia