In Conway's Game of Life

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

 and other cellular automata

Cellular automaton

A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...

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

Pseudo still lifes

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

Skew-symmetric graph

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges. The isomorphism is required to be an involution without any fixed points....

.

In Conway's Game of Life

There are many naturally occurring still lifes in Conway's Game of Life

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

. A random initial pattern will leave behind a great deal of debris, containing small oscillators and a large variety of still lifes.

Blocks

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.

Hives

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.

Loaves

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.

Tubs, barges, boats and ships

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.

A pair of boats can be combined to give another still life known as the boat tie (a pun on bow tie

Bow tie

The bow tie is a type of men's necktie. It consists of a ribbon of fabric tied around the collar in a symmetrical manner such that the two opposite ends form loops. Ready-tied bow ties are available, in which the distinctive bow is sewn into shape and the band around the neck incorporates a clip....

, which it superficially resembles). Similarly, a pair of ships can be combined into a ship tie.

Miscellaneous

Eaters and reflectors

Still lifes can be used to modify or destroy other objects. An eater is capable of absorbing a spaceship and returning to its original state after the collision. Many examples exist, with the most notable being the fish-hook, which is capable of absorbing several types of spaceship. A similar device is the reflector, which alters the direction of an incoming spaceship. Eaters and reflectors are not necessarily still lifes, as the term may also apply to oscillators with similar properties.

Number of different patterns

The number of still lifes existing for a given number of live cells has been documented up to a value of 24 .

Live cells	Number of still lifes	Examples
1	0
2	0
3	0
4	2	Block, Tub
5	1	Boat
6	5	Barge, Carrier, Hive, Ship, Snake
7	4	Fish-hook, Loaf, Long boat
8	9	Canoe, Mango, Long barge, Pond
9	10	Integral sign
10	25	Boat tie
11	46
12	121	Ship tie
13	240
14	619	Bi-loaf
15	1353
16	3286
17	7773
18	19044
19	45759	Eater2
20	112243
21	273188
22	672172
23	1646147
24	4051711

Maximum density

The problem of fitting an n×n region with a maximally dense still life has attracted attention as a test case for constraint programming

Constraint programming

Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties...

.
In the limit of an infinitely large grid, no more than half of the cells in the plane can be live.
For finite square grids, greater densities can be achieved. For instance, the maximum density still life within an 8×8 square is a regular grid of nine blocks, with density 36/64 ≈ 0.5624. Optimal solutions are known for squares of size up to 20×20;
Yorke-Smith provides a listing of known finite maximum-density patterns.