Complexity_ A Guided Tour - Melanie Mitchell [70]
It’s fascinating to see that something as simple to define as the Life cellular automaton can, in principle, run any program that can be run on a standard computer. However, in practice, any nontrivial computation will require a large collection of logic operations, interacting in specific ways, and it is very difficult, if not impossible, to design initial configurations that will achieve nontrivial computations. And even if it were possible, the ensuing computation would be achingly slow, not to mention wasteful, since the huge parallel, non-von-Neumann-style computing resources of the cellular automaton would be used to simulate, in a very slow manner, a traditional von-Neumann-style computer.
For these reasons, people don’t use Life (or other “universal” cellular automata) to perform real-world computations or even to model natural systems. What we really want from cellular automata is to harness their parallelism and ability to form complex patterns in order to achieve computations in a nontraditional way. The first step is to characterize the kinds of patterns that cellular automata can form.
The Four Classes
In the early 1980s, Stephen Wolfram, a physicist working at the Institute for Advanced Study in Princeton, became fascinated with cellular automata and the patterns they make. Wolfram is one of those legendary former child prodigies whom people like to tell stories about. Born in London in 1959, Wolfram published his first physics paper at age 15. Two years later, in the summer after his first year at Oxford, a time when typical college students get jobs as lifeguards or hitchhike around Europe with a backpack, Wolfram wrote a paper in the field of “quantum chromodynamics” that caught the attention of Nobel prize–winning physicist Murray Gell-Mann, who invited Wolfram to join his group at Caltech (California Institute of Technology). Two years later, at age twenty, Wolfram received a Ph.D. in theoretical physics. (Most students take at least five years to get a Ph.D., after graduating from college.) He then joined the Caltech faculty, and was soon awarded one of the first MacArthur Foundation “genius” grants. A couple of years later, he was invited to join the faculty at the Institute for Advanced Study in Princeton.
Stephen Wolfram. (Photograph courtesy of Wolfram Research, Inc.)
Whew. With all that fame, funding, and the freedom to do whatever he wanted, Wolfram chose to study the dynamics of cellular automata.
In the spirit of good theoretical physics, Wolfram set out to study the behavior of cellular automata in the simplest form possible—using one-dimensional, two-state cellular automata in which each cell is connected only to its two nearest neighbors (figure 10.4a). Wolfram termed these “elementary cellular automata.” He figured that if he couldn’t understand what was going on in these seemingly ultra-simple systems, there was no chance of understanding more complex (e.g., two-dimensional or multistate) cellular automata.
Figure 10.4 illustrates one particular elementary cellular automaton rule. Figure 10.4a shows the lattice—now just a line of cells, each connected to its nearest neighbor on either side. As before, a cell is represented by a square—black for on, and white for off. The edges of the lattice wrap around to make a circle. Figure 10.4b shows the rule that each cell follows: for each of the eight possible state configurations for a three-cell neighborhood, the update state for the center cell is given. For example, whenever a three-cell neighborhood consists of all off states, the center cell should stay off at the next time step. Likewise, whenever a three-cell neighborhood has the configuration off-off-on, the center cell should change its state to on at the next time step. Note that the term rule refers to the entire list of configurations and update states, not to the individual lines in the list. Figure 10.4c shows a space-time diagram for this cellular automaton. The top row of cells is the one-dimensional lattice set up with a particular initial configuration of on and