Still life

Classification of still lifes (stable patterns). Click to enlarge.

A still life (or stable pattern) is a pattern that does not change from one generation to the next, and thus may be thought of as an oscillator with period 1. Still lifes are sometimes assumed to be finite and non-empty. The two main subgroups of still lifes are strict still lifes and pseudo still lifes. In some contexts, the term "still life" may refer to stable objects rather than stable patterns in general, or strict still lifes rather than stable objects in general.

Strict still lifes

A strict still life is a still life that is either connected (i.e., has only one island), or is such that removing one or more its islands destroys the stability of the pattern. For example, beehive with tail is a strict still life because it is connected, and mirrored table is a strict still life because neither of the tables are stable by themselves.

• 

  Beehive is a strict still life because it is connected

• 

  Beehive with tail is a strict still life because it is connected, even though it contains a smaller still life

• 

  Mirrored table is a strict still life because neither table is stable without the other

Pseudo still lifes

A pseudo still life consists of two or more islands which can be partitioned (either individually or as sets) into non-interacting subpatterns which are by themselves each still lifes. Furthermore, there must be at least one dead cell that has more than three alive neighbours in the overall pattern but has less than three alive neighbours in the subpatterns. This final restriction removes patterns such as bakery, blockade and fleet from consideration, as the islands are not "almost touching".

Note that a pattern may have multiple disconnected components and still be a strict (as opposed to pseudo) still life if the disconnected components are dependent on each other for stability (for example, mirrored table above). Some pseudo still lifes have also been found by Gabriel Nivasch that can be partitioned into a minimum of three and four stable subpatterns, respectively, as in the second and third images below. The stable subpatterns themselves may be either strict or pseudo still lifes. It is not possible to construct a pseudo still life that can be partitioned into a minimum of greater than four stable subpatterns because of the four-color theorem.

• 

  Bi-block is a pseudo still life because each block is stable by itself

• 

  triple pseudo still life

• 

  quad pseudo still life

It has been 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.

Constellations

A (stable) constellation is a still life that is composed of two or more non-interacting objects. This contrasts with pseudo and quasi still lifes, in which the objects in question must interact. Compare for instance the bi-block and blockade:

• 

  Bi-block is a pseudo still life because the two blocks interact: the two dead cells between them (highlighted in red) are influenced by both

• 

  Blockade is a constellation because the four blocks do not interact in any way

Certain unstable (e.g. oscillating) patterns are sometimes also referred to as constellations. The term "stable constellation" is used to refer specifically to still life constellations.

Quasi still lifes

A stable constellation in which the constituent objects share dead cells, but where all cells that used to remain dead from under-population in the overall pattern still do so in the constituent objects, is called a quasi still life. In Conway's Life, this occurs when objects are diagonally adjacent (e.g. two blocks sharing a single diagonal neighbor), or when single protruding cells in two objects such as tubs share multiple neighbors.

• 

  Two blocks sharing a single diagonal neighbor, marked in yellow; this cell is dead from underpopulation and remains so after separation

The term "quasi still life" is due to Mark Niemiec.

Enumerating still lifes

The number of strict and pseudo still lifes that exist for a given number of cells has been enumerated up to 34, and the number of quasi still lifes for a given number of cells up to 22.

• The values in the strict still life table below were originally computed by John Conway (4-7 cells), Robert Wainwright (8-10 cells), David Buckingham (11-13 cells), Peter Raynham (14 cells), Mark Niemiec (15-24 cells), Simon Ekström (25-28 cells), Simon Ekström and "Apple Bottom" (29-30 cells), and Nathaniel Johnston (31-34 cells).
• The values in the pseudo still life table were enumerated by Mark Niemiec (1-24 cells), Simon Ekström (25-28 cells), Simon Ekström and "Apple Bottom" (29-30 cells), and Nathaniel Johnston (31-34 cells).
• The values in the quasi still life table below were originally computed by Mark Niemiec (8-20 cells) and Simon Ekström (21-22 cells).

