Still life (cellular automaton)

In Conway's Game of Life and other 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 with unit period.

A pseudo still life consists of two or more adjacent islands which can be partitioned (either individually or as sets) into non-interacting subparts, which are also still lifes. This compares with a strict still life, in which the islands depend on one another for stability, and thus cannot be decomposed. The distinction between the two is not always obvious, as a strict still life may have multiple connected components all of which are needed for its stability. However, 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.

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 (i.e. that most likely to be generated from a random initial state) is the block. A pair of blocks placed side-by-side (or bi-block) is the simplest pseudo still life. Blocks are used as components in many complex devices, an example being the Gosper glider gun.

The second most common still life is the hive (or beehive). Hives are frequently created in (non-interacting) sets of four, in a formation known as a honey farm.

The third most common still life is the loaf. Loaves are often found together in a pairing known as a bi-loaf. Bi-loaves themselves are often created in a further (non-interacting) pairing known as a bakery. Two bakeries can extremely rarely form next to each other, forming a set of four loaves known as a tetraloaf alongside two more bi-loafs.

A tub consists of four live cells placed in a diamond shape around a central dead cell. Placing an extra live cell diagonally to the central cell gives another still life, known as a boat. Placing a further live cell on the opposite side gives yet another still life, known as a ship. A tub, a boat or a ship can be extended by adding a pair of live cells, to give a barge, a long-boat or a long-ship respectively. This extension can be repeated indefinitely, to give arbitrarily large structures.

...
Wikipedia