Still life (cellular automaton)
In Conway's Game of Life and other cellular automata, a still life is a pattern that does not change from one generation to the next. The term comes from the art world where a still life painting or photograph depicts an inanimate scene. In cellular automata, a still life can be thought of as an oscillator with unit period.[1]
Classification
A pseudo still life consists of two or more adjacent islands (
Examples
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.
The second most common still life is the hive (or beehive).[3] Hives are frequently created in (non-interacting) sets of four, in a formation known as a honey farm.
The third most common still life is the loaf.[3] 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.
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.
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.
Eaters
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
Enumeration
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 A019473 and A056613 respectively in the On-Line Encyclopedia of Integer Sequences (OEIS)).[4][5]
Live cells | Strict still lifes | Pseudo still lifes | Examples[1] |
---|---|---|---|
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[citation needed] |
13 | 240 | 110 | |
14 | 619 | 279 | Bi-loaf[citation needed] |
15 | 1,353 | 620 | |
16 | 3,286 | 1,645 | |
17 | 7,773 | 4,067 | |
18 | 19,044 | 10,843 | |
19 | 45,759 | 27,250 | Eater 2[citation needed] |
20 | 112,243 | 70,637 | |
21 | 273,188 | 179,011 | |
22 | 672,172 | 462,086 | |
23 | 1,646,147 | 1,184,882 | |
24 | 4,051,732 | 3,069,135 | |
25 | 9,971,377 | 7,906,676 | |
26 | 24,619,307 | 20,463,274 | |
27 | 60,823,008 | 52,816,265 | |
28 | 150,613,157 | 136,655,095 | |
29 | 373,188,952 | 353,198,379 | |
30 | 926,068,847 | 914,075,620 | |
31 | 2,299,616,637 | 2,364,815,358 | |
32 | 5,716,948,683 | 6,123,084,116 | |
33 | 14,223,867,298 | 15,851,861,075 | |
34 | 35,422,864,104 | 41,058,173,683 |
Density
The problem of fitting an n×n region with a maximally dense still life has attracted attention as a test case for constraint programming.[6][7][8][9][10] In the limit of an infinitely large grid, no more than half of the cells in the plane can be live.[11] 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.[6] Optimal solutions are known for squares of all sizes.[12] Yorke-Smith provides a listing of known finite maximum-density patterns.[13]
References
- ^ a b "Still Life - from Eric Weisstein's Treasure Trove of Life C.A." Retrieved 2009-01-24.
- ^ Cook, Matthew (2003). "Still life theory". New Constructions in Cellular Automata. Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. pp. 93–118.
- ^ a b c Achim Flammenkamp. "Top 100 of Game-of-Life Ash Objects". Retrieved 2008-11-05.
- ^ Number of stable n-celled patterns ("still lifes") in Conway's game of Life (sequence A019473 in the OEIS).
- ^ Number of n-celled pseudo-still-lifes in Conway's game of Life (sequence A056613 in the OEIS).
- ^ ..
- ..
- ..
- S2CID 27359250..
- S2CID 8241518..
- arXiv:math.CO/9905194.
- .
- ^ Neil Yorke-Smith. "Maximum Density Still Life". Artificial Intelligence Center. SRI International.