Glider (Conway's Life)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The mutation and movement of a "glider".
A three-dimensional view of a glider, with previous generations visible going down the z-axis. The c/4 period is clearly visible as "stacks" of cells that remain alive for successive generations.

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. The glider is often produced from randomly generated starting configurations.[1] John Conway has remarked that he wishes he hadn't called it the glider. The game was developed before computers and after seeing it animated, he feels the glider looks more like an ant walking across the plane.[2]

Importance[edit]

Gliders are important to the Game of Life because they are easily produced, can be collided with each other to form more complicated objects, and can be used to transmit information over long distances. For instance, eight gliders can be positioned so that they collide to form a Gosper glider gun.[3] Glider collisions designed to result in certain patterns are also called glider syntheses.

Patterns like blocks, beehives, blinkers, traffic lights, even the uncommon Eater, can be synthesized with but 2 gliders. It takes 3 gliders to build the 3 classic (naturally occurring) spaceships, and even the pentadecathlon.

Some patterns require a very large number (scores, even hundreds) of glider collisions; some oscillators, exotic spaceships, puffer trains, guns, etc. Whether the construction of an exotic pattern from gliders can possibly mean it can occur naturally, is still conjecture.

Gliders can also be collided with other patterns with interesting results. For example, if two gliders are shot at a block in just the right way, the block will move closer to the source of the gliders. If three gliders are shot in just the right way, the block will move farther away. This "sliding block memory" can be used to simulate a counter, which would be modified by firing gliders at it. It is possible to construct logic gates such as AND, OR and NOT using gliders. One may also build a pattern that acts like a finite state machine connected to two counters. This has the same computational power as a universal Turing machine, so, using the glider, the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints: it is Turing complete.[4][5]

Going by the technical definition, the number of gliders is possibly unlimited, of which the familiar 5-bit one is the only one that naturally occurs. Some consist of 1 or more gliders towing & inducting raw matter (Orion, etc.) and others do not have towing gliders,but satisfy the definition of a glider nevertheless .Conversely, diagonal period 4 spaceships towed by gliders do not necessarily have glide-reflected half-periods (swan, big "glider", etc.)

The artificial mega-gliders are somewhat larger than the familiar one known from 1970, but were not known until 1989 when computer search programs vastly increased Life knowledge.

There is even a period 6 glider of large size, the Seal.

Hacker emblem[edit]

Eric S. Raymond has proposed the glider as an emblem to represent the hacker subculture, as the Game of Life appeals to hackers, and the concept of the glider was "born at almost the same time as the Internet and Unix".[6]

References[edit]

  1. ^ "Spontaneous appeared Spaceships out of Random Dust". Achim Flammenkamp. 1995-12-09. Retrieved 2009-02-27. 
  2. ^ "Does John Conway hate his Game of Life?". Numberphile channel on YouTube. 2014-03-03. Retrieved 2014-05-09. 
  3. ^ Gosper Glider Gun at the LifeWiki
  4. ^ Paul Chapman (November 11, 2002). "Life Universal Computer". Retrieved July 12, 2009. 
  5. ^ Berlekamp, E. R.; Conway, John Horton; Guy, R.K. (2001 2004), Winning Ways for your Mathematical Plays (2nd ed.), A K Peters Ltd, ISBN 978-1-56881-130-7, ISBN 1-56881-142-X, ISBN 1-56881-143-8, ISBN 1-56881-144-6 
  6. ^ Raymond, Eric S.. "Frequently Asked Questions about the Glider Emblem". Retrieved November 5, 2012. 

External links[edit]