Conway's Game Of Life

Computer simulation.  A two-dimensional grid (of boolean) of cells.  A cell is either alive or dead.  The player fills in the grid with living or dead cells as they choose.

At each time step:
	A living cell adjacent to exactly two or three living cells remains alive.
	A living cell adjacent to exactly one or zero living cells dies of loneliness.
	A living cell adjacent to four or more living cells dies of overpopulation.
	A dead cell adjacent to exactly three living cells becomes alive.  (Strangely, every cell is a product of three parents.)

So, the way the game is normally played, you choose your initial configuration and just let it run time step after time step, until one of the following happens:

ON A FINITE GRID,

EXTINCTION.  There is no longer any living cell.

STABILITY.  Each time yields a grid that is exactly the same as the previous time step.

OSCILLATION / REPETITION.  You eventually hit a pattern that repeats itself every fixed number of cycles.  (It's called oscillation if the cycle length is 2.)

_ _ _ _ _     _ _ _ _ _    _ _ _ _ _
_ _ _ _ _     _ _ X _ _    _ _ _ _ _
_ X X X _     _ _ X _ _    _ X X X _    OSCILLATION  (repeating cycle of 2)
_ _ _ _ _     _ _ X _ _    _ _ _ _ _
_ _ _ _ _     _ _ _ _ _    _ _ _ _ _



_ _ _ _ _
_ _ X X _    STABILITY
_ _ X X _
_ _ _ _ _
_ _ _ _ _


X X X X X      X _ _ _ X     _ _ _ _ _
X X X X X      _ _ _ _ _     _ _ _ _ _
X X X X X      _ _ _ _ _     _ _ _ _ _    EXTINCTION
X X X X X      _ _ _ _ _     _ _ _ _ _
X X X X X      X _ _ _ X     _ _ _ _ _

The Game of Life can be used to generate all sorts of clever animations, including hyaving shapes move around the screen, having shapes "shoot" other shapes that move across the screen.

If the Game of Life is extended to an infinite grid, then we have situations where the game runs forever, but without a repeating cycle.  For example, a shape might move right forever, there not be a boundary to limit it.

It turns out that the Game of Life is Turing-complete.  This means that with appropriate input encoding, you can write "programs" to "accept input" and if you achieve stability, the patterns will resemble the outputs aka "correct" answers from the stability, provided that you are to interpret the output properly.


WONDERFUL EXAMPLE of distributed computing.  Each processor represents a cell in the grid.  It keeps track of whether it's alive or dead.  At each time step it sends a message to its neighbors (up to eight of them) as to whether it's alive.  It receives up to eight messages from its neighbors letting the cell know which of its neighbors are alive or dead.  Then the cell decides whether it is alive or dead in the next time step.  At each time step, each cell transmits its status to the "master" process which then prints out the grid.

If you're doing, say, a 5x5 grid, you might do it with 26 processors.  One of each of the 25 cells, and one for the master process.