Difference between revisions of "Still life"

From LifeWiki
Jump to navigation Jump to search
(The term "fake still life" is used by Template:Stilllife. Since the question of the difference between fake and pseudo recently came up, explain it here.)
(→‎Enumerating still lifes: We finally have an entry for a 29-bitter.)
(25 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Glossary}}
{{Glossary}}
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|strict still lifes]] and [[#Pseudo still lifes|pseudo still lifes]]. In some contexts, the term "still life" may refer to strict still lifes.
[[File:Still life classification.png|thumb|right|Classification of still lifes (stable patterns). Click to enlarge.|link=http://conwaylife.com/w/images/7/73/Still_life_classification.png]]
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|strict still lifes]] and [[#Pseudo still lifes|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==
==Strict still lifes==
Line 14: Line 15:
A '''pseudo still life''' consists of two or more [[island]]s 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".
A '''pseudo still life''' consists of two or more [[island]]s 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 [[:Category:Patterns found by Gabriel Nivasch|Gabriel Nivasch]] that can be partitioned into a minimum of three and four stable subpatterns, respectively, as in the second and third images below.<ref name="gn_stilllife">{{cite web|url=http://www.gabrielnivasch.org/fun/life/still-lifes |title=Still lifes |author=Nivasch, Gabriel|date=July, 2001|accessdate=March 23, 2016}}</ref> 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.<ref name="gn_stilllife" />
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 [[:Category:Patterns found by Gabriel Nivasch|Gabriel Nivasch]] that can be partitioned into a minimum of three and four stable subpatterns, respectively, as in the second and third images below.<ref name="gn_stilllife">{{cite web|url=http://www.gabrielnivasch.org/fun/life/still-lifes |title=Still lifes |author=Nivasch, Gabriel|date=July, 2001|accessdate=March 23, 2016}}</ref> 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.<ref name="gn_stilllife" />


{|
{|
|-
|-
|[[Image:Biblock.png|framed|[[Bi-block]] is a pseudo still life because each [[block]] is stable by itself.]]
|[[Image:Biblock.png|framed|[[Bi-block]] is a pseudo still life because each [[block]] is stable by itself.]]
|[[Image:Triplepseudostilllife_small.png|framed|Pseudo still life that can be partitioned into three still lifes, but not two. {{JavaRLE|triplepseudostilllife|brief}}]]
|[[Image:Triplepseudostilllife_small.png|center|100px|framed|Pseudo still life that can be partitioned into three to five independent stable subpatterns, but not two. {{JavaRLE|triplepseudostilllife|brief}}]]
|[[Image:Quadpseudostilllife_small.png|framed|Pseudo still life that can be partitioned into four still lifes, but not two or three. {{JavaRLE|quadpseudostilllife|brief}}]]
|[[Image:Quadpseudostilllife_small.png|framed|Pseudo still life that can be partitioned into four still lifes, but not two or three. {{JavaRLE|quadpseudostilllife|brief}}]]
|}
|}
Line 25: Line 26:
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.<ref name="cook">{{cite conference | authorlink = Matthew Cook | author = Cook, Matthew | title = Still life theory | date = 2003 | booktitle = New Constructions in Cellular Automata | publisher = Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press | pages = 93–118}}</ref><ref>{{cite web|url=http://msri.org/publications/ln/msri/2000/gametheory/cook/1/index.html |title=Still Life |author=Cook, Matthew |publisher=Mathematical Sciences Research Institute}}</ref>
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.<ref name="cook">{{cite conference | authorlink = Matthew Cook | author = Cook, Matthew | title = Still life theory | date = 2003 | booktitle = New Constructions in Cellular Automata | publisher = Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press | pages = 93–118}}</ref><ref>{{cite web|url=http://msri.org/publications/ln/msri/2000/gametheory/cook/1/index.html |title=Still Life |author=Cook, Matthew |publisher=Mathematical Sciences Research Institute}}</ref>


==Fake still lifes==
==Constellations==
A '''fake still life''' 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]]:
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]]:


{|
{|
|-
|-
|[[Image:Biblock.png|framed|[[Bi-block]] is a pseudo still life because the two blocks interact: the two dead cells between the [[block]]s are influenced by both.]]
|[[Image:Biblock.png|framed|[[Bi-block]] is a pseudo still life because the two [[block]]s interact: the two dead cells between them are influenced by both.]]
|[[Image:Blockade.png|framed|[[Blockade]] is a fake still life because the four blocks do not interact in any way.]]
|[[Image:Blockade.png|framed|[[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 [[constellation]]s. 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 Game of Life|Conway Life]], this occurs when objects are diagonally adjacent (e.g. two [[block]]s sharing a single diagonal neighbor), or when single protruding cells in two objects such as [[tub]]s share multiple neighbors.
{|
|-
|[[Image:Quasistilllife.png|framed|Two [[block]]s sharing a single diagonal neighbor, marked in green; this cell is dead from underpopulation, and remains so after separation.]]
|}
The term "quasi still life" is due to Mark Niemiec.


==Enumerating still lifes==
==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) and [[Simon Ekström]] (25-28 cells). The values in the pseudo still life table were enumerated by Mark Niemiec (1-24 cells) and Simon Ekström (25-28 cells). The values in the tables below are given by Sloane's {{OEIS|A019473}} and {{OEIS|A056613}}, respectively.
The number of strict and pseudo still lifes that exist for a given number of cells has been enumerated up to 32, 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-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 quasi still life table below were originally computed by [[Mark Niemiec]] (8-20 cells) and Simon Ekström (21-22 cells).<ref name="post39372" />


<table border="0" cellpadding="0" cellspacing="0" width="100%"><tr><td align="center" width="50%">
{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
|-
|-
! Live cells
! rowspan="2" | Live cells
! # of strict still lifes
! colspan="3" | Strict still lifes
! colspan="3" | Pseudo still lifes
! colspan="3" | Quasi still lifes
|-
! Count ({{OEIS|A019473}})
! Examples
! List
! Count ({{OEIS|A056613}})
! Examples
! List
! Count
! Examples
! Examples
! List
! List
|-
|-
|1|| {{A019473|1}} ||||
|1|| {{A019473|1}} || || || {{A056613|1}} || || || 0 || ||  
|-
|2|| {{A019473|2}} ||||
|-
|3|| {{A019473|3}} ||||
|-
|4|| {{A019473|4}} || [[block]], [[tub]] || [[:Category:Strict_still lifes with 4 cells|Full list]]
|-
|5|| {{A019473|5}} || [[boat]] || [[:Category:Strict_still lifes with 5 cells|Full list]]
|-
|6|| {{A019473|6}} || [[beehive]], [[ship]] || [[:Category:Strict_still lifes with 6 cells|Full list]]
|-
|7|| {{A019473|7}} || [[eater 1]], [[loaf]] || [[:Category:Strict_still lifes with 7 cells|Full list]]
|-
|8|| {{A019473|8}} || [[canoe]], [[pond]] || [[:Category:Strict_still lifes with 8 cells|Full list]]
|-
|9|| {{A019473|9}} || [[hat]], [[integral sign]] || [[:Category:Strict_still lifes with 9 cells|Full list]]
|-
|10|| {{A019473|10}} || [[boat-tie]], [[loop]] || [[:Category:Strict_still lifes with 10 cells|Full list]]
|-
|11|| {{A019473|11}} || [[elevener]] ||  [[:Category:Strict_still_lifes_with_11_cells|Full list]]
|-
|12|| {{A019473|12}} || [[honeycomb]], [[table on table]] ||  [[:Category:Strict_still_lifes_with_12_cells|Partial list]]
|-
|13|| {{A019473|13}} || [[sesquihat]] ||  [[:Category:Strict_still_lifes_with_13_cells|Partial list]]
|-
|14|| {{A019473|14}} || [[fourteener]], [[paperclip]] || [[:Category:Strict_still_lifes_with_14_cells|Partial list]]
|-
|15|| {{A019473|15}} || [[moose antlers]] ||  [[:Category:Strict_still_lifes_with_15_cells|Partial list]]
|-
|16|| {{A019473|16}} || [[bi-cap]], [[scorpion]] ||  [[:Category:Strict_still_lifes_with_16_cells|Partial list]]
|-
|17|| {{A019473|17}} || [[twin hat]] ||  [[:Category:Strict_still_lifes_with_17_cells|Partial list]]
|-
|18|| {{A019473|18}} || [[dead spark coil]] ||  [[:Category:Strict_still_lifes_with_18_cells|Partial list]]
|-
|19|| {{A019473|19}} || [[eater 2]] || [[:Category:Strict_still_lifes_with_19_cells|Partial list]]
|-
|20|| {{A019473|20}} || [[spiral]] || [[:Category:Strict_still_lifes_with_20_cells|Partial list]]
|-
|-
|21|| {{A019473|21}} || || [[:Category:Strict_still_lifes_with_21_cells|Partial list]]
|2|| {{A019473|2}} || || || {{A056613|2}} || || || 0 || ||
|-
|-
|22|| {{A019473|22}} || || [[:Category:Strict_still_lifes_with_22_cells|Partial list]]
|3|| {{A019473|3}} || || || {{A056613|3}} || || || 0 || ||
|-
|-
|23|| {{A019473|23}} || || [[:Category:Strict_still_lifes_with_23_cells|Partial list]]
|4|| {{A019473|4}} || [[block]], [[tub]] || [[:Category:Strict still lifes with 4 cells|Full list]] || {{A056613|4}} || || || 0 || ||
|-
|-
|24|| {{A019473|24}} || [[lake 2]] || [[:Category:Strict_still_lifes_with_24_cells|Partial list]]
|5|| {{A019473|5}} || [[boat]] || [[:Category:Strict still lifes with 5 cells|Full list]] || {{A056613|5}} || || || 0 || ||
|-
|-
|25|| {{A019473|25}} || || [[:Category:Strict_still_lifes_with_25_cells|Partial list]]
|6|| {{A019473|6}} || [[beehive]], [[ship]] || [[:Category:Strict still lifes with 6 cells|Full list]] || {{A056613|6}} || || || 0 || ||
|-
|-
|26|| {{A019473|26}} || || [[:Category:Strict_still_lifes_with_26_cells|Partial list]]
|7|| {{A019473|7}} || [[eater 1]], [[loaf]] || [[:Category:Strict still lifes with 7 cells|Full list]] || {{A056613|7}} || || || 0 || ||
|-
|-
|27|| {{A019473|27}} || || [[:Category:Strict_still_lifes_with_27_cells|Partial list]]
|8|| {{A019473|8}} || [[canoe]], [[pond]] || [[:Category:Strict still lifes with 8 cells|Full list]] || {{A056613|8}} || [[bi-block]] || [[:Category:Pseudo still lifes with 8 cells|Full list]] || 6 || ||
|-
|-
|28|| {{A019473|28}} || || [[:Category:Strict_still_lifes_with_28_cells|Partial list]]
|9|| {{A019473|9}} || [[hat]], [[integral sign]] || [[:Category:Strict still lifes with 9 cells|Full list]] || {{A056613|9}} || [[block on boat]] ||  [[:Category:Pseudo still lifes with 9 cells|Full list]] || 13 || ||
|-
|-
|29|| {{A019473|29}} || || [[:Category:Strict_still_lifes_with_29_cells|Partial list]]
|10|| {{A019473|10}} || [[boat-tie]], [[loop]] || [[:Category:Strict still lifes with 10 cells|Full list]] || {{A056613|10}} || [[bi-boat]] || [[:Category:Pseudo still lifes with 10 cells|Partial list]] || 57 || ||
|-
|-
|30|| {{A019473|30}} || || [[:Category:Strict_still_lifes_with_30_cells|Partial list]]
|11|| {{A019473|11}} || [[elevener]] || [[:Category:Strict still lifes with 11 cells|Full list]] || {{A056613|11}} || || || 141 || ||  
|}
</td><td align="center" width="50%">
{| class="wikitable" style="text-align:center"
|-
|-
! Live cells
|12|| {{A019473|12}} || [[honeycomb]], [[table on table]] ||  [[:Category:Strict still lifes with 12 cells|Partial list]] || {{A056613|12}} || || || 465 || ||
! # of pseudo still lifes
! Examples
|-
|-
|1|| {{A056613|1}} ||
|13|| {{A019473|13}} || [[sesquihat]] ||  [[:Category:Strict still lifes with 13 cells|Partial list]] || {{A056613|13}} || || || 1,224 || ||  
|-
|-
|2|| {{A056613|2}} ||
|14|| {{A019473|14}} || [[fourteener]], [[paperclip]] || [[:Category:Strict still lifes with 14 cells|Partial list]]  || {{A056613|14}} || || || 3,956 || ||  
|-
|-
|3|| {{A056613|3}} ||
|15|| {{A019473|15}} || [[moose antlers]] ||  [[:Category:Strict still lifes with 15 cells|Partial list]] || {{A056613|15}} || || || 11,599 || ||  
|-
|-
|4|| {{A056613|4}} ||
|16|| {{A019473|16}} || [[bi-cap]], [[scorpion]] ||  [[:Category:Strict still lifes with 16 cells|Partial list]] || {{A056613|16}} || [[pond on pond]] || [[:Category:Pseudo still lifes with 16 cells|Partial list]] || 36,538 || ||  
|-
|-
|5|| {{A056613|5}} ||
|17|| {{A019473|17}} || [[twin hat]] ||  [[:Category:Strict still lifes with 17 cells|Partial list]] || {{A056613|17}} || || || 107,415 || ||  
|-
|-
|6|| {{A056613|6}} ||
|18|| {{A019473|18}} || [[dead spark coil]] ||  [[:Category:Strict still lifes with 18 cells|Partial list]] || {{A056613|18}} || || || 327,250 || ||  
|-
|-
|7|| {{A056613|7}} ||
|19|| {{A019473|19}} || [[eater 2]] || [[:Category:Strict still lifes with 19 cells|Partial list]] || {{A056613|19}} || || || 972,040 || ||  
|-
|-
|8|| {{A056613|8}} || [[bi-block]]
|20|| {{A019473|20}} || [[spiral]] || [[:Category:Strict still lifes with 20 cells|Partial list]]  || {{A056613|20}} || || || 2,957,488 || ||
|-
|-
|9|| {{A056613|9}} || [[block on boat]]
|21|| {{A019473|21}} || [[very^7 long boat]] || [[:Category:Strict still lifes with 21 cells|Partial list]]  || {{A056613|21}} || || || 8,879,327 || ||
|-
|-
|10|| {{A056613|10}} ||
|22|| {{A019473|22}} || [[cis-mirrored worm]] || [[:Category:Strict still lifes with 22 cells|Partial list]]  || {{A056613|22}} || || || 26,943,317 || ||  
|-
|-
|11|| {{A056613|11}} ||
|23|| {{A019473|23}} || [[very^8 long boat]] || [[:Category:Strict still lifes with 23 cells|Partial list]] || {{A056613|23}} || || || || ||  
|-
|-
|12|| {{A056613|12}} ||
|24|| {{A019473|24}} || [[lake 2]] || [[:Category:Strict still lifes with 24 cells|Partial list]] || {{A056613|24}} || || || || ||  
|-
|-
|13|| {{A056613|13}} ||
|25|| {{A019473|25}} || [[very^9 long boat]] || [[:Category:Strict still lifes with 25 cells|Partial list]] || {{A056613|25}} || || || || ||  
|-
|-
|14|| {{A056613|14}} ||
|26|| {{A019473|26}} || [[Mickey Mouse]] || [[:Category:Strict still lifes with 26 cells|Partial list]] || {{A056613|26}} || || || || ||  
|-
|-
|15|| {{A056613|15}} ||
|27|| {{A019473|27}} || [[Vase siamese hat]] || [[:Category:Strict still lifes with 27 cells|Partial list]] || {{A056613|27}} || || || || ||  
|-
|-
|16|| {{A056613|16}} || [[pond on pond]]
|28|| {{A019473|28}} || [[Tetraloaf I]] || [[:Category:Strict still lifes with 28 cells|Partial list]] || {{A056613|28}} || || || || ||
|-
|-
|17|| {{A056613|17}} ||
|29|| {{A019473|29}} || [[29-bit still-life No. 1]] || [[:Category:Strict still lifes with 29 cells|Partial list]] || {{A056613|29}} || || || || ||  
|-
|-
|18|| {{A056613|18}} ||
|30|| {{A019473|30}} || [[Clips]] || [[:Category:Strict still lifes with 30 cells|Partial list]] || {{A056613|30}} || || || || ||  
|-
|-
|19|| {{A056613|19}} ||
|31|| {{A019473|31}} || [[Aries betwixt two blocks]] || [[:Category:Strict still lifes with 31 cells|Partial list]] || {{A056613|31}} || || || || ||  
|-
|-
|20|| {{A056613|20}} ||
|32|| {{A019473|32}} || [[Inflected 30-great sym]] || [[:Category:Strict still lifes with 32 cells|Partial list]] || {{A056613|32}} || [[triple pseudo still life]] || [[:Category:Pseudo still lifes with 32 cells|Partial list]] || || ||  
|-
|21|| {{A056613|21}} ||
|-
|22|| {{A056613|22}} ||
|-
|23|| {{A056613|23}} ||
|-
|24|| {{A056613|24}} ||
|-
|25|| {{A056613|25}} ||
|-
|26|| {{A056613|26}} ||
|-
|27|| {{A056613|27}} ||
|-
|28|| {{A056613|28}} ||
|-
|29|| {{A056613|29}} ||
|-
|30|| {{A056613|30}} ||
|}
|}
</td></tr></table>
 
As the number of bits increases, these counts goes up exponentially; the rate for strict still lifes is about O(2.46<sup>n</sup>), while for pseudo still lifes it is around O(2.56<sup>n</sup>), and approximately O(3.04<sup>n</sup>) for quasi still lifes.


==See also==
==See also==
Line 181: Line 143:


==References==
==References==
<references />
<references>
<ref name="post39372">{{LinkForumThread
|author = Mark Niemiec
|title  = Re: Enumerating Still Lifes (in C)
|format = ref
|p      = 39372
}}</ref>
</references>


==External links==
==External links==
{{LinkLexicon|lex_s.htm#stilllife|name=Still life}}
{{LinkLexicon|lex_p.htm#pseudostilllife|name=Pseudo still life}}
{{LinkLexicon|lex_q.htm#quasistilllife|name=Quasi still life}}
{{LinkNiemiec|objcount.htm|patternname=Life Object Counts}}
{{LinkNiemiec|objcount.htm|patternname=Life Object Counts}}

Revision as of 10:37, 14 September 2017

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

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

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 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 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 green; 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 32, 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-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 quasi still life table below were originally computed by Mark Niemiec (8-20 cells) and Simon Ekström (21-22 cells).[4]

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 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
9 10 hat, integral sign Full list 1 block on boat Full list 13
10 25 boat-tie, loop Full list 7 bi-boat Partial list 57
11 46 elevener Full list 16 141
12 121 honeycomb, table on table Partial list 55 465
13 240 sesquihat Partial list 110 1,224
14 619 fourteener, paperclip Partial list 279 3,956
15 1,353 moose antlers Partial list 620 11,599
16 3,286 bi-cap, scorpion Partial list 1,645 pond on pond Partial list 36,538
17 7,773 twin hat Partial list 4,067 107,415
18 19,044 dead spark coil Partial list 10,843 327,250
19 45,759 eater 2 Partial list 27,250 972,040
20 112,243 spiral Partial list 70,637 2,957,488
21 273,188 very^7 long boat Partial list 179,011 8,879,327
22 672,172 cis-mirrored worm Partial list 462,086 26,943,317
23 1,646,147 very^8 long boat Partial list 1,184,882
24 4,051,732 lake 2 Partial list 3,069,135
25 9,971,377 very^9 long boat Partial list 7,906,676
26 24,619,307 Mickey Mouse Partial list 20,463,274
27 60,823,008 Vase siamese hat Partial list 52,816,265
28 150,613,157 Tetraloaf I Partial list 136,655,095
29 373,188,952 29-bit still-life No. 1 Partial list 353,198,379
30 926,068,847 Clips Partial list 914,075,620
31 2,299,616,637 Aries betwixt two blocks Partial list 2,364,815,358
32 5,716,948,683 Inflected 30-great sym Partial list 6,123,084,116 triple pseudo still life Partial list

As the number of bits increases, these counts goes up 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

References

  1. 1.0 1.1 Nivasch, Gabriel (July, 2001). "Still lifes". Retrieved on March 23, 2016.
  2. 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. 
  3. Cook, Matthew. "Still Life". Mathematical Sciences Research Institute.
  4. Mark Niemiec. Re: Enumerating Still Lifes (in C) (discussion thread) at the ConwayLife.com forums

External links