artificial life
Chapter 3: Cellular Automata
3.2 Cellular Automata
Langton and von Neumann both created creatures that existed in environments broken down into discrete cells. These systems were called Cellular Automata. Both Langton's Loops and von Neumann's creature were complex and highly structured forms of Cellular Automata (CA's).
A d-dimensional Cellular Automata is made up of a d-dimensional lattice of discrete cells. Each cell on the lattice is basically a finite state machine. The state is determined by rules that apply to all the cells in the lattice.
These rules take into account the state of the cell and the states of cells in the cell's local neighborhood. The neighborhood of cells is dependant upon the rules of the CA. Figure 3.1 shows different possible neighborhoods for a cell. The dark cells indicate the neighborhood of the center cell.
Figure 3.1: Cell Neighborhood
The CA updates the states of all of the cells in the lattice for every time increment. Figure 3.2 shows six time intervals of a 2-dimensional Cellular Automaton. This automaton has only two different states per cell. The rules of this automaton are simple: For any given cell c, if the cell immediately to its left is "on" or "live" at time T-1, the cell c will be alive at time T. In this automaton, the neighborhood includes only the cell immediately to the left of the cell in question.
Figure 3.2 : Progression of a 2-d CA
Another item of note for the cellular automaton in Figure 3.2 is that the lattice "wraps-around". If a cell is bordering on the left-most edge of the lattice, it checks the state of the rightmost cell in its row to determine its state in the next generation.
Cellular Automata are interesting in terms of Artificial Life because sometimes groups of cells appear to have emergent behavior. The individual loops in Langton's experiment are examples of 'organisms' made up of cells in a Cellular Automata.