Spaceship (cellular automaton)

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 $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 is translated by $(x,y)$ after $n$ generations, then the speed $v$ is defined as:

v={\frac {\max \left(|x|,|y|\right)}{n}}\,c

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.

In March 2016, the unexpected discovery of a small but high-period spaceship enthused the Game of Life community. It was named "copperhead".^[1]

References

↑ https://niginsblog.wordpress.com/2016/03/07/new-spaceship-speed-in-conways-game-of-life/

External links

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

Conway's Game of Life & related cellular automata

Structures	Breeder Garden of Eden Glider Gun Methuselah Oscillator Puffer train Rake Reflector Replicator Sawtooth Spacefiller Spaceship Spark Still life

Life variants	Day and Night Highlife Life without Death Seeds

Concepts	Moore neighborhood Speed of light Von Neumann neighborhood

Implementations	Golly Life Genesis Mirek's Cellebration Video Life

Key people	John Conway Martin Gardner Bill Gosper Richard Guy

Popular culture	Bloom Wake

This article is issued from Wikipedia - version of the 10/1/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.