Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Terms of use
Privacy Policy

More Mathematics
CTK Exchange

Games to Relax
Guest book
Recommend this site

Sites for teachers
Sites for parents

Manifesto: what CTK is about Buying a book is a commitment to learning Things you can find on CTK Email to Cut The Knot Recommend this page

The Game of Life

The Game of Life, which is not actually a game, is addictive nonetheless. The Game of Life, or simply Life, has been invented by the famous mathematician John H. Conway, now of Princeton University, in the late 1960s. It was popularized by Martin Gardner in three Scientific American columns starting 1970. All three have been republished in one of his books. Life is also the subject of the last chapter of a mathematical gamer bible, The Winning Ways for Your Mathematical Plays.

Life is a cellular automaton with transition rules for birth, survival and death of individual cells. On a square grid, a cell has 8 neighbors, corresponding to the notion of 8-connectedness. With a reference to a grid square, the terms "empty" and "dead" cell are interchangeable. The rules define a community of organisms that interact in order to reproduce and compete for the living space in the following manner:

 Birth
 An empty cell comes to life if the number of its live neighbors is exactly 3.
 Survival
 A live cell lives on if the number of its live neighbors is either 2 or 3.

It follows that a live cell with fewer than 2 or with more than 3 neighbors dies, apparently of loneliness in the former case and of overcrowding in the latter.

The applet below implements Conway's transition rules. It offers the following controls:

Side  The number of squares on a side of the visible part of the board. The board is finite, although the definition of a cellular automaton requires it to be infinite. We bow to the limitations of our physical hardware.
Reset  Removes all live cells from the board.
Randomize  Creates a random population of live cells.
N  Defines the number of live cells in the random population created by Randomize.
Start/Stop  Starts or stops an automatic application of transition rules.
Delay  Defines a time interval (in milliseconds) between subsequent application of the transition rules.
One step  Causes a single application of the transition rules.
Reverse step  Goes back to the generation before the last use of One step.
Border  The size of the invisible layer of cells that expands the visible part of the board. This parameter may affect the behavior of cells next to the border of the board.
Grid on  Turns the grid on and off.

Finally, at the bottom of the applet a drop-down control allows for a selection of some known shapes, some static, some dynamic.

<hr> <h3> This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet. </h3> <hr>

(Another implementation allows one to define the birth and survival rules.)

Where is mathematics in all that? you may ask. Well, it may not be apparent, but there is a plenty, although, as the authors of Winning Ways write assertively, "Life's problems are hard!" Many among the finest mathematicians devoted their time to the study of cellular automata: John von Neumann and Stanislaw Ulam were among the pioneers in the field.

Are all Life configurations have an ancestor? According to Winning Ways, the answer is No. There is also a proof that such a configuration, which are appropriately called Garden(s) of Eden, exists that fits into a 2325816000×2325816000 grid square. A smaller paradise has been found with the help of computers, the size of 9×33.

The authors of Winning Ways also show how Life patterns can imitate computers. The gliders, that is, the patterns that move across the board staying in a fixed size moving frame, play an important role in their theory.

This alone may justify a widespread involvement of Life enthusiasts in the search for glider patterns. David Epstein's site is a good starting point for the curious.

References

  1. M. Gardner, Wheels, Life and Other Mathematical Amusements, W. H. Freeman and Co, 10th printing, 1999
  2. E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, v4, AK Peters, Ltd. (March 30, 2004)

Cellular Automaton

  1. Life-like Automaton With Definable Rules
  2. Sierpinski's Gasket and Dihedral Symmetry
  3. Simple Cellular Automaton
  4. The Game of Life

Copyright © 1996-2008 Alexander Bogomolny



Search:
Keywords: