Complexity_ A Guided Tour - Melanie Mitchell [72]
Class 1: Almost all initial configurations settle down to the same uniform final pattern. Rule 8 is an example of this class; for all initial configurations, all cells in the lattice quickly switch to the off state and stay that way.
Class 2: Almost all initial configurations settle down to either a uniform final pattern or a cycling between a few final patterns. Here, the specific final pattern or patterns depends on the initial configuration.
Class 3: Most initial configurations produce random-looking behavior, although triangles or other regular structures are present. Rule 30 (figure 10.7) is an example of this class.
Class 4: The most interesting class. As described by Wolfram: “class 4 involves a mixture of order and randomness: localized structures are produced which on their own are fairly simple, but these structures move around and interact with each other in very complicated ways.” Rule 110 (figure 10.6) is an example of this class.
Wolfram speculated that, because of this complexity of patterns and interactions, all class 4 rules are capable of universal computation. However, in general it is hard to prove that a particular cellular automaton, Turing machine, or any other device is universal. Turing’s proof that there exists a universal Turing machine was a triumph, as was von Neumann’s proof that his self-replicating automaton was also a universal computer. Since then several researchers have proved that simple cellular automata (such as the Game of Life) are universal. In the 1990s, Matthew Cook, one of Wolfram’s research assistants, finally proved that Rule 110 was indeed universal, and is perhaps the simplest known example of a universal computer.
Wolfram’s “New Kind of Science”
I first heard about Cook’s result in 1998 when he spoke at a workshop at the Santa Fe Institute. My own reaction, like that of many of my colleagues, was “Very cool! Very ingenious! But not of much practical or scientific significance.” Like the Game of Life, Rule 110 is an example of a very simple deterministic system that can create unpredictable complex behavior. But in practice it would be very difficult to design an initial configuration that would result in a desired nontrivial computation. Moreover, Rule 110 would be an even slower computer than the Game of Life.
Wolfram’s view of the result is very different. In his 2002 book, A New Kind of Science, Wolfram interprets the universality of Rule 110 as strong evidence for “a new law of nature,” namely, his Principle of Computational Equivalence. Wolfram’s proposed principle consists of four parts:
The proper way to think about processes in nature is that they are computing.
Since even very simple rules (or “programs”) such as Rule 110 can support universal computation, the ability to support universal computation is very common in nature.
Universal computation is an upper limit on the complexity of computations in nature. That is, no natural system or process can produce behavior that is “noncomputable.”
The computations done by different processes in nature are almost always equivalent in sophistication.
Got that? I admit, it’s kind of hard to figure out what this principle means, and a major purpose of Wolfram’s 1,200-page book is to explicate this principle and show how it applies in very diverse areas of science. I read the whole book, and I still don’t completely understand what Wolfram is getting at here. However, I’ll give my best gloss on it.
What Wolfram means by “processes in nature are computing” is something like what you see in figures 10.6 and 10.7. At any given time a cellular automaton possesses information—the configuration of states—and processes information by applying its rule to its current configuration. Wolfram believes that natural systems work much the same way—that they contain information and process that information according to simple rules. In A New Kind of Science (or “NKS” as it is