Gun (cellular automaton)
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.
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 conjectured to be impossible. However, according to Conway's later testimony, this conjecture was explicitly intended to encourage someone to disprove it -- i.e., Conway hoped that infinite-growth patterns did exist.
Bill Gosper discovered the first glider gun (still, so far, the smallest glider gun ever found, though no longer the smallest infinite-growth pattern) 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.
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|