Conway's Game of Life

In 1970, mathematician John Horton Conway invented a game called Life. Conway was intrigued by John von Neumann's theories about self-replicating automata: simple mathematical formulae representing virtual "life forms" that could be depicted in a virtual world. Of course, in von Neumann's day the "virtual world" was a piece of graph paper with some squares filled in (squares being the life forms), but still, it was a pretty cool idea. Conway took von Neumann's ideas a step further, creating a computer simulation of the graph paper-based automata, and forcing the automata to follow simple rules:

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur: 1. Any live cell with fewer than two live neighbours dies, as if by needs caused by underpopulation. 2. Any live cell with more than three live neighbours dies, as if by overcrowding. 3. Any live cell with two or three live neighbours lives, unchanged, to the next generation. 4. Any tile with exactly three live neighbours cells will be populated with a living cell. The initial pattern constitutes the 'seed' of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed — births and deaths happen simultaneously, and the discrete moment at which this happens is sometimes called a tick. (In other words, each generation is a pure function of the one before.) The rules continue to be applied repeatedly to create further generations.

Conway's Game of Life often starts with a very simple playing field: mostly blank, with a few little bits filled in. What's fascinating is how complexity arises from the simple rules above, as they operate on the seed (the initial condition of the game). Some crazy things happen, including "guns" (pictured above), in which base cells seem to shoot virtual pellets. (When Bill Gosper at MIT discovered/invented guns, he won a $50 prize from Conway.)

Since 1970, Conway's Game of Life has been implemented on virtually every computer platform, either as a time waster or a nice way to get started with simple graphics programming. You can even get Life on the iPhone. To get a feel for Life, try playing The irRegular Game of Life, a nice Flash game in which you solve puzzles by creating automata (you do have to sit through an ad first, though). For a more traditional version of Life, check out this Java version (warning: kinda slow). To learn more about Conway's famous game, read up at Wikipedia.