Life without death
|Life without death|
|View animated image|
Life without death (or flakes or inkspot) is a Life-like cellular automaton in which live cells never die, and dead cells are born if they have exactly 3 life neighbours. That is, it has rulestring "B3/S012345678". As a result of its evolution rule, patterns never shrink and almost all large random starting patterns expand without bound. In contrast to the more complex patterns that exist within Conway's Game of Life, Life without death commonly features still lifes and ladder patterns that grow in a straight line. It was originally considered by Toffoli and Margolus.
Because it is impossible for cells to die under this rule, patterns such as oscillators and spaceships can not be constructed. Similarly, sawtooths, breeders, fuses, any various types of patterns that are common in Conway's Game of Life are impossible under this rule. The only "usual" types of patterns that occur are still lifes, of which Life without death has plenty. It has one class of patterns that don't occur under standard Life rules – shoots and ladders.
Because a pattern is a still life in this rule if and only if it does not contain a bordering cell with exactly three live neighbours, any pattern that is a still life under the standard Life rules will also be a still life in Life without death. The same applies to other B3-based rules such as 2x2, Move or Day and Night. Even every still life in the maze (B3/S12345) and mazectric (B3/S1234) rules will work as a still life in this rule.
Shoots and ladders
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 following is the most commonly-occurring ladder pattern, which often appears on the boundary of chaotic growth regions:
Every twelve generations, the same shape appears at the tip of the ladder, four cells farther from the starting position of the ladder. The speed of the ladder's growth is therefore c/3. Another common pattern (called a "parasitic shoot" by Gravner and Griffeath) advances twice as quickly, at 2c/3, along the side of a ladder, eventually blocking the ladder and causing a chaotic explosion.
Some 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, 2c/5, and 4c/13.
Simulation of circuits
The ladders in Life without death can be used to simulate arbitrary Boolean circuits: 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 lifes, 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.
Seed patterns of radius up to ten typically evolve into a still life. However, Gravner suggested that the rule is supercritical, meaning that larger random seeds typically expand forever chaotically.
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. 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. In 2009, Dean Hickerson found a quadratic growth pattern that eventually settles down into a predictable pattern, solving the open problem in the affirmative.
- ↑ Cellular automata rules lexicon at Mirek's Cellebration
- ↑ 2.0 2.1 Toffoli, Tommaso; Margolus, Norman (1987), "1.2 Animate-by-numbers", Cellular Automata Machines: A New Environment for Modeling, MIT Press, pp. 6–7.
- ↑ 3.0 3.1 3.2 3.3 3.4 Gravner, Janko; Griffeath, David (1998), "Cellular Automaton Growth on Z2: Theorems, Examples, and Problems", Advances in Applied Mathematics 21: 241–304
- ↑ 4.0 4.1 4.2 4.3 Griffeath, David; Moore, Cristopher (1996), "Life without Death is P-complete", Complex Systems 10: 437–447
- ↑ 5.0 5.1 Eppstein, David (2009), Faster ladders in Life without Death.
- ↑ 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