A one-dimensional cellular automaton consists of two things: a row of "cells" and a set of "rules". (There are also two-dimensional cellular automata, which use rectangular grids of cells, but from now on when I say "cellular automaton" or just "CA", I will mean "one-dimensional cellular automaton".)
Each of the cells can be in one of several "states". The number of possible states depends on the automaton. Think of the states as colors. In a two-state automaton, each of the cells can be either black or white. Of course, you might just as easily use purple and orange to represent the states, if you thing that's prettier. In a three-state automaton, the states might be black, red, and blue.
A CA doesn't just sit there. Over time, the cells can change from state to state. The cellular automaton's rules determine how the states change. It works like this: When the time comes for the cells to change state, each cell looks around and gathers information on its neighbors' states. (Exactly which cells are considered"neighbors" is also something that depends on the paticular CA.) Based on its own state, its neighbors' states, and the rules of the CA, the cell decides what its new state should be. All the cells change state at the same time. You should think of the row of cells as a miniature "world" that runs through a sequence of "years" or "generations." At the end of each year, all the cells simultaneously decide on their state for the next year.
When a CA is simulated on a computer, it's a good idea to have two rows of cells. One row is the actual world; the other is used as a convenient place for computing the cells' states in the next year. After all the cells have been processed, the new world can replace the old.
This might make more sense after you see it in action. Click on the following applet to see it compute a new generation of cells.
Click to compute the New World
This applet shows a two-state automaton, in which a cell can be either black or white. Each cell has three neighbors (counting itself). The rules for this CA say that if all three of these cells are white, then the new state of the cell will be white; if all three of the cells are black, then the new state of the cell will also be white; in any other case, the new state of the cell will be black.
As the applet animation runs, the three cells that are being considered are framed in blue. In the New World, the cell that is being computed is also framed in blue. After states have been computed for all the cells, the states in The World are replaced by the states in the New World. This operation can then be repeated over and over to produce suceeding generations of cells.
In fact, when CA's are displayed, they are not usually shown as a single row of cells that changes with time. Instead, the second gernation of cells is drawn under the first, then the third generation is drawn under the second, and so on. This produces a potentially very nice two-dimensional pictures, in which you see the whole evolution of the CA through time. This is what is done for the CA on the index page, which uses the same rules as the CA in the above demonstration. I find it surprising that such simple rules can produce such complicated and interesting patterns.
A nice way to visualize the rules of a CA is to show a cell and its neighbors with the new state of the cell shown beneath. The rules for our simple example CA can then be shown in pictorial form as follows:
In this case, there are 8 rules because there are 8 possible ways to set the states of the cell's three neighbors. In general, if there are K states and if each cell is taken to have N neighbors (including itself), then there are KN rules. (That's K raised to the power N, or K multiplied by itself N times.) To specify a CA, you have to say what the new state will be for each of the KN rules. The number of different ways of doing this--that is, the number of different CA's with K states and N neighbors--is K raised to the power KN. Even for moderate values of K and N, this can be almost unimaginably large.
One final small note: A neighborhood in the sample CA consists of a cell and the cells to its left and to its right. However, the cell at the left end of the row doesn't have a neighbor to its left, and the cell at the right end of the row lacks a neighbor on its right. This problem is solved by pretending that the two ends of row are joined. The cell at the left end is considered to neighbor on the cell on the right end. In effect, the world is really a circle of cells rather than a row. You can see how this works if you watch the demo carefully as it computes new values for the cells on the left and right ends of the world.
The next page describes an applet that will let you handcraft CA's and help you to understand them better.
[Index] [Next] [HandCraftCA Applet] [EdgeOfChaos Applet, Version 1] [EdgeOfChaos Applet, Version 2] [Eck's Java Page]