artificial life
Chapter 3: Cellular Automata
3.3 Conway's Game of Life
A Cambridge mathematician, John Conway, developed the Game of Life in the sixties. Conway knew of von Neumann's extravagant creature and thought it was an interesting idea, but he also thought that interesting virtual organisms could be created using a far simpler scheme. The system he developed has cells with only 2 states, dead or alive. The cells have a 9-cell neighborhood, the eight cells immediately adjacent to the cell and the cell itself. The rules are as follows [Levy, 1992]:
1. If a cell is alive and two or three surrounding cells are alive, then the cell stays alive, otherwise the cell dies of exposure or overcrowding.
2. If a cell is dead and exactly three surrounding cells are alive, then the cell's state is changed to alive, otherwise it remains dead.
Initially, the game was carried out by hand on boards in Cambridge. The participants created shapes by placing objects on the board to represent 'live' cells and then followed the rules to see if any behavior emerged. Many patterns simply died away producing an empty board. Others changed a little initially but settled into a stable structure that would stay constant if undisturbed. Sometimes, however, there emerged interesting phenomena from an initial board configuration; blocks of cells that moved through the board, almost with purpose.
The first of these strange patterns to emerge has come to be known as a "glider". A glider cycles through several states and moves one cell diagonally in one direction after each cycle. The glider continues to move in the same direction until it runs into some obstacle, a wall, or another "live" cell. Figure 3.3 shows a "glider". The first frame is identical to the fifth frame except that the glider has displaced itself by one cell diagonally.
Figure 3.3 : A "Glider"
As Conway and his colleagues continued to investigate the nature of his game they found other similar interesting patterns. The game eventually spread and was implemented on computers leading to an investigation of more complex scenarios.
As more complex CA organisms were found, Conway was eventually able to prove that Life was a universal computer. A universal computer, or a Turing machine, is a machine that can perform any finite algorithm. Alan Turing, who came up with the concept of a universal computer, believed that the human mind was a universal computer.