Complexity_ A Guided Tour - Melanie Mitchell [71]
FIGURE 10.4. (a) An illustration of a one-dimensional lattice whose ends wrap around in a circle; (b) A particular elementary cellular automaton rule (Rule 110) expressed as a list of three-cell configurations and corresponding update states for the configuration’s center cell; (c) A space-time diagram, showing four successive configurations of the cellular automaton.
Since there are only eight possible configurations of states for a three-cell neighborhood (cf. figure 10.4b) and only two possible ways to fill in the update state (on or off) for each of these eight configurations, there are only 256 (28) possible rules for elementary cellular automata. By the 1980s, computers were powerful enough for Wolfram to thoroughly investigate every single one of them by looking at their behavior starting from many different initial lattice configurations.
Wolfram assigned an identifying number to each elementary cellular automaton rule as illustrated in figure 10.5. He called the on state “1” and the off state “0,” and wrote the rule’s update states as a string of 1s and 0s, starting with the update state for the all on neighborhood and ending with the update state for the all off neighborhood. As shown, the rule given in figure 10.4 is written as 01101110. Wolfram then interpreted this string as a number written in binary (i.e., base 2). The string 01101110 in binary is equal to the number 110 in decimal. This rule is thus called “Rule 110.” As another example, the rule with update states 00011110 is “Rule 30.” (See the notes for a review on how to convert base 2 numbers to decimal.)
FIGURE 10.5. An illustration of the numbering system for elementary cellular automata used by Stephen Wolfram.
FIGURE 10.6. Rule 110 space-time diagram. The one-dimensional cellular automaton lattice has 200 cells, which are shown starting with a random initial configuration of states, and updating over 200 time steps.
Wolfram and his colleagues developed a special programming language, called Mathematica, designed in part to make it easy to simulate cellular automata. Using Mathematica, Wolfram programmed his computer to run elementary cellular automata and to display space-time diagrams that show their behavior. For example, figures 10.6 and 10.7 are plots like that given in figure 10.4, just on a larger scale. The top horizontal row of figure 10.6 is a random initial configuration of 200 black and white cells, and each successive row is the result of applying Rule 110 to each cell in the previous row, for 200 time steps. The plot in figure 10.7 shows the pattern created by Rule 30, starting from a random initial configuration.
FIGURE 10.7. Rule 30 space-time diagram, with an initial configuration of random states.
Looking at figures 10.6 and 10.7, perhaps you can sense why Wolfram got so excited about elementary cellular automata. How, exactly, did these complex patterns emerge from the very simple cellular automaton rules that created them?
Seeing such complexity emerge from simple rules was evidently an epiphany for Wolfram. He later said, “The Rule 30 automaton is the most surprising thing I’ve ever seen in science…. It took me several years to absorb how important this was. But in the end, I realized that this one picture contains the clue to what’s perhaps the most long-standing mystery in all of science: where, in the end, the complexity of the natural world comes from.” In fact, Wolfram was so impressed by Rule 30 that he patented its use as part of a pseudo-random number generator.
In Wolfram’s exhaustive survey of all 256 elementary cellular automata, he viewed the behavior over time of each one starting from many different initial configurations. For each elementary cellular automaton and each initial configuration, he applied the cellular automaton rule to the lattice for a number