In a

cellular automaton A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...

, 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.

Description

The speed of a spaceship is often expressed in terms of ''c'', the metaphorical

speed of light The speed of light in vacuum, commonly denoted , is a universal physical constant that is important in many areas of physics. The speed of light is exactly equal to ). According to the special theory of relativity, is the upper limit ...

(one cell per generation) which in many cellular automata is the fastest that an effect can spread. For example, a

glider Glider may refer to: Aircraft and transport Aircraft * Glider (aircraft), heavier-than-air aircraft primarily intended for unpowered flight ** Glider (sailplane), a rigid-winged glider aircraft with an undercarriage, used in the sport of glidin ...

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. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further ...

is said to have a speed of

c/4

, 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

c/2

, as it takes four generations for a given state to be translated by two cells. More generally, if a spaceship in a 2D automaton with the

Moore neighborhood In cellular automata, the Moore neighborhood is defined on a two-dimensional square lattice and is composed of a central cell and the eight cells that surround it. Name The neighborhood is named after Edward F. Moore, a pioneer of cellular au ...

is translated by

(x, y)

after

n

generations, then the speed

v

is defined as: This notation can be readily generalised to cellular automata with dimensionality other than two. A pullalong 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. The term tagalong can refer to either of these patterns or a pattern that can be placed at the side of a spaceship to form a larger spaceship. A pattern that, when a spaceship is input, outputs a copy of the spaceship travelling in a different direction is called a reflector. If the output is instead a different spaceship, the pattern is known as a converter. Spaceships are important because they can sometimes be modified to produce puffers. Spaceships can also be used to transmit

information Information is an abstract concept that refers to that which has the power to inform. At the most fundamental level information pertains to the interpretation of that which may be sensed. Any natural process that is not completely random ...

. For example, in

, the ability of the

(Life's simplest spaceship) to transmit information is part of a proof that Life is

Turing-complete In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Tur ...

. In March 2016, the unexpected discovery of a small but high-period spaceship enthused the Game of Life community. It was named "copperhead". A similar example, called "loafer", was found a few years earlier. In March 2018, the first elementary spaceship with displacement (2,1) ( knightwise) was discovered and named Sir Robin.

References

External links

Spaceships in Conway's Game of Life
by David I. Bell
Gliders in "Life"-Like Cellular Automata
by

David Eppstein David Arthur Eppstein (born 1963) is an American computer scientist and mathematician. He is a Distinguished Professor of computer science at the University of California, Irvine. He is known for his work in computational geometry, graph algorit ...

{{Conway's Game of Life Cellular automaton patterns