Oscillator (cellular automaton)


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 context, the term may also include spaceships as well.

The smallest number of generations it takes before the pattern returns to its initial condition is called the period of the oscillator. An oscillator with a period of 1 is usually called a still life, as such a pattern never changes. Sometimes, still lifes are not taken to be oscillators. Another common stipulation is that an oscillator must be finite.

Examples

In Conway's Game of Life, finite oscillators are known to exist for almost any period. The exceptions are 19, 23, 38, 41, 43, and 53. It is not known whether oscillators of those periods exist, but it is strongly believed that they do. Additionally, while oscillators exist for period 34, the only known examples are considered trivial because they consist of essentially separate components that oscillate at smaller periods. For instance, one can create a period 34 oscillator by placing period 2 and period 17 oscillators so that they do not interact. An oscillator is considered non-trivial if it contains at least one cell that oscillates at the necessary period.

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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

  • Spark (cellular automaton) — [ oscillator in Conway s Game of Life. The two live cells appearing at the top of the pattern every five generations form a spark.] In Conway s Game of Life and similar cellular automaton rules, a spark is a small collection of live cells that… …   Wikipedia

  • Seeds (cellular automaton) — Seeds is a cellular automaton in the same family as the Game of Life, initially investigated by Brian Silverman and named by Mirek Wójtowicz. It consists of infinite two dimensional grid of cells, each of which may be in one of two states: on or… …   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

  • Gun (cellular automaton) — In a cellular automaton, a gun is a pattern of which the main part repeats periodically, like an oscillator and which also periodically emits spaceships. There are then two periods that may be considered. There is the period of the spaceship… …   Wikipedia

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

  • 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… …   Wikipedia

  • Oscillator (disambiguation) — An oscillator is a device designed for oscillation. Oscillator may also refer to: Electronic oscillator Harmonic oscillator Oscillator (technical analysis), a method used in technical analysis of financial markets Oscillator (cellular automaton)… …   Wikipedia

  • Осциллятор — (от лат. oscillo  качаюсь)  система, совершающая колебания, то есть показатели которой периодически повторяются во времени. Физика Понятие осциллятора играет важную роль в физике и достаточно повсеместно используется, например, в… …   Википедия

  • 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