Still life (cellular automaton)
From Wikipedia, the free encyclopedia
In cellular automata, a still life is a pattern that does not change from one generation to the next. A still life can be thought of as an oscillator of period 1. A strict still life is an indecomposable still life pattern, while a pseudo still life is a still life pattern that can be partitioned into two non-interacting subparts (Cook, 2003).
[edit] In Conway's Game of Life
There are many naturally occurring still lifes in Conway's Game of Life. A random initial pattern will leave behind a great deal of debris, containing small oscillators and a large variety of still lifes. The most common still life is the block. Another example is the loaf.
Block
|
Loaf
|
A glider eater
|
Still lifes can also be used to modify or destroy other objects. For example, the eater pictured above is capable of absorbing a glider approaching from the upper left, and returning to its original state after the collision. This is not unique—there are many other eaters.
The distinction between strict still lifes and pseudo still lifes is not always obvious, as a strict still life may have multiple connected components all of which are needed for its stability. However, Cook (2003) has shown that it is possible to determine whether a still life pattern is a strict still life or a pseudo still life in polynomial time by searching for cycles in an associated skew-symmetric graph.
Niemiec lists all still life patterns in the Game of Life up to patterns with 17 live cells. The number of still life patterns with n stable cells (n ≥ 4) is
Elkies (1998) shows that, in the Game of Life, any infinite still life pattern can fill at most half of the cells in the plane.
[edit] References
- Cook, Matthew (2003). "Still life theory". New Constructions in Cellular Automata: 93–118, Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press.
- Elkies, Noam D. (1998). "The still life density problem and its generalizations". Voronoi's Impact on Modern Science, Book I: 228–253, Proc. Inst. Math. Nat. Acad. Sci. Ukraine, vol. 21. arXiv:math.CO/9905194.
- Niemiec, Mark D.. Life Still-Lifes.
