fbpx
Wikipedia

Life-like cellular automaton

March 16, 2024

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 edit

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 edit

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

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:

  • Non-totalistic rules depend on the configuration of live cells in the neighborhood.
    • Non-isotropic rules that behave differently in different directions. There are 2512≈1.34*10154 rules of this kind, including isotropic rules.[citation needed]
    • Isotropic non-totalistic rules behave identically under rotation and reflection. There are 2102≈5.07*1030 rules of this kind, including outer-totalistic rules.[22]
  • Generations rules include one or more "dying" states cells switch to instead of instantly dying. The most famous examples in this category are the rules "Brian's Brain" (B2/S/3) and "Star Wars" (B2/S345/4). Random patterns in these two rules feature a large variety of spaceships and rakes with a speed of c, often crashing and combining into even more objects.
  • Larger than Life is a family of cellular automata studied by Kellie Michele Evans. They have very large radius neighborhoods, but perform "birth/death" thresholding similar to Conway's life. These automata have eerily organic "glider" and "blinker" structures.[23]
  • RealLife is the continuum limit of Evan's Larger Than Life CA, in the limit as the neighborhood 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.[24]
  • Lenia is a family of continuous cellular automata created by Bert Wang-Chak Chan. The space, time and states of the Game of Life are generalized to continuous domains, using large neighborhoods, fractional updates, and real number states, respectively.
  • Carter Bays has proposed a variety of generalizations of the Game of Life to three-dimensional CA defined on Z3 (3D Life).[25] Bays has also studied two-dimensional life-like CA with triangular or hexagonal neighborhoods.[26][27]

References edit

  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. ^ a b c d e f g h i j k Wójtowicz, Mirek, Cellular Automaton Rules Lexicon — Family: Life, Mirek's Cellebration.
  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 978-1-905986-31-6.
  4. ^ a b c d e f g h i j k 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), , 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.

External links edit

  • Griffeath, David, "Totalistic Growth Rules with Moore Neighborhood", The Primordial Soup Kitchen, Department of Mathematics, University of Wisconsin.
  • Game of Life - Conway and Variants - Online Software Tool

March 16, 2024
life, like, cellular, automaton, cellular, automaton, life, like, sense, being, similar, conway, game, life, meets, following, criteria, array, cells, automaton, dimensions, each, cell, automaton, states, conventionally, referred, alive, dead, alternatively, n. 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 Contents 1 Notation for rules 2 A selection of Life like rules 3 Generalizations 4 References 5 External linksNotation for rules editThere are three standard notations for describing these rules that are similar to each other but incompatible Wolfram amp 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 edit nbsp Chaotic diamonds in the Diamoeba B35678 S5678 rule nbsp Exploding chaos in the Seeds B2 S rule nbsp Conway s Game of Life B3 S23 nbsp 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 Rule Name Description and sourcesB1357 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 amp 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 B4678 S35678 Anneal Also 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 amp Night or beginning with B0 and not including S8 as otherwise the dual can be studied instead 4 Generalizations editThere 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 Non totalistic rules depend on the configuration of live cells in the neighborhood Non isotropic rules that behave differently in different directions There are 2512 1 34 10154 rules of this kind including isotropic rules citation needed Isotropic non totalistic rules behave identically under rotation and reflection There are 2102 5 07 1030 rules of this kind including outer totalistic rules 22 Generations rules include one or more dying states cells switch to instead of instantly dying The most famous examples in this category are the rules Brian s Brain B2 S 3 and Star Wars B2 S345 4 Random patterns in these two rules feature a large variety of spaceships and rakes with a speed of c often crashing and combining into even more objects Larger than Life is a family of cellular automata studied by Kellie Michele Evans They have very large radius neighborhoods but perform birth death thresholding similar to Conway s life These automata have eerily organic glider and blinker structures 23 RealLife is the continuum limit of Evan s Larger Than Life CA in the limit as the neighborhood 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 24 Lenia is a family of continuous cellular automata created by Bert Wang Chak Chan The space time and states of the Game of Life are generalized to continuous domains using large neighborhoods fractional updates and real number states respectively Carter Bays has proposed a variety of generalizations of the Game of Life to three dimensional CA defined on Z3 3D Life 25 Bays has also studied two dimensional life like CA with triangular or hexagonal neighborhoods 26 27 References edit 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 a b c d e f g h i j k Wojtowicz Mirek Cellular Automaton Rules Lexicon Family Life Mirek s Cellebration 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 978 1 905986 31 6 a b c d e f g h i j k 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 Silverman Brian Changing the Rules The Virtual Computer Mathematical Association of America Patterns for Seeds collected by Jason Summers Nivasch Gabriel 2007 The photon XOR system Toffoli Tommaso Margolus Norman 1987 1 2 Animate by numbers Cellular Automata Machines A New Environment for Modeling MIT Press pp 6 7 Griffeath David Moore Cristopher 1996 Life without Death is P complete Complex Systems 10 437 447 Gardner Martin October 1970 Mathematical Games The fantastic combinations of John Conway s new solitaire game life Scientific American 223 120 123 Berlekamp E R Conway John Horton Guy R K 2004 Winning Ways for your Mathematical Plays 2nd ed A K Peters Ltd Poundstone William 1985 The Recursive Universe Cosmic Complexity and the Limits of Scientific Knowledge Contemporary Books p 134 ISBN 978 0 8092 5202 2 Eisenmann Jack 34 LIFE 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 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 Bell David HighLife An Interesting Variant of Life Bell David Day amp Night An Interesting Variant of Life Morley Stephen 2005 b368s245 Guns archived from the original on 2006 03 11 Vichniac Gerard Y 1986 Cellular automata models of disorder and organization in Bienenstock E Fogelman Soulie 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 Pickover Clifford A 1993 Lava lamps in the 21st century The Visual Computer 10 3 173 177 doi 10 1007 bf01900906 Chopard Bastien Droz Michel 1998 2 2 4 The annealing rule Cellular automata modeling of physical systems Collection Alea 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 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 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 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 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 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 2005 A note on the game of life in hexagonal and pentagonal tessellations Complex Systems 15 3 245 252 External links editGriffeath David Totalistic Growth Rules with Moore Neighborhood The Primordial Soup Kitchen Department of Mathematics University of Wisconsin Game of Life Conway and Variants Online Software Tool Retrieved from https en wikipedia org w index php title Life like cellular automaton amp oldid 1171714848, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.