Life without Death

Life without Death pattern that creates three ladders and shows the death of two ladders by colliding with a single cell (two different ways), the turning of a ladder and the death of a ladder by colliding with another ladder.
The number of live cells per generation of the pattern shown above demonstrating the monotonic nature of Life without Death.

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";[1] it has also been called "Flakes".[2] 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.

Rules

A cellular automaton is a type of model studied in mathematics and theoretical biology consisting of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off". A pattern in the Life without Death cellular automaton consists of an infinite two-dimensional grid of cells, each of which can be in one of two states: dead or alive. Equivalently, it can be thought of as an array of pixels, each of which may be black and white; in the figures, the white pixels represent live cells while the black pixels represent dead cells. Two of these cells are considered to be neighbors if they are vertically, horizontally, or diagonally adjacent.[3]

Any such pattern changes over a sequence of time steps by applying the following simple rules simultaneously to all cells of the pattern: every cell that was alive in the previous pattern remains alive, every dead cell that has exactly three live neighbors becomes alive itself, and every other dead cell remains dead. That is, in the notation describing Life-like cellular automaton rules, it is rule B3/S012345678: a live cell is born when there are three live neighbors, and a live cell survives with any number of neighbors.

Shoots and ladders

Still life patterns are common in Life without Death: if there is no dead cell with three live neighbors, a pattern will remain unchanging for all future time steps. However, because a cell, once alive, remains alive, the set of live cells grows monotonically throughout the evolution of a pattern, and there can be no oscillators (patterns that cycle through a repeating sequence of shapes), spaceships (patterns that keep the same shape but change position), or the other more complex patterns that exist within Conway's Game of Life.

An example of a fast parasitic shoot running alongside a slower ladder. When the tips of the shoot and of the ladder meet they are both destroyed creating a chaotic mess and sending two shoots back down the original ladder in the opposite direction.

Instead, a common feature in Life without Death patterns is the presence of ladders, patterns that grow in a straight line. A ladder will grow forever unless it runs into some other part of the pattern and is blocked or unless some more quickly-growing pattern overtakes it. The most common ladder pattern is shown in the figure; every twelve steps, the same shape appears at the tip of the ladder, four cells farther from the starting position of the ladder.[4] The speed of the ladder's growth is therefore four cells per twelve steps, or, in Life notation, 4c/12 = c/3; here c represents one unit of distance per time step.[5] Another common pattern (called a "parasitic shoot" by Gravner and Griffeath[4]) advances twice as quickly, at speed 2c/3, along the side of a ladder, eventually blocking the ladder and causing a chaotic explosion.[4][6]

Variant ladders of other speeds were discovered in 2000 by Dean Hickerson, along with some parasitic shoots that are slower than the most common 2c/3 one. Hickerson's ladders grow at speeds 4c/9, 4c/10, and 4c/13.[7]

Simulation of circuits

The ladders in Life without Death can be used to simulate arbitrary Boolean circuits:[6] the presence or absence of a ladder in a certain position may be used to represent a Boolean signal, and different interactions between pairs of ladders, or between ladders and still life patterns, may be used to simulate the 'and', 'or', and 'negation' gates of Boolean logic, as well as the points where two signals cross each other. Therefore, it is P-complete to simulate patterns in the Life without Death rule, meaning it is unlikely that a parallel algorithm exists for a simulation significantly faster than that obtained by a naive parallel algorithm with one processor per cellular automaton cell and one time step per generation of the pattern.[6]

Infinite growth

Seed patterns in the form of balls of radius up to ten typically lead to a still life pattern;[4] however, Gravner[8] suggests that the rule is supercritical, meaning that larger or less-symmetric seeds typically expand forever chaotically. Ladders are a frequent phenomenon on the boundaries of chaotic growth regions.

A pattern in Life without Death is said to fill the plane with positive density if there is some radius r such that every cell of the plane is eventually within distance r of a live cell. The question of whether such infinite growth patterns exist was posed as an open problem by Gravner, Griffeath, and Moore.[4][6] The chaotic patterns common in this rule may fill the plane, but they may also leave large empty rectangular regions framed by ladders, causing them to fail the density condition. However, in 2009 Dean Hickerson found diagonally-expanding patterns that eventually settle down into high-period infinite growth, solving the open problem.[7]

Notes

  1. ↑ Toffoli, Tommaso; Margolus, Norman (1987), "1.2 Animate-by-numbers", Cellular Automata Machines: A New Environment for Modeling, MIT Press, pp. 6–7.
  2. ↑ MCell lexicon of Cellular Automata rules.
  3. ↑ This definition of neighbours is known as the Moore neighborhood
  4. 1 2 3 4 5 Gravner, Janko; David, Griffeath (1998), "Cellular Automaton Growth on Z2: Theorems, Examples, and Problems", Advances in Applied Mathematics 21: 241–304, doi:10.1006/aama.1998.0599.
  5. ↑ The notation c is used, and c is called the speed of light, because it is the fastest speed at which information can propagate across a cellular automaton that uses the Moore neighborhood.
  6. 1 2 3 4 Griffeath, David; Moore, Cristopher (1996), "Life without Death is P-complete", Complex Systems 10: 437–447.
  7. 1 2 Eppstein, David (2009), Faster ladders in Life without Death.
  8. ↑ Gravner, Janko (2003), "Growth phenomena in cellular automata", New Constructions in Cellular Automata, Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press, pp. 161–182

External links

This article is issued from Wikipedia - version of the Friday, May 01, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.