A cellular automaton (CA) is defined by four attributes:
1. The state space, the model of the world, a collection of cells.
2. The neighborhood (nbhd) of a cell. Those cells whose current states affect the next state of a cell.
3. The number of states a cell can assume. This measures the level of detail at which we view the cells.
4. The rule of the CA: how the current states of the cells in the nbhd determine the next state of a cell.
This seems awfully simple, especially if the number of states is few and the neighborhood size small. As a hint of the possible richness involved, we calculate the number of CA rules.
We have already seen with S states per cell and N cells per nbhd, there are SN neighborhood configurations. A rule specifies eaxctly which of the S possible states results from each of the SN neighborhood configurations. Suppose we number the neighborhood configurations 1 through SN. Then there are S outcomes for configuration 1 and S outcomes for configuration 2, so S2 combinations of outcomes for configurations 1 and 2.
Suppose S = 2, and write the states as 0 and 1. Then the combinations for the first two neighborhood configurations are
00, 10, 01, 11
Continuing, there are S3 combinations of outcomes for configurations 1, 2, and 3. For S = 2, here are the combinations for the first three neighborhood configurations
000, 100, 010, 110, 001, 101, 011, 111
In general, there are S(SN) rules. How large is this number?
S = 2, N = 3 gives 2(23) = 28 = 256 rules. Spending one minute investigating each rule, one person could see all the possibilities in 4 and 1/4 hours, a single afternoon.
S = 2, N = 5 gives 2(25) = 232 = 4,294,967,296 rules. At one second per rule, a person would have to work 24 hours a day, every day without interruption for 136 years.
S = 2, N = 9 (two-dimensional Moore neighborhood automata) gives 2(29) = 2512 rules. How big is this number? If every elementary particle in the universe were a supercomputer examining a trillion CA per second, starting at the Big Bang, by now only one part in 1044 would have been examined. Failing some fundamental advance in the physics of computation (superstring computers working at superstring frequencies?), we will never, Never, NEVER see all the possibilities.
What happens for S = 3? As a hint of what this small increase in
S will do, note that for N = 3 we have
Cellular automata are used to model physical, chemical, biological, and social interactions. For many of these the exact positions of live cells in the neighborhood is not as important as the number of live cells. Such CA are called totalistic. We are interested in an extension of this notion called outer totalistic.
Continue to 4. C. Examples of Cellular Automata Patterns
Return to 4. A. The Paradox of Self-Replicating Machines
Return to 4. Cellular Automata and Fractal Evolution