Still life (cellular automaton)

Still life (cellular automaton)

In cellular automata, a still life is a pattern that does not change from one generation to the next. A still life can be thought of as an oscillator of period 1. A "strict still life" is an indecomposable still life pattern, while a "pseudo still life" is a still life pattern that can be partitioned into two non-interacting subparts (Cook, 2003).

In Conway's Game of Life

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 is the block. Another example is the loaf.

Still lifes can also be used to modify or destroy other objects. For example, the eater pictured above is capable of absorbing a glider approaching from the upper left, and returning to its original state after the collision. This is not unique—there are many other eaters.

The distinction between strict still lifes and pseudo still lifes is not always obvious, as a strict still life may have multiple connected components all of which are needed for its stability. However, Cook (2003) has 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.

Niemiec lists all still life patterns in the Game of Life up to patterns with 17 live cells. The number of still life patterns with "n" stable cells ("n" ≥ 4) is:2, 1, 5, 4, 9, 10, 25, 46, 121, 240, 619, 1353, ... OEIS|id=A019473.

Elkies (1998) shows that, in the Game of Life, any infinite still life pattern can fill at most half of the cells in the plane.


*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

*cite conference
author = Elkies, Noam D.
title = The still life density problem and its generalizations
date = 1998
booktitle = Voronoi's Impact on Modern Science, Book I
publisher = Proc. Inst. Math. Nat. Acad. Sci. Ukraine, vol. 21
pages = 228–253
id = arxiv | archive = math.CO | id = 9905194

*cite web
author = Niemiec, Mark D.
title = Life Still-Lifes
url =

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Still Life (disambiguation) — A still life is a work of art depicting inanimate subject matter.Still life may also refer to:* Still life photography * Still life (cellular automaton), an unchanging pattern in a cellular automaton * Still Life (video game), a 2005 computer… …   Wikipedia

  • Cellular automaton — A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, theoretical biology and microstructure modeling. It consists of a regular grid of cells , each in one of a finite number of states …   Wikipedia

  • Puffer train (cellular automaton) — In a cellular automaton a puffer train, or simply puffer, is a finite pattern that moves itself across the universe , leaving debris behind. Thus a pattern consisting of only a puffer will grow arbitrarily large over time. Puffers differ from… …   Wikipedia

  • Garden of Eden (cellular automaton) — An orphan pattern in Conway s Game of Life, discovered by R. Banks in 1971.[1] …   Wikipedia

  • Block cellular automaton — The Margolus neighborhood for a two dimensional block cellular automaton. The partition of the cells alternates between the set of 2 × 2 blocks indicated by the solid blue lines, and the set of blocks indicated by the dashed red lines. A block… …   Wikipedia

  • Oscillator (cellular automaton) — In a cellular automaton, an oscillator is a pattern that returns to its original state, in the same orientation and position, after a finite number of generations. Thus the evolution of such a pattern repeats itself indefinitely. Depending on… …   Wikipedia

  • Methuselah (cellular automaton) — The die hard Methuselah lives for 130 generations before all cells die. In cellular automata, a methuselah is a small seed pattern of initial live cells that take a large number of generations in order to stabilize. More specifically, Martin… …   Wikipedia

  • Conway's Game of Life — Conway game , which redirects to here, can also refer to games as defined by surreal numbers, which John Conway also developed …   Wikipedia

  • History of artificial life — The idea of human artifacts being given life has fascinated mankind for as long as men have been recording their myths and stories. Whether Pygmalion or Frankenstein, mankind has been fascinated with the idea of artificial life. Pre computer… …   Wikipedia

  • Natural computing — For the scientific journal, see Natural Computing (journal). Natural computing, also called Natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”