 | This article needs additional citations for verification .(June 2015) |
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 , 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 , 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 is translated by after generations, then the speed 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. 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] A similar example, [2] 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. [3]
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 input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves. It is Turing complete and can simulate a universal constructor or any other Turing machine.
A cellular automaton is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling.
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states and transitions. As the automaton sees a symbol of input, it makes a transition to another state, according to its transition function, which takes the previous state and current input symbol as its arguments.
The Rule 110 cellular automaton is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to Conway's Game of Life. Like Life, Rule 110 with a particular repeating background pattern is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.
Highlife is a cellular automaton similar to Conway's Game of Life. It was devised in 1994 by Nathan Thompson. It is a two-dimensional, two-state cellular automaton in the "Life family" and is described by the rule B36/S23; that is, a cell is born if it has 3 or 6 neighbors and survives if it has 2 or 3 neighbors. Because the rules of HighLife and Conway's Life are similar, many simple patterns in Conway's Life function identically in HighLife. More complicated engineered patterns for one rule, though, typically do not work in the other rule.
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. While both puffers and spaceships have periods and speeds, unlike puffers, spaceships do not leave debris behind.
A cellular automaton (CA) is Life-like if it meets the following criteria:
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 an infinite two-dimensional grid of cells, each of which may be in one of two states: on or off. Each cell is considered to have eight neighbors, as in Life. In each time step, a cell turns on or is "born" if it was off or "dead" but had exactly two neighbors that were on; all other cells turn off. Thus, in the notation describing the family of cellular automata containing Life, it is described by the rule B2/S.
Hashlife is a memoized algorithm for computing the long-term fate of a given starting configuration in Conway's Game of Life and related cellular automata, much more quickly than would be possible using alternative algorithms that simulate each time step of each cell of the automaton. The algorithm was first described by Bill Gosper in the early 1980s while he was engaged in research at the Xerox Palo Alto Research Center. Hashlife was originally implemented on Symbolics Lisp machines with the aid of the Flavors extension.
The glider is a pattern that travels across the board in Conway's Game of Life. It was first discovered by Richard K. Guy in 1969, while John Conway's group was attempting to track the evolution of the R-pentomino. Gliders are the smallest spaceships, and they travel diagonally at a speed of one cell every four generations, or . The glider is often produced from randomly generated starting configurations. John Conway remarked that he wished he hadn't called it the glider. The game was developed before the widespread use of interactive computers, and after seeing it animated, he feels the glider looks more like an ant walking across the plane.
In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. It can be the initial configuration of the automaton but cannot arise in any other way. John Tukey named these configurations after the Garden of Eden in Abrahamic religions, which was created out of nowhere.
A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell. Block cellular automata are useful for simulations of physical quantities, because it is straightforward to choose transition rules that obey physical constraints such as reversibility and conservation laws.
In Conway's Game of Life and other cellular automata, a still life is a pattern that does not change from one generation to the next. The term comes from the art world where a still life painting or photograph depicts an inanimate scene. In cellular automata, a still life can be thought of as an oscillator with unit period.
A rake, in the lexicon of cellular automata, is a type of puffer train, which is an automaton that leaves behind a trail of debris. In the case of a rake, however, the debris left behind is a stream of spaceships, which are automata that "travel" by looping through a short series of iterations and end up in a new location after each cycle returns to the original configuration.
In Conway's Game of Life and similar cellular automaton rules, a spark is a small collection of live cells that appears at the edge of some larger pattern such as a spaceship or oscillator, then quickly dies off.
In Conway's Game of Life, the speed of light is a propagation rate across the grid of exactly one step per generation. In a single generation, a cell can only influence its nearest neighbours, and so the speed of light is the maximum rate at which information can propagate. It is therefore an upper bound to the speed at which any pattern can move.
Brian's Brain is a cellular automaton devised by Brian Silverman, which is very similar to his Seeds rule.
Life without Death is a cellular automaton, similar to Conway's Game of Life and other Life-like cellular automaton rules. In this cellular automaton, an initial seed pattern grows according to the same rule as in Conway's Game of Life; however, unlike Life, patterns never shrink. The rule was originally considered by Toffoli & Margolus (1987), who called it "Inkspot"; it has also been called "Flakes". In contrast to the more complex patterns that exist within Conway's Game of Life, Life without Death commonly features still life patterns, in which no change occurs, and ladder patterns, that grow in a straight line.
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells. The time-reversed dynamics of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood.
Critters is a reversible block cellular automaton with similar dynamics to Conway's Game of Life, first described by Tommaso Toffoli and Norman Margolus in 1987.