Live cells	Strict still lifes			Pseudo still lifes			Quasi still lifes
	Count ( A019473)	Examples	List	Count ( A056613)	Examples	List	Count ( A330283)	Examples	List
1	0			0			0
2	0			0			0
3	0			0			0
4	2	block, tub	Full list	0			0
5	1	boat	Full list	0			0
6	5	beehive, ship	Full list	0			0
7	4	eater 1, loaf	Full list	0			0
8	9	canoe, pond	Full list	1	bi-block	Full list	6	xs8_g8g252z01
9	10	hat, integral sign	Full list	1	block on boat	Full list	13	xs9_g8o033z01
10	25	boat-tie, loop	Full list	7	cis-bi-boat	Full list	57	xs10_0gg0652z121
11	46	elevener	Full list	16	block on loaf	Full list	141	xs11_0gg0652z321
12	121	honeycomb, mirrored table	Full list	55	xs12_6606996		465	xs12_0gg0653z321
13	240	sesquihat	Partial list	110	xs13_253035ac		1,224	xs13_x6952z653
14	619	fourteener, paperclip	Partial list	279	xs14_ca23z3lo		3,956	xs14_2596zw69a4
15	1,353	moose antlers	Partial list	620	xs15_2lmzold		11,599	xs15_dbwkcz6421
16	3,286	mirrored cap, scorpion	Partial list	1,645	pond on pond		36,538	xs16_2l20kq23z121
17	7,773	twin hat	Partial list	4,067	xs17_4aar0rr		107,415
18	19,044	dead spark coil	Partial list	10,843	xs18_8e12kmz31243		327,250
19	45,759	eater 2	Partial list	27,250	xs19_4aar0ra96		972,040
20	112,243	spiral	Partial list	70,637	xs20_0ml3z0ddz653		2,957,488
21	273,188	tri-loaf 2	Partial list	179,011	xs21_4aar0rahr		8,879,327
22	672,172	cis-mirrored worm	Partial list	462,086	xs22_2lm0mmz343056		26,943,317
23	1,646,147	xs23_259e0ehu0ui		1,184,882	xs23_bd0mkk8z178l8
24	4,051,732	lake 2	Partial list	3,069,135	xs24_gg0gbbg0ggz1101qq1011
25	9,971,377	squid	Partial list	7,906,676	xs25_3lkkl3zrag023z01
26	24,619,307	Mickey Mouse	Partial list	20,463,274	xs26_rhe0ehr0rr
27	60,823,008	hat siamese vase	Partial list	52,816,265	xs27_ciqb96z4aicggzx1221
28	150,613,157	O quad-loaf	Partial list	136,655,095	xs28_69bqic0ciqb96
29	373,188,952	xs29_cc0s2ticz330fgkc	Partial list	353,198,379	xs29_0g8ow31e8gz2fgkc0c871
30	926,068,847	Clips	Partial list	914,075,620	xs30_03lkl3zgbq0qbgz11x11
31	2,299,616,637	Aries betwixt two blocks	Partial list	2,364,815,358	xs32_bd0mk2sgz1785d0mq
32	5,716,948,683	Inflected 30-great sym	Partial list	6,123,084,116	triple pseudo still life	Partial list
33	14,223,867,298	xs33_69b8bb88gz69d1dd11		15,851,861,075	xs33_321fgkcz6a88a6z651156
34	35,422,864,104	Cis-mirrored elf-shoe	Partial list	41,058,173,683	quad pseudo still life	Partial list

As the number of bits increases, these counts increase exponentially; the rate for strict still lifes is about O(2.46ⁿ), while for pseudo still lifes it is around O(2.56ⁿ), and approximately O(3.04ⁿ) for quasi still lifes.

See also

• List of common still lifes
• Pseudo still lifes (category)
• Still lifes (category)
• Strict still lifes (category)
• Object

External links

• Still life at Wikipedia
• Still life at the Life Lexicon
• Pseudo still life at the Life Lexicon
• Quasi still life at the Life Lexicon
• Life Object Counts at Mark D. Niemiec's Life Page