Cellular Automata: Complexity from Simplicity

Cellular automata is a fascinating field of research that spans several scientific disciplines. The idea is simple: Very basic mathematical rules can eventually produce extraordinarily complex behavior. A cellular automaton is defined as a "state machine that consists of an array of cells, each of which can be in one of a finite number of possible states." The idea is that a cell is switched on or off according to rules based on the state of its neighbors. If you think of a cell as being a square on an infinite sheet of graph paper, imagine its neighbors as being the eight squares that border it.

There is a game (and it is only loosely a game) called "Life," which was developed by mathematician John Conway. It follows three simple rules. (Note: A filled-in square is considered "alive," and a blank square is considered "dead.")

1. A dead cell with exactly three live neighbors becomes a live cell (birth).
2. A live cell with two or three live neighbors stays alive (survival).
3. In all other cases, a cell dies or stays dead (overcrowding or loneliness).

Simple as those rules are, the complexity of the interactions (considering that each neighbor also has a neighborhood that influences its behavior) presents a situation wherein it is essentially impossible to predict the outcome of an initial state (the initial state being some choice of live cells arranged on the grid).

If you go to this site, there is an applet that will run the game of Life on your computer in a separate window (you don't have to download anything). All you have to do is click on a few squares here and there to make an initial image and then click "Go." The computer will then apply the rules over successive generations, and your initial image will evolve. It will either stabilize into several groups of "still life" images that remain constant when the rules are applied, produce "gliders" that will move off indefinitely, produce "oscillators" that stay fixed in their positions, or the squares will blink out of existence altogether. There is also the possibility that the scene will evolve indefinitely and chaotically (this was originally not thought to be possible).

Try it out for yourself. After you try a few images of your own (hitting "Clear" to start over), try starting with the shape known as the r-pentomino, shown here:

You will be surprised to see how this one simple image of only five filled-in squares evolves over successive generations, not stabilizing until generation 1,103.

What is the point of all this? Well, some people, including Stephen Wolfram, theoretical physicist and creator of the Mathematica software, believe that cellular automata can go a long way toward explaining the evolution of complex systems—including perhaps life and the universe itself—based on simple rules. A simple one-page explanation of the principle in PDF format can be found here.

Play with it and have some fun! Prepare to become addicted.