Difference between revisions of "Still life"
Apple Bottom (talk | contribs) (Figures for 29- and 30-bitters) |
Apple Bottom (talk | contribs) (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.) |
||
Line 24: | Line 24: | ||
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== | |||
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]]: | |||
{| | |||
|- | |||
|[[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:Blockade.png|framed|[[Blockade]] is a fake still life because the four blocks do not interact in any way.]] | |||
|} | |||
==Enumerating still lifes== | ==Enumerating still lifes== |
Revision as of 15:00, 15 January 2017
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.
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] 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]
Fake still lifes
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:
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 A019473 and A056613, respectively.
|
|
See also
- List of common still lifes
- List of pseudo still lifes
- List of still lifes
- List of strict still lifes
References
- ↑ 1.0 1.1 Nivasch, Gabriel (July, 2001). "Still lifes". Retrieved on March 23, 2016.
- ↑ 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.
- ↑ Cook, Matthew. "Still Life". Mathematical Sciences Research Institute.
External links
- Life Object Counts at Mark D. Niemiec's Life Page