MY AMERICAN SCIENTIST
SEARCH

HOME > PAST ISSUE > July-August 2002 > Article Detail

COMPUTING SCIENCE

# Playing by the Rules

Science is usually viewed as an inductive art, which starts with observations or experiments and proceeds toward laws of nature. Wolfram stands this process on its head, suggesting that we start by listing all possible laws of nature and then see which of them might correspond to observed events.

Is such a scheme feasible? If we set out to compile a catalogue of all conceivable natural laws, where would we begin, and how would we know when to stop? Wolfram answers by introducing abstract systems small enough and simple enough that we can enumerate all the rules or programs that might possibly govern their behavior. In these systems you don't have to go very far down the list before the rules start making toy worlds with interesting properties.

Wolfram first formulated these ideas in studies of cellular automata—geometric arrays of minimalist computing elements, called cells. Each cell in an automaton has a finite number of possible states, and it spends its time continually recomputing this state. To do so it looks at its own present state and at the states of a few neighboring cells, then applies a fixed rule to determine its next state. As soon as all the cells have updated their states in this way, the process starts over. All the cells use the same rule and operate in synchrony.

In the early 1980s Wolfram began a systematic survey of one-dimensional cellular automata, where the cells are arranged in a line or a ring. The operation of a one-dimensional automaton is particularly easy to visualize: If you draw the line of cells horizontally and show successive states of the system going down the page, the result is a two-dimensional spacetime diagram that reveals the entire evolution of the system.

Consider a one-dimensional automaton where the cells have just two possible states (black and white) and where each cell interacts only with its nearest neighbors. There are eight possible configurations of a cell and its two neighbors, and for each of these configurations the next state can be either black or white. Hence there are 28 possible rules for the evolution of the system. These 256 rules are all the available candidates for laws of nature in this tiny universe.

Can anything interesting ever happen in a world of such meager resources? Wolfram identifies four broad categories of behavior, which are illustrated in Figure 1. First are simple repetitive patterns, such as all white cells or all black cells, or alternation in stripes and checkerboards. The second category includes self-similar, fractal patterns, whose characteristic feature Wolfram describes as "nesting." In the third category are rules that generate apparent randomness; although the output is not a totally patternless spatter of black and white cells, the sequence of states of a single cell can have the statistical properties of a random series. Finally, a few rules yield localized structures that maintain their coherence while moving through the cellular space. These persistent structures are reminiscent of particles being created and annihilated in a quantum field theory.

It was the random patterns and the persistent structures that caught Wolfram's attention. Where does all that complexity come from? The naive assumption might have been that simple rules would yield only simple behavior, and the complexity of the pattern would grow steadily along with the complexity of the underlying rules. But Wolfram observed a different relation: There is a threshold of complexity. If the rules are kept simple enough to stay below the threshold, the outcome is always rather dull. (For example, a cellular automaton in which each cell's next state depends only on that same cell's present state is inevitably repetitious.) But once the rules get just a little more intricate, all four categories of behavior appear. What's more, once the system has crossed the threshold, further embellishments of the rules have little effect. New details may appear, but all the patterns can still be assigned to the same four basic categories.

To provide evidence in support of this last assertion, Wolfram surveys an exuberant variety of systems—some familiar, some novel, all interesting in their own right. He looks at cellular automata with more than two states per cell, including systems where the range of possible states is a continuum. He considers cellular automata in two and three dimensions. He studies automata where the cells are updated one at a time rather than simultaneously. Leaving behind the theme of cellular automata, he studies Turing machines and grammar-driven systems where substitution rules allow a string of symbols to grow and change. He looks at differential equations and at iterated numerical functions. He even examines the sequence of prime numbers. In each case his conclusion is the same: Simple sets of rules can generate complex outputs, but piling further complications onto the rules leads to little additional complexity in the outcome.