Spaceship (CA)
Encyclopedia
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. The smallest such number of generations is called the period of the spaceship.
The speed of a spaceship is often expressed in terms of c, the metaphorical speed of light
(one cell per generation) which in many cellular automata is the fastest that an effect can spread. For example, a glider
in Conway's Game of Life
is said to have a speed of
, as it takes four generations for a given state to be translated by one cell. Similarly, the lightweight spaceship is said to have a speed of 
, as it takes four generations for a given state to be translated by two cells. More generally, if a spaceship in a 2D automaton is translated by 
after 
generations, then the speed 
is defined as:
This notation can be readily generalised to cellular automata with dimensionality other than two.
A tagalong is a pattern that is not a spaceship in itself but that can be attached to the back of a spaceship to form a larger spaceship. Similarly, a pushalong is placed at the front.
A pattern that, when a spaceship is input, outputs a copy of the spaceship travelling in a different direction is called a reflector.
Spaceships are important because they can sometimes be modified to produce puffers. Spaceships can also be used to transmit information
. For example, in Conway's Game of Life
, the ability of the glider
(Life's simplest spaceship) to transmit information is part of a proof that Life is Turing-complete.
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"...
, 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. The smallest such number of generations is called the period of the spaceship.
The speed of a spaceship is often expressed in terms of c, the metaphorical speed of light
Speed of light (cellular automaton)
In Conway's Game of Life , the speed of light is a propagation rate across the grid of exactly one step per generation...
(one cell per generation) which in many cellular automata is the fastest that an effect can spread. For example, a glider
Glider (Conway's Life)
The glider is a pattern that travels across the board in Conway's Game of Life. It was first discovered by Richard K. Guy in 1970, while John Conway's group was attempting to track the evolution of the R-pentomino. Gliders are the smallest spaceships, and they travel diagonally at a speed of c/4...
in Conway's Game of Life
Conway'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....
is said to have a speed of
, as it takes four generations for a given state to be translated by one cell. Similarly, the lightweight spaceship is said to have a speed of , as it takes four generations for a given state to be translated by two cells. More generally, if a spaceship in a 2D automaton is translated by after generations, then the speed is defined as:This notation can be readily generalised to cellular automata with dimensionality other than two.
A tagalong is a pattern that is not a spaceship in itself but that can be attached to the back of a spaceship to form a larger spaceship. Similarly, a pushalong is placed at the front.
A pattern that, when a spaceship is input, outputs a copy of the spaceship travelling in a different direction is called a reflector.
Spaceships are important because they can sometimes be modified to produce puffers. Spaceships can also be used to transmit information
Information
Information in its most restricted technical sense is a message or collection of messages that consists of an ordered sequence of symbols, or it is the meaning that can be interpreted from such a message or collection of messages. Information can be recorded or transmitted. It can be recorded as...
. For example, in Conway's Game of Life
Conway'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....
, the ability of the glider
Glider (Conway's Life)
The glider is a pattern that travels across the board in Conway's Game of Life. It was first discovered by Richard K. Guy in 1970, while John Conway's group was attempting to track the evolution of the R-pentomino. Gliders are the smallest spaceships, and they travel diagonally at a speed of c/4...
(Life's simplest spaceship) to transmit information is part of a proof that Life is Turing-complete.
External links
- Spaceships in Conway's Game of Life by David I. Bell
- Gliders in "Life"-Like Cellular Automata by David EppsteinDavid EppsteinDavid Arthur Eppstein is an American computer scientist and mathematician. He is professor of computer science at University of California, Irvine. He is known for his work in computational geometry, graph algorithms, and recreational mathematics.-Biography:Born in England of New Zealander...