Spaceship (cellular automaton)
- 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. In a two-dimensional cellular automaton, if a spaceship is translated by ("m", "n") every period, then the speed is defined as the maximum of |"m"| and |"n"|, divided by the period, multiplied by "c". For example, "c"/4 means a speed of one cell every four generations. This is easily generalized to cellular automata of dimensionality other than 2.
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.
External links
* [http://surf.de.uu.net/people/joke/rsc/ships_toc.html Spaceships in Conway's Game of Life] by David I. Bell
* [http://www.ics.uci.edu/~eppstein/ca/ Gliders in "Life"-Like Cellular Automata] by David Eppstein
Wikimedia Foundation.
2010.
Look at other dictionaries:
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… … 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
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
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
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
Garden of Eden (cellular automaton) — An orphan pattern in Conway s Game of Life, discovered by R. Banks in 1971.[1] … Wikipedia
Puffer train (cellular automaton) — In a cellular automaton a puffer train, or simply puffer, is a finite pattern that moves itself across the universe , leaving debris behind. Thus a pattern consisting of only a puffer will grow arbitrarily large over time. Puffers differ from… … Wikipedia
Spaceship — can refer to: * Another name for a spacecraft used for human spaceflight. * An Unidentified flying object (UFO) * Spaceship , a song by Kanye West from his album The College Dropout . * Spaceship , a song by Australian band The Vines from their… … Wikipedia
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
Day & Night — This article is about a cellular automaton rule. For other uses, see Day Night (disambiguation). Gun and antigun demonstrating the symmetric nature of Day Night. Day Night is a cellular automaton rule in the same family as Game of Life. It is… … Wikipedia
