Still life

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 strict still lifes.

Strict still lifes

A strict still life is a still life that is either connected (i.e., has no islands), 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 table on 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.

File:Tableontable sideways.png Table on 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, table on 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.

Pseudo still life that can be partitioned into three to five independent stable subpatterns, but not two. RLE: here

Pseudo still life that can be partitioned into four still lifes, but not two or three. RLE: here

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 constellation is not, strictly speaking, a still life; instead, the term is used for patterns composed of two or more non-interacting objects. This contrasts with pseudo 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 are influenced by both.

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

Enumerating still lifes

The number of strict and pseudo still lifes that exist for a given number of cells has been enumerated up to 24. 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-32 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-32 cells). The values in the tables below are given by Sloane's  A019473 and  A056613, respectively.

Live cells # of strict still lifes Examples List 1 0 2 0 3 0 4 2 block, tub Full list 5 1 boat Full list 6 5 beehive, ship Full list 7 4 eater 1, loaf Full list 8 9 canoe, pond Full list 9 10 hat, integral sign Full list 10 25 boat-tie, loop Full list 11 46 elevener Full list 12 121 honeycomb, table on table Partial list 13 240 sesquihat Partial list 14 619 fourteener, paperclip Partial list 15 1,353 moose antlers Partial list 16 3,286 bi-cap, scorpion Partial list 17 7,773 twin hat Partial list 18 19,044 dead spark coil Partial list 19 45,759 eater 2 Partial list 20 112,243 spiral Partial list 21 273,188 very^7 long boat Partial list 22 672,172 cis-mirrored worm Partial list 23 1,646,147 very^8 long boat Partial list 24 4,051,732 lake 2 Partial list 25 9,971,377 very^9 long boat Partial list 26 24,619,307 Mickey Mouse Partial list 27 60,823,008 Vase siamese hat Partial list 28 150,613,157 Tetraloaf I Partial list 29 373,188,952 30 926,068,847 31 2,299,616,637 32 5,716,948,683

Live cells # of pseudo still lifes Examples List 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 1 bi-block Complete list 9 1 block on boat Complete list 10 7 bi-boat Partial list 11 16 12 55 13 110 14 279 15 620 16 1,645 pond on pond Partial list 17 4,067 18 10,843 19 27,250 20 70,637 21 179,011 22 462,086 23 1,184,882 24 3,069,135 25 7,906,676 26 20,463,274 27 52,816,265 28 136,655,095 29 353,198,379 30 914,075,620 31 2,364,815,358 32 6,123,084,116 triple pseudo still life Partial list

See also

• List of common still lifes
• List of pseudo still lifes
• List of still lifes
• List of strict still lifes

External links

• Life Object Counts at Mark D. Niemiec's Life Page