Still life (CA)

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.

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

2, 1, 5, 4, 9, 10, 25, 46, 121, 240, 619, 1353, ... (sequence A019473 in OEIS).

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.