We have briefly examined two types of one-dimensional cellular automata - elementary and totalistic CAs. Many other types of cellular automata have been constructed and studied in detail. CAs have been constructed and studied in which all cells in a generation do not all reproduce simultaneously, and CAs have been studied in which only a few cells in a generation are allowed to reproduce at all. CA's constructed on non-square grids have been constructed and studied. While all of these different types of CAs produce patterns which differ in detail, they all seem to have the same character, more or less. They all behave essentially like the elementary CA's that we furst investigated. Surprisingly, more complicated rules don't really lead to much more complicated behavior. The complicated behavior that we saw seems to be already "built into" the simple elementary rules. It seems that very simple sets of rules really can produce complicated behavior!
Here is a short list of links to cellular automata and fractal sites - certainly not an exhaustive list, but rather a starting point for exploring.
|
| John H. Conway (Source) |
Two, and even three-dimensional cellular automata have also been developed and studied. One of the most interesting - well, at least one of the most famous - is the "Game of Life" invented by the mathematician/physicist John H. Conway and introduced in Martin Gardner's Scientific American mathematics column in 1970. The "Game of Life" is incredibly and totally mis-named. It isn't a game, in that you don't play it - there are no "moves" to make, and nobody wins - it is an automaton, you set it up and watch it go. It isn't alive, either - although once you see the Game of Life in action you will understand the "Life" part.
Although innumerable variations of the Game of Life have been developed, the original is "played" using two colors/states (white/black or dead/alive) on a two-dimensional rectangular grid. The rules are very simple: Given an initial generation of cells, the next generation is determined as follows:
| Description | Digram |
|---|---|
| Suppose we start with three adjacent "live" cells in a horizontal row, as shown at right. |  |
| Looking at the surrounding cells, there will be two new cells "born" in the next generation. |  |
| Looking at the currently-living cells, two will "die" and the center cell will "survive" into the next generation. |  |
So, the next generation of cells looks like this. This is just the original array of cells turned through 90 degrees, so that in the next generation the result will be the original array, as shown below. |
 |
After two generations, we get the original configuration! This arrangement of cells will simply alternate from a horizontal row to a vertical row in each succeeding generation. Many patterns have been studied and named in the Game of Life. This simple configuration is called a "blinker." and is an example of a oscillator of period 2. |
|
Here is a (very) brief and cursory look at some of the more-interesting configurations found in the Game of Life.
| Description | Image |
|---|---|
The 4x4 array of cells shown in the upper-left of the image at right is called a "block."The "block" never changes - no cells are born, and none ever die. It is an example of a "still life." The lower image is the "bee hive", another "still life." |
 |
| The "beacon" is a period-2 "oscillator." |  |
| The "glider" is a simple example of a "space ship." |  |
| Some patterns last a long time before dying out or becoming static. They are called "methuselas". The "r -pentomino" (a pentomino is any shape constructed of 5 adjacent cells) lives for 1103 generations before becoming a static pattern of 116 cells. It creates 6 gliders during its lifetime. |  |
| The "diehard" is another very simple (only 7 cells) "methuselah." It dies out after about 130 generations. |  |
There are lots of other types of "creatures" in the Game of Life - puffers, rakes, glider guns, breeders, loops, space ships, etc.
The images shown above hardly exhaust the vast array of "creatures" to be found in the Game of Life. Creating generation after generation by hand on graph paper can be very tedious and error prone (although that is how the Game of Life was originally done!). Fortunately, the Internet is littered with programs and applets that allow you to explore the Game of Life. In class, we will use a partiularly-well-done program called "Golly." Not only is Golly a great program, it has the additional benefit of being free!
Your instructor (who is NOT a Golly expert, by the way) will give you an introduction to using the program and some suggestions for exploring the Game of Life using Golly. Have fun!