Still life

From LifeWiki

Jump to: navigation, search

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.

Contents

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.
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 (see table on table above). Some pseudo still lifes have also been found that can be partitioned into three or more stable subpatterns, but can not be partitioned into two stable subpatterns (see the second and third images below).

Bi-block is a pseudo still life because each block is stable by itself.
Triple pseudo still life can be partitioned into three still lifes, but not two.
Quad pseudo still life can be partitioned into four still lifes, but not two or three.

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

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) and Mark Niemiec (15-24 cells). The values in the pseudo still life table were enumerated by Mark Niemiec. The values in the tables below are given by Sloane's A019473 and A056613, respectively.

Live cells # of strict still lifes Examples List
10
20
30
42 block, tub Full list
51 boat Full list
65 beehive, ship Full list
74 eater 1, loaf Full list
89 canoe, pond Full list
910 hat, integral sign Full list
1025 boat-tie, loop Full list
1146 elevener Partial list
12121 honeycomb, table on table Partial list
13240 sesquihat Partial list
14619 fourteener, paperclip Partial list
151353 moose antlers Partial list
163286 bi-cap, scorpion Partial list
177773 twin hat Partial list
1819044 dead spark coil Partial list
1945759 eater 2 Partial list
20112243 spiral Partial list
21273188
22672172
231646147
244051711 lake 2 Partial list
Live cells # of pseudo still lifes Examples
10
20
30
40
50
60
70
81 bi-block
91 block on boat
107
1116
1255
13110
14279
15620
161645 pond on pond
174067
1810843
1927250
2070637
21179011
22462086
231184882
243068984

See also

References

  1. Cook, Matthew (2003). "Still life theory". New Constructions in Cellular Automata: 93–118, Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. 
  2. Cook, Matthew. "Still Life". Mathematical Sciences Research Institute.

External links

Personal tools