Still life (cellular automaton)

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).

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.

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:2, 1, 5, 4, 9, 10, 25, 46, 121, 240, 619, 1353, ... OEIS|id=A019473.

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.

References

*cite conference
authorlink = Matthew Cook
author = Cook, Matthew
title = Still life theory
date = 2003
booktitle = New Constructions in Cellular Automata
publisher = Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press
pages = 93–118

*cite conference
author = Elkies, Noam D.
title = The still life density problem and its generalizations
date = 1998
booktitle = Voronoi's Impact on Modern Science, Book I
publisher = Proc. Inst. Math. Nat. Acad. Sci. Ukraine, vol. 21
pages = 228–253
id = arxiv | archive = math.CO | id = 9905194

*cite web
author = Niemiec, Mark D.
title = Life Still-Lifes
url = http://home.interserv.com/~mniemiec/still.htm