# Conway's Game of Life

Conway's Game of Life is the best known example of a cellular
automaton; it was invented by John Conway and first brought to public
attention in Martin Gardner's *Scientific American* column in Oct
1970. Conway's goal in creating Life was to devise a universal Turing
machine – a sort of infinitely programmable computer. John von
Neumann had described such a system in the 1950s, but it had very complex
rules; Conway wanted to find one that was much simpler to describe and to
operate.

Life is played on a grid of squares on which each cell is either alive (occupied) or dead (empty). The game starts from an arbitrary initial configuration of live cells, and then progresses through generations as the life and death rules are applied. These rules are very simple: (1) A live cell survives to the next generation if it has two or three neighbors. (2) A live cell dies if it has four or more neighbors (overcrowding) or if it has only one neighbor or none (isolation). (3) A dead cell becomes a live cell in the next generation if it has exactly three neighbors (birth).

The rules of Life were developed over a two-year-period during tea and coffee
breaks by Conway and a group of graduate students and colleagues. Because Go boards and counters were used at this stage,
instead of computers, it was important to have a death rule so that populations
didn't tend to explode and quickly race off the board. On the other hand,
to enable sufficiently interesting behavior that the game had a chance of
being a universal system, it was equally important to have a birth rule
that prevented populations from dying out. The rules eventually chosen provided
a balance between birth and death so that the system tended to be fairly
stable yet interesting enough to study. An early sign of success was the
discovery of patterns, known as 'gliders,' that kept their shape while drifting
across the plane. This was a hopeful step toward proving universality because
it showed that the system had a way to transmit information from one place
to another. Conway and his group went on to build nearly all the necessary
configurations for arbitrary computations: AND gates, OR gates, and so on,
just like the components of an ordinary computer. What they needed next
was a way of producing gliders at will – a 'glider gun.' At this point,
Conway sent a letter describing Life and the early finding's to Martin Gardner,
offering a prize of $50 for a configuration whose population tended towards
infinity. The resulting *Scientific American* column sparked the public's
imagination and very quickly a glider gun was discovered by a group at the
Massachusetts Institute of Technology led by R. W. Gosper. Within two weeks
of the discovery of the glider gun, both Conway's group and the group at
MIT had shown that the system was indeed universal.