artificial life

Chapter 3: Cellular Automata

3.5 One Dimensional Cellular Automata

Physicist Stephan Wolfram developed another interesting example of cellular automata. Before Wolfram’s work CA’s were generally created on “boards”, which were 2-dimensional lattices. The researchers studied the CA’s to understand complex systems. Wolfram recognized that they were making their task unnecessarily complex. Wolfram simplified the Cellular Automata to a one-dimensional lattice; a vector of cells. When CA’s are represented in two-dimensions the only way to observe their state changes is by watching an animation or by viewing them as a 3-dimensional lattice, with time as the third dimension. Neither of these options is very good for observing, recognizing and analyzing patterns. By making the lattice one-dimensional it is possible to view the CA over time in only 2-dimensions. The initial state of the CA is placed on the first line of an image. Applying the rule set to the first line creates the next line of the image.

Figure 3.5 shows one such image created from a one-dimensional cellular automaton. In this automaton the neighborhood for a cell are the cells immediately adjacent to it and the cell itself. There are two different states for the automaton: dark (on) and white (off).

In figure 3.6 the automaton is seeded with a single cell in the on state. More interesting are the automata seeded with a vector of random on and off states. Figure 3.6 depicts such an automata. This automata has the same rule set as the automaton in Figure 3.5, but is initialized at random. This automaton also uses “wrapping”, where the cells on either end of the vector look at the state of cells at the other extremity of the automaton to determine their state.

Unlike Conway's Game of Life, Wolfram tested more than one set of rules for his construct. In the automaton of Figures 3.5 and 3.6 there are 256 different rule sets, 8 rules per rule set, each of which can have one of two different states; 28 = 256 rule sets. There are infinitely many different types of one-dimensional CA’s because it is possible to increase the neighborhood of the cells or increase the number of possible states for a cell. Wolfram was able to exhaustively study the automatons with rule sets similar to those used by the automata in Figures 3.5 and 3.6. After observing them he identified 3 different classes based upon their complexity.

The first Class of CA’s are those that quickly deteriorate into a homogenous state, all off or all on. Class 2 CA’s are those that stabilize into a simple pattern or exhibit some sort of periodicity. Figure 3.7 depicts Class 1 and Class 2 automata.

The third class of cellular automata are those that never settle into a simple pattern. Instead they form an image that is complex, but still recognizable regardless of how the automaton is seeded. Figure 3.8 shows two different automata, both have the same rule set, but have been seeded with different random vectors.

The images produced by these Cellular Automata are similar to patterns found in nature. An example that Wolfram found was that of mollusk shells, which have coloration patterns very similar to the patterns seen in Figure 3.8. Such patterns, identifiable in similar configurations of 1-D CA’s, are thought of as a type of ‘strange attractor’.

;Wolfram also identified a 4th class of Cellular Automata. These are CA’s that are complex enough to be considered universal machines. Conway’s Game of Life is such a CA. In order to produce a Class 4 CA in one-dimension it is necessary to increase the neighborhood from 3 cells to 5 cells (a radix of 2 cells). The rules for this CA are similar to those of the game of life. If and only if 2 or 4 of the cells in a cell’s neighborhood are on during the current generation will the cell be on in the next generation.