CELLULAR AUTOMATA AND CONWAY'S GAME OF LIFE

http://hensel.lifepatterns.net/

OVERVIEW

Conway's game of Life was invented by John Horton Conway and was described in Scientific American's Mathematical Games column back in the early 70's. The "game" (placed in quotes because there are actually no players - the outcome is decided by the pattern initially chosen) is played on a grid of "cells" which are represented as squares). Each cell is either "alive" or "dead". The cells live or die from generation to generation depending upon whether they are already alive or not, and how many living neighbors (hereafter called simply "neighbors") they currently have.

THE NEIGHBORHOOD RULES FOR CONWAY'S "GAME"

Deaths: A live cell will die if it has either too few or too many neighbors:

0 or 1 neighbor: the cell will die.

4 or more neighbors: the cell will die.

(hence, if a living cell has two or three neighbors, it will remain alive for the next generation.)

Births: A cell will become alive if it has exactly 3 neighbors.

A CONVENIENT SHORTHAND

The shorthand way for writing this "rule" is 2,3/3, meaning that a living cell remains alive next generation if it has 2 or 3 neighbors, and a non-living cell comes to life if it has exactly three neighbors. (Note: this shorthand allows us to write many rules - e.g. 1,2,4/2,4, etc. But only 2,3/3 is the "Conway life" rule, which is a subset of a large number of "Cellular Automata" rules.)

NEIGHBORHOOD DEFINED

The neighborhood will be each square that a king could move to on a chessboard. That is, a cell can have vertical, horizontal, and/or diagonal neighbors.

A SIMPLE EXAMPLE

Look at the grid below. The white squares are dead cells, and the blue squares are live cells. We start with three live cells in a central column.

Now we count the neighbors that each cell has. Here we have placed the neighbor count inside the cell position.

You see that the middle cell was alive and has two neighbors, so that it stays alive. The cells directly above and below the center have only one neighbor so they die. The cells to the right and left of the center (currently not alive) have three neighbors, so they become alive. There are other cells with one or two neighbors but they were not alive to start with so they stay dead. Hence, the next generation looks like this:

Note that this pattern will flip back and forth, There are many interesting patterns in the life

universe - most of them have been given rather whimsical names such as "glider", "spaceship", etc. The above pattern is called a "blinker." Below is another pattern. See if you can work out what it does.

SIGNATURES

Though not unique, obtaining signatures of forms that appear on a grid provides a means of distinguishing between different shapes. Basically, a signature is a vector containing neighbor information about all cells in the grid. The signature is represented as shown below:

(left part) (right part)

neighbors of live cells <> neighbors of dead cells

Each part gives the number of cells in the entire grid with a given count of live neighbors. To obtain the signature, we examine every cell in the grid (live or dead) and tally how many live neighbors it has. Consider the "blinker" (Conway's Life).

The neighbor count for each live cell and each dead cell is given below:

Notice that most dead cells have no live neighbors; hence this count is omitted from the right part of the signature.

The signature for the "blinker" would thus be:

0 0 0 0 0 0 1 2 0 <> 6 4 2 0 0 0 0 0

8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8

(the numbers on the line directly above are for reference only. These numbers are indices that indicate the count.)

Thus, there are two live cells with one neighbor; one live cell with two neighbors; six dead cells with one neighbor; four dead cells with two neighbors; two dead cells with three neighbors. We can omit all leading (and trailing) zeros, giving:

1 2 0 <> 6 4 2

Which is the actual way the signature would be read. An important characteristic of signatures is that a given shape has the same signature no matter how it is oriented. Of course, different phases of the same oscillator usually will have different signatures. In the case of the "blinker", the two phases are identical; hence the signature for the two phases it the same. **Note that when we add up the numbers in the left part, we get the total count of live cells.