Oscillator (CA)
Encyclopedia
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 spaceship
s 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.
, 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.
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
, 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 spaceship
Spaceship (CA)
In a cellular automaton, a finite pattern is called a spaceship if it reappears after a certain number of generations in the same orientation but in a different position...
s 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
Still life (CA)
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. A still life can be thought of as an oscillator with unit period.-Pseudo still lifes:...
, 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 LifeConway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
, 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
- List of known oscillators at the LifeWiki
- A collection of oscillators in the Game of Life (zip file)