Life-like cellular automaton

Last updated

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:

Contents

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 Diamonds.png
Chaotic diamonds in the Diamoeba (B35678/S5678) rule
Exploding chaos in the Seeds (B2/S) rule Seeds.png
Exploding chaos in the Seeds (B2/S) rule
Conway's Game of Life (B3/S23) Conway.png
Conway's Game of Life (B3/S23)
Anneal (B4678/S35678) Anneal CA.png
Anneal (B4678/S35678)

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
RuleNameDescription and sources
B1357/S1357Replicator 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/S4This 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/S3434 LifeWas 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/S5678DiamoebaForms 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/S1252x2If 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/S245MorleyNamed after Stephen Morley; also called Move. Supports very high-period and slow spaceships. [2] [4] [18]
B4678/S35678AnnealAlso called the twisted majority rule. Symmetric under on-off reversal. Approximates the curve-shortening flow on the boundaries between live and dead cells. [19] [20] [21]

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]

Any automaton of the above form that does not include any of B0, B1, B2 or B3 cannot support movement or expansion of patterns because any cell outside a rectangular building box containing the pattern has at most three on neighbours. Most finite patterns in rules whose notation begins with B2, and all finite patterns in rules beginning with B1, grow in all directions rather than remaining of bounded size, with a front that moves at the speed of light. Thus, the remaining "interesting" rules are the ones beginning with B3 (Game of Life, Highlife, Morley, 2x2, Day&Night) or beginning with B0 (and not including S8, as otherwise the dual can be studied instead). [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 neighborhoods are larger than the Moore neighborhood, or they are defined on three-dimensional lattices, or they use a different lattice topology. For example:

Related Research Articles

<span class="mw-page-title-main">Conway's Game of Life</span> Two-dimensional cellular automaton devised by J. H. Conway in 1970

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves. It is Turing complete and can simulate a universal constructor or any other Turing machine.

<span class="mw-page-title-main">Cellular automaton</span> Discrete model studied in computer science

A cellular automaton is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling.

<span class="mw-page-title-main">Rule 110</span> Elementary cellular automaton

The Rule 110 cellular automaton is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to Conway's Game of Life. Like Life, Rule 110 with a particular repeating background pattern is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.

<span class="mw-page-title-main">Highlife (cellular automaton)</span> 2D cellular automaton similar to Conways Game of Life

Highlife is a cellular automaton similar to Conway's Game of Life. It was devised in 1994 by Nathan Thompson. It is a two-dimensional, two-state cellular automaton in the "Life family" and is described by the rule B36/S23; that is, a cell is born if it has 3 or 6 neighbors and survives if it has 2 or 3 neighbors. Because the rules of HighLife and Conway's Life are similar, many simple patterns in Conway's Life function identically in HighLife. More complicated engineered patterns for one rule, though, typically do not work in the other rule.

<span class="mw-page-title-main">Spaceship (cellular automaton)</span> Type of pattern that periodically changes position

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

<span class="mw-page-title-main">Seeds (cellular automaton)</span> 2D cellular automaton similar to Conways Game of Life

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 an infinite two-dimensional grid of cells, each of which may be in one of two states: on or off. Each cell is considered to have eight neighbors, as in Life. In each time step, a cell turns on or is "born" if it was off or "dead" but had exactly two neighbors that were on; all other cells turn off. Thus, in the notation describing the family of cellular automata containing Life, it is described by the rule B2/S.

<span class="mw-page-title-main">Garden of Eden (cellular automaton)</span> Pattern that has no predecessors

In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. It can be the initial configuration of the automaton but cannot arise in any other way. John Tukey named these configurations after the Garden of Eden in Abrahamic religions, which was created out of nowhere.

<span class="mw-page-title-main">Block cellular automaton</span> Kind of cellular automaton

A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell. Block cellular automata are useful for simulations of physical quantities, because it is straightforward to choose transition rules that obey physical constraints such as reversibility and conservation laws.

<span class="mw-page-title-main">Rule 30</span> Elementary cellular automaton

Rule 30 is an elementary cellular automaton introduced by Stephen Wolfram in 1983. Using Wolfram's classification scheme, Rule 30 is a Class III rule, displaying aperiodic, chaotic behaviour.

Wolfram code is a widely used numbering system for one-dimensional cellular automaton rules, introduced by Stephen Wolfram in a 1983 paper and popularized in his book A New Kind of Science.

<span class="mw-page-title-main">Cyclic cellular automaton</span>

A cyclic cellular automaton is a kind of cellular automaton rule developed by David Griffeath and studied by several other cellular automaton researchers. In this system, each cell remains unchanged until some neighboring cell has a modular value exactly one unit larger than that of the cell itself, at which point it copies its neighbor's value. One-dimensional cyclic cellular automata can be interpreted as systems of interacting particles, while cyclic cellular automata in higher dimensions exhibit complex spiraling behavior.

<span class="mw-page-title-main">Rule 184</span> Elementary cellular automaton

Rule 184 is a one-dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems:

<span class="mw-page-title-main">Rule 90</span> Elementary cellular automaton

In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. In each time step all values are simultaneously replaced by the XOR of their two neighboring values. Martin, Odlyzko & Wolfram (1984) call it "the simplest non-trivial cellular automaton", and it is described extensively in Stephen Wolfram's 2002 book A New Kind of Science.

The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlund credited Curtis and Lyndon as co-discoverers. It has been called "one of the fundamental results in symbolic dynamics".

<span class="mw-page-title-main">Brian's Brain</span> 2D cellular automaton devised by Brian Silverman

Brian's Brain is a cellular automaton devised by Brian Silverman, which is very similar to his Seeds rule.

<span class="mw-page-title-main">Life without Death</span> 2D cellular automaton similar to Conways Game of Life

Life without Death is a cellular automaton, similar to Conway's Game of Life and other Life-like cellular automaton rules. In this cellular automaton, an initial seed pattern grows according to the same rule as in Conway's Game of Life; however, unlike Life, patterns never shrink. The rule was originally considered by Toffoli & Margolus (1987), who called it "Inkspot"; it has also been called "Flakes". In contrast to the more complex patterns that exist within Conway's Game of Life, Life without Death commonly features still life patterns, in which no change occurs, and ladder patterns, that grow in a straight line.

<span class="mw-page-title-main">Reversible cellular automaton</span> Cellular automaton that can be run backwards

A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells. The time-reversed dynamics of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood.

<span class="mw-page-title-main">Golly (program)</span> Tool for simulating cellular automata

Golly is a tool for the simulation of cellular automata. It is free open-source software written by Andrew Trevorrow and Tomas Rokicki; it can be scripted using Lua or Python. It includes a hashlife algorithm that can simulate the behavior of very large structured or repetitive patterns such as Paul Rendell's Life universal Turing machine, and that is fast enough to simulate some patterns for 232 or more time units. It also includes a large library of predefined patterns in Conway's Game of Life and other rules.

<span class="mw-page-title-main">Critters (cellular automaton)</span>

Critters is a reversible block cellular automaton with similar dynamics to Conway's Game of Life, first described by Tommaso Toffoli and Norman Margolus in 1987.

<span class="mw-page-title-main">Replicator (cellular automaton)</span> Type of pattern that infinitely produces copies of itself

In cellular automata, a replicator is a pattern that produces copies of itself.

References

  1. Wolfram, Stephen; Packard, N. H. (1985), "Two-dimensional cellular automata", Journal of Statistical Physics, 38 (5–6): 901–946, Bibcode:1985JSP....38..901P, doi:10.1007/BF01010423 Reprinted in Wolfram, Stephen (1994), Cellular Automata and Complexity, Westview Press, pp. 211–249, ISBN   978-0-201-62664-3 .
  2. 1 2 3 4 5 6 7 8 9 10 11 Wójtowicz, Mirek, Cellular Automaton Rules Lexicon — Family: Life, Mirek's Cellebration.
  3. 1 2 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   978-1-905986-31-6 .
  4. 1 2 3 4 5 6 7 8 9 10 11 Eppstein, David (2010), "Growth and decay in life-like cellular automata", in Adamatzky, Andrew (ed.), 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   978-0-8092-5202-2 .
  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 , MR   1634709 .
  15. Johnston, Nathaniel (2010), "The B36/S125 "2x2" Life-Like Cellular Automaton", in Adamatzky, Andrew (ed.), Game of Life Cellular Automata, Springer, pp. 99–114, arXiv: 1203.1644 , Bibcode:2010golc.book...99J, doi:10.1007/978-1-84996-217-9_7, ISBN   978-1-84996-216-2 .
  16. Bell, David, HighLife - An Interesting Variant of Life .
  17. Bell, David, Day & Night - An Interesting Variant of Life .
  18. Morley, Stephen (2005), b368s245 Guns, archived from the original on 2006-03-11.
  19. Vichniac, Gérard Y. (1986), "Cellular automata models of disorder and organization", in Bienenstock, E.; Fogelman Soulié, F.; Weisbuch, G. (eds.), Disordered Systems and Biological Organization, NATO ASI Series, vol. 20, Springer-Verlag, pp. 3–20, doi:10.1007/978-3-642-82657-3_1 .
  20. Pickover, Clifford A. (1993), "Lava lamps in the 21st century", The Visual Computer, 10 (3): 173–177, doi:10.1007/bf01900906 .
  21. Chopard, Bastien; Droz, Michel (1998), "2.2.4 The annealing rule", Cellular automata modeling of physical systems, Collection Aléa-Saclay: Monographs and Texts in Statistical Physics, Cambridge University Press, Cambridge, pp. 37–38, doi:10.1017/CBO9780511549755, ISBN   0-521-46168-5, MR   1669736 .
  22. Sapin, Emmanuel (2010), "Larger than Life: threshold-range scaling of Life's coherent structures", in Adamatzky, Andrew (ed.), Game of Life Cellular Automata, pp. 135–165, doi:10.1007/978-1-84996-217-9_9
  23. Evans, Kellie Michele (2003), "Larger than Life: threshold-range scaling of Life's coherent structures", Physica D, 183 (1–2): 45–67, Bibcode:2003PhyD..183...45E, doi:10.1016/S0167-2789(03)00155-6 .
  24. 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 .
  25. 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.
  26. 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.
  27. Bays, Carter (2005), "A note on the game of life in hexagonal and pentagonal tessellations", Complex Systems, 15 (3): 245–252.