Life-like cellular automaton
Template:Short description A cellular automaton (CA) is Template:Not a typo (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 rulesEdit
There are three standard notations for describing these rules, that are similar to each other but incompatible. Template:Harvtxt 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.<ref>Template:Citation Reprinted in Template:Citation.</ref> 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.<ref name="mirekw">Template:Citation.</ref><ref name="wuensche">Template:Citation.</ref>
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".<ref name="e10"/>
A selection of Template:Not a typo rulesEdit
There are 218 = 262,144 possible Template:Not a typo 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.
| Rule | Name | Description and sources |
|---|---|---|
| B1357/S1357 | Replicator | Edward Fredkin's replicating automaton: every pattern is eventually replaced by multiple copies of itself.<ref name="mirekw"/><ref name="wuensche"/><ref name="e10"/> |
| 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.<ref name="mirekw"/><ref>Template:Citation.</ref><ref>Patterns for Seeds collected by Jason Summers.</ref> |
| 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.<ref name="e10"/><ref>Template:Citation.</ref> | |
| 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.<ref name="mirekw"/><ref name="e10"/><ref>Template:Citation.</ref><ref>Template:Citation.</ref> |
| B3/S23 | Life | Highly complex behavior.<ref>Template:Citation.</ref><ref>Template:Citation.</ref> |
| 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.<ref name="mirekw"/><ref>Template:Citation.</ref><ref>Template:Citation.</ref> |
| 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.<ref name="mirekw"/><ref name="e10"/><ref>Template:Citation.</ref> |
| 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.<ref name="mirekw"/><ref>Template:Citation.</ref> |
| B36/S23 | HighLife | Similar to Life but with a small self-replicating pattern.<ref name="mirekw"/><ref name="e10"/><ref>Template:Citation.</ref> |
| B3678/S34678 | Day & Night | Symmetric under on-off reversal. Has engineered patterns with highly complex behavior.<ref name="mirekw"/><ref name="e10"/><ref>Template:Citation.</ref> |
| B368/S245 | Morley | Named after Stephen Morley; also called Move. Supports very high-period and slow spaceships.<ref name="mirekw"/><ref name="e10"/><ref>Template:Citation.</ref> |
| 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.<ref>Template:Citation.</ref><ref>Template:Citation.</ref><ref>Template:Citation.</ref> |
Several more rules are listed and described in the MCell rule list<ref name="mirekw"/> and by Template:Harvtxt, including some rules with B0 in which the background of the field of cells alternates between live and dead at each step.<ref name="e10">Template:Citation.</ref>
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.<ref name="e10"/>
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).<ref name="e10"/>
GeneralizationsEdit
There are other cellular automata which are inspired by the Game of Life, but which do not fit the definition of "Template:Not a typo" 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.Template: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.<ref>Template:Citation</ref>
- 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.<ref>Template:Citation.</ref>
- 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.<ref>Template:Citation.</ref>
- 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).<ref>Template:Citation.</ref> Bays has also studied two-dimensional Template:Not a typo CA with triangular or hexagonal neighborhoods.<ref>Template:Citation.</ref><ref>Template:Citation.</ref>