Still life

From LifeWiki
Jump to navigation Jump to search
Classification of still lifes (stable patterns). Click to enlarge.

A still life[note 1] (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.

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.[1] 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.[1]

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.[2][3]


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:

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.

The term "quasi still life" was coined by 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.

Live cells Strict still lifes Pseudo still lifes Quasi still lifes
Count (OEISicon light 11px.pngA019473) Examples List Count (OEISicon light 11px.pngA056613) Examples List Count (OEISicon light 11px.pngA330283) 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.46n), while for pseudo still lifes it is around O(2.56n), and approximately O(3.04n) for quasi still lifes.

See also


  1. For the plural form, both "still lifes" and "still lives" are in common use.


  1. 1.0 1.1 Nivasch, Gabriel (July, 2001). "Still lifes". Retrieved on March 23, 2016.
  2. Cook, Matthew (2003). "New Constructions in Cellular Automata: Still life theory, pages 93–118". Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press.
  3. Cook, Matthew. "Still Life". Mathematical Sciences Research Institute.
  4. 4.0 4.1 Simon Ekström (January 2, 2017). Re: Enumerating Still Lifes (in C) (discussion thread) at the forums
  5. 5.0 5.1 Simon Ekström (January 3, 2017). Re: Enumerating Still Lifes (in C) (discussion thread) at the forums
  6. 6.0 6.1 Simon Ekström (January 7, 2017). Re: Enumerating Still Lifes (in C) (discussion thread) at the forums
  7. 7.0 7.1 Simon Ekström (January 14, 2017). Re: Enumerating Still Lifes (in C) (discussion thread) at the forums
  8. 8.0 8.1 Nathaniel Johnston (March 27, 2017). Re: Enumerating Still Lifes (in C) (discussion thread) at the forums
  9. 9.0 9.1 Nathaniel Johnston (May 25, 2017). Re: Enumerating Still Lifes (in C) (discussion thread) at the forums
  10. 10.0 10.1 Nathaniel Johnston (April 5, 2019). Re: Enumerating Still Lifes (in C) (discussion thread) at the forums
  11. 11.0 11.1 Nathaniel Johnston (January 9, 2020). Re: Enumerating Still Lifes (in C) (discussion thread) at the forums
  12. Mark Niemiec (January 15, 2017). Re: Enumerating Still Lifes (in C) (discussion thread) at the forums

External links