Spaceship (cellular automaton)
From Wikipedia, the free 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. 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.
