العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolSPACESHIP (CELLULAR AUTOMATON)
(Redirected from 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. 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 the proof that a universal Turing machine (a machine that can calculate anything that is calculable) can be constructed in Life.
★ Spaceships in Conway's Game of Life by David I. Bell
★ Gliders in "Life"-Like Cellular Automata by David Eppstein
The "lightweight spaceship" (LWSS) pattern in Conway's Game of Life
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 the proof that a universal Turing machine (a machine that can calculate anything that is calculable) can be constructed in Life.
| Contents |
| External links |
External links
★ Spaceships in Conway's Game of Life by David I. Bell
★ Gliders in "Life"-Like Cellular Automata by David Eppstein
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
