Still life (cellular automaton)

{{multiple image|image1=Conways game of life two hives.png|caption1=Pseudo still life|width1=82

|image2=Conways game of life table on table.png|caption2=Strict still life|width2=64}}

A pseudo still life consists of two or more adjacent islands (connected components) which can be partitioned (either individually or as sets) into non-interacting subparts, which are also still lifes. This compares with a strict still life, which may not be partitioned in this way. A strict still life may have only a single island, or it may have multiple islands that depend on one another for stability, and thus cannot be decomposed. The distinction between the two is not always obvious, as a strict still life may have multiple connected components all of which are needed for its stability. However, 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.{{cite conference

| author-link = Matthew Cook

| author = Cook, Matthew

| title = Still life theory

| date = 2003

| book-title = New Constructions in Cellular Automata

| publisher = Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press

| pages = 93–118}}

There are many naturally occurring still lifes in Conway's Game of Life. A random initial pattern will leave behind a great deal of debris, containing small oscillators and a large variety of still lifes.

The most common still life (i.e. that most likely to be generated from a random initial state) is the block.{{cite web |author = Achim Flammenkamp |title = Top 100 of Game-of-Life Ash Objects |url = http://wwwhomes.uni-bielefeld.de/achim/freq_top_life.html |access-date=2008-11-05}} A pair of blocks placed side-by-side (or bi-block) is the simplest pseudo still life. Blocks are used as components in many complex devices, an example being the Gosper glider gun.

valign="top" | Image:CGoL Block.PNG | Image:Conways game of life biblock.png

{{clear}}

The second most common still life is the hive (or beehive). Hives are frequently created in (non-interacting) sets of four, in a formation known as a honey farm.

valign="top" | Image:Conways game of life hive.png | Image:Conways game of life honey farm.png

{{clear}}

The third most common still life is the loaf. Loaves are often found together in a pairing known as a bi-loaf. Bi-loaves themselves are often created in a further (non-interacting) pairing known as a bakery. Two bakeries can extremely rarely form next to each other, forming a set of four loaves known as a tetraloaf alongside two more bi-loafs.

valign="top" | Image:CGoL Loaf.PNG | Image:Conways game of life biloaf.png | Image:Conways game of life bakery.png

{{clear}}

A tub consists of four live cells placed in a diamond shape around a central dead cell. Placing an extra live cell diagonally to the central cell gives another still life, known as a boat. Placing a further live cell on the opposite side gives yet another still life, known as a ship. A tub, a boat or a ship can be extended by adding a pair of live cells, to give a barge, a long-boat or a long-ship respectively. This extension can be repeated indefinitely, to give arbitrarily large structures.

valign="top" | Image:Conways game of life barges.png

valign="top" | Image:Conways game of life boats.png

valign="top" | Image:Conways game of life ships.png

A pair of boats can be combined to give another still life known as the boat tie (a pun on "bow tie", which it superficially resembles). Similarly, a pair of ships can be combined into a ship tie.

valign="top" | Image:Conways game of life boat tie.png | Image:Conways game of life ship tie.png

{{clear}}

{{multiple image|image1=Conways game of life fishhook.png|caption1=Fish-hook (eater1)|width1=55

|image2=CGoL Eater.PNG|caption2=eater2|width2=82}}

Still lifes can be used to modify or destroy other objects. A still life is called an eater when it can be used to absorb some other pattern (often a glider, spaceship, or the debris from a more complicated reaction) and returns to its original state after the collision. Many examples exist, with the most notable being the fish-hook (Also known as eater 1), which is capable of absorbing several types of spaceship. A similar device is the 'reflector', which alters the direction of an incoming spaceship. Oscillators with similar properties may also be called eaters or reflectors, but are more difficult to apply as they must be synchronized to the pattern they modify. Still life eaters and reflectors, on the other hand, work correctly regardless of the timing of the pattern they modify, as long as successive reactions occur with enough separation in time to allow the eater or reflector to recover its original shape.

The number of strict and pseudo still lifes in Conway's Game of Life existing for a given number of live cells has been documented up to a value of 34 (sequences {{OEIS link|id=A019473}} and {{OEIS link|id=A056613}} respectively in the On-Line Encyclopedia of Integer Sequences (OEIS)).Number of stable n-celled patterns ("still lifes") in Conway's game of Life {{OEIS|id=A019473}}.Number of n-celled pseudo-still-lifes in Conway's game of Life {{OEIS|id=A056613}}.

class="wikitable" style="text-align:center"
Live cells ! Strict still lifes ! Pseudo still lifes ! Examples
1	0	0
2	0	0
3	0	0
4	2	0	Block, tub
5	1	0	Boat
6	5	0	Barge, beehive, carrier, ship, snake
7	4	0	Fishhook, loaf, long boat, python
8	9	1	Canoe, mango, long barge, pond
9	10	1	Hat, integral sign
10	25	7	Block on table, boat-tie, loop
11	46	16
12	121	55	Ship-tie {{cite web |url=https://conwaylife.com/wiki/Ship-tie |access-date=2024-07-11| title = Ship-tie - from LifeWiki}}
13	240	110
14	619	279	Bi-loaf {{cite web |url=https://conwaylife.com/wiki/Half-bakery |access-date=2024-07-11| title = Half-bakery - from LifeWiki}}
15	{{formatnum:1353}}	620
16	{{formatnum:3286}}	{{formatnum:1645}}
17	{{formatnum:7773}}	{{formatnum:4067}}
18	{{formatnum:19044}}	{{formatnum:10843}}
19	{{formatnum:45759}}	{{formatnum:27250}}	Eater 2{{cite web |url=https://conwaylife.com/wiki/Eater_2 |access-date=2024-07-11| title = Eater 2 - from LifeWiki}}
20	{{formatnum:112243}}	{{formatnum:70637}}
21	{{formatnum:273188}}	{{formatnum:179011}}
22	{{formatnum:672172}}	{{formatnum:462086}}
23	{{formatnum:1646147}}	{{formatnum:1184882}}
24	{{formatnum:4051732}}	{{formatnum:3069135}}
25	{{formatnum:9971377}}	{{formatnum:7906676}}
26	{{formatnum:24619307}}	{{formatnum:20463274}}
27	{{formatnum:60823008}}	{{formatnum:52816265}}
28	{{formatnum:150613157}}	{{formatnum:136655095}}
29	{{formatnum:373188952}}	{{formatnum:353198379}}
30	{{formatnum:926068847}}	{{formatnum:914075620}}
31	{{formatnum:2299616637}}	{{formatnum:2364815358}}
32	{{formatnum:5716948683}}	{{formatnum:6123084116}}
33	{{formatnum:14223867298}}	{{formatnum:15851861075}}
34	{{formatnum:35422864104}}	{{formatnum:41058173683}}

{{multiple image|image1=GOLMaxDens19x19.png|caption1=19×19 maximum-density still life in Conway's game of life

|image2=GOLMaxDens20x20.png|caption2=20×20 maximum-density still life in Conway's game of life}}

The problem of fitting an n×n region with a maximally dense still life has attracted attention as a test case for constraint programming.{{Cite journal|first=R. A.|last=Bosch|title=Integer programming and Conway's game of Life|journal=SIAM Review|volume=41|issue=3|year=1999|pages=594–604|doi=10.1137/S0036144598338252|bibcode=1999SIAMR..41..594B|doi-access=}}.{{Cite journal|first=R. A.|last=Bosch|title=Maximum density stable patterns in variants of Conway's game of Life|journal=Operations Research Letters|volume=27|pages=7–11|year=2000|issue=1|doi=10.1016/S0167-6377(00)00016-X}}.{{Cite conference|first=Barbara M.|last=Smith|contribution=A dual graph translation of a problem in ‘Life’|title=Principles and Practice of Constraint Programming - CP 2002|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=2470|doi=10.1007/3-540-46135-3_27|year=2002|pages=89–94|isbn=978-3-540-44120-5 }}.{{Cite journal|first1=Robert|last1=Bosch|first2=Michael|last2=Trick|author2-link= Michael Trick |title= Constraint programming and hybrid formulations for three Life designs|journal=Annals of Operations Research|volume=130|issue=1–4|year=2004|doi=10.1023/B:ANOR.0000032569.86938.2f|pages=41–56|s2cid=27359250 }}.{{Cite journal|first1=Kenil C. K.|last1=Cheng|first2=Roland H. C.|last2=Yap|journal=Constraints|title=Applying ad-hoc global constraints with the case constraint to still-life|volume=11|issue=2–3|year=2006|pages=91–114|doi=10.1007/s10601-006-8058-9|s2cid=8241518 }}.

In the limit of an infinitely large grid, no more than half of the cells in the plane can be live.{{cite conference

| author = Elkies, Noam D.

| title = The still life density problem and its generalizations

| date = 1998

| book-title = Voronoi's Impact on Modern Science, Book I

| publisher = Proc. Inst. Math. Nat. Acad. Sci. Ukraine, vol. 21

| pages = 228–253

| arxiv = math.CO/9905194

| author-link = Noam D. Elkies}}

For finite square grids, greater densities can be achieved. For instance, the maximum density still life within an 8×8 square is a regular grid of nine blocks, with density 36/64 = 0.5625. Optimal solutions are known for squares of all sizes.{{Cite journal|title = A complete solution to the Maximum Density Still Life Problem|journal = Artificial Intelligence|date = 2012-06-01|pages = 1–16|volume = 184–185|doi = 10.1016/j.artint.2012.02.001|first1 = Geoffrey|last1 = Chu|first2 = Peter J.|last2 = Stuckey|doi-access = free}} Yorke-Smith provides a listing of known finite maximum-density patterns.{{cite web

| author = Neil Yorke-Smith

| title = Maximum Density Still Life

| url = http://www.ai.sri.com/~nysmith/life/index.html

| work=Artificial Intelligence Center

| publisher=SRI International}}

{{reflist|30em}}

{{Conway's Game of Life}}

{{DEFAULTSORT:Still Life (Cellular Automaton)}}

Category:Cellular automaton patterns