Speed of light (cellular automaton)
Encyclopedia
In Conway's Game of Life
(and related cellular automata
), the speed of light is a propagation rate across the grid of exactly one step (either horizontally, vertically or diagonally) per generation. In a single generation, a cell can only influence its nearest neighbours
, and so the speed of light (by analogy with the speed of light
in physics) is the maximum rate at which information
can propagate. It is therefore an upper bound to the speed at which any pattern can move.
. This in turn is used as a reference for describing the average propagation speed of spaceships. For example, a glider
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.
is an absolute upper bound to propagation speed, the maximum speed of a spaceship in Conway's Game of Life is in fact 
. This is because it is impossible to build a spaceship that can move every generation. (This is not true, though, for cellular automata in general; for instance many light-speed spaceships exist in Seeds.) It is, however, possible for objects to travel at the speed of light if they move through a medium other than empty space. Such media include trails of hives, and alternating stripes of live and dead cells.
An example is the "Star Gate", an arrangement of three converging gliders that will mutually annihilate on collision. If a lightweight spaceship (LWSS) hits the colliding gliders, it will appear to move forwards by 11 cells in only 6 generations, and thus travel faster than light. This illusion happens because the glider annihilation reaction proceeds by the creation and soon-after destruction of another LWSS. When the incoming LWSS hits the colliding gliders, it isn't transported, but instead modifies the reaction so that the newly created LWSS can survive. The only signal being transmitted is that determining whether the outgoing LWSS should survive or not. This does not need to reach its destination until after the LWSS has been "transported", and so no information needs to travel faster than light.
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
(and related cellular automata
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
), the speed of light is a propagation rate across the grid of exactly one step (either horizontally, vertically or diagonally) per generation. In a single generation, a cell can only influence its nearest neighbours
Moore neighborhood
In cellular automata, the Moore neighborhood comprises the eight cells surrounding a central cell on a two-dimensional square lattice. The neighborhood is named after Edward F. Moore, a pioneer of cellular automata theory. It is one of the two most commonly used neighborhood types, the other one...
, and so the speed of light (by analogy with the speed of light
Speed of light
The speed of light in vacuum, usually denoted by c, is a physical constant important in many areas of physics. Its value is 299,792,458 metres per second, a figure that is exact since the length of the metre is defined from this constant and the international standard for time...
in physics) is the maximum rate at which information
Information
Information in its most restricted technical sense is a message or collection of messages that consists of an ordered sequence of symbols, or it is the meaning that can be interpreted from such a message or collection of messages. Information can be recorded or transmitted. It can be recorded as...
can propagate. It is therefore an upper bound to the speed at which any pattern can move.
Notation
As in physics, the speed of light is represented with the letter. This in turn is used as a reference for describing the average propagation speed of spaceships. For example, a gliderGlider (Conway's Life)
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 1970, 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 c/4...
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.Lightspeed propagation
While is an absolute upper bound to propagation speed, the maximum speed of a spaceship in Conway's Game of Life is in fact . This is because it is impossible to build a spaceship that can move every generation. (This is not true, though, for cellular automata in general; for instance many light-speed spaceships exist in Seeds.) It is, however, possible for objects to travel at the speed of light if they move through a medium other than empty space. Such media include trails of hives, and alternating stripes of live and dead cells.Faster than light propagation
Certain patterns can appear to move at a speed greater than one cell per generation, but like faster than light phenomena in physics this is illusory.An example is the "Star Gate", an arrangement of three converging gliders that will mutually annihilate on collision. If a lightweight spaceship (LWSS) hits the colliding gliders, it will appear to move forwards by 11 cells in only 6 generations, and thus travel faster than light. This illusion happens because the glider annihilation reaction proceeds by the creation and soon-after destruction of another LWSS. When the incoming LWSS hits the colliding gliders, it isn't transported, but instead modifies the reaction so that the newly created LWSS can survive. The only signal being transmitted is that determining whether the outgoing LWSS should survive or not. This does not need to reach its destination until after the LWSS has been "transported", and so no information needs to travel faster than light.