Gun (cellular automaton)

From Wikipedia, the free encyclopedia
  (Redirected from Gosper Glider Gun)
Jump to: navigation, search
Gosper Glider Gun shooting gliders

In a cellular automaton, a gun is a pattern with a main part that repeats periodically, like an oscillator, and that also periodically emits spaceships. There are then two periods that may be considered: the period of the spaceship output, and the period of the gun itself, which is necessarily a multiple of the spaceship output's period. A gun whose period is larger than the period of the output is a pseudoperiod gun.

A gun and an "antigun" in the Life variation Day & Night
The smallest gun found so far in Conway's Game of Life is the Gosper Glider Gun

In the Game of Life, for every p greater than or equal to 14, it is possible to construct a glider gun in which the gliders are emitted with period p.[1]

Since guns continually emit spaceships, the existence of guns in Life means that initial patterns with finite numbers of cells can eventually lead to configurations with limitless numbers of cells, something that John Conway himself originally did not believe was possible. Bill Gosper discovered the first glider gun (and, so far, the smallest one found) in 1970, earning $50 from Conway. The discovery of the glider gun eventually led to the proof that Conway's Game of Life could function as a Turing machine.[2]

References[edit]

  1. ^ Summers, Jason. "Game of Life Status page". Entropymine.com. Retrieved February 5, 2011. 
  2. ^ Gardner, Martin (2001). The Colossal Book of Mathematics. New York: W. W. Norton. ISBN 0-393-02023-1.