Complexity is Elusive
Researchers need enormous computer power to forecast changes in the Earth’s climate, but they can predict the speed of a ball rolling down a ramp with pencil and paper. Stephen Wolfram claimed in his 2002 best seller, A New Kind of Science, that there is a clear dividing line between complex problems that require computer crunching and those for which equations alone will do. He argued that many important problems are more like the climate than the ball. But according to the 20 February PRL, his definition of complexity is imperfect because many of the problems he classified as complex are easily solved, as long as you can accept approximate answers. The results suggest that the traditional approach of physics–the equivalent of pencil and paper–is more widely applicable than Wolfram’s analysis implies.
Wolfram’s book describes checkerboard-like arrays of colored squares (“cells”), called cellular automata, which are generated by following simple rules. For example, the Game of Life, described in 1970 [1] follows the rule that if two or three of the neighbors of a black cell are currently black, it will remain black in the next update of the picture; if it is currently white, it will become black if it has three black neighbors. The rule runs over and over, continually changing the picture in surprisingly complex ways.
Many rules quickly settle into simple patterns, such as unchanging, oscillating, or random. But some rules generate complex patterns that are “computationally irreducible,” meaning there are no shortcuts to predict what they will do. Unlike electric circuits or cannon balls, you can’t find the result by plugging numbers into equations; you have to run the program to see what happens. Wolfram suggests that rules like these govern much of the natural world, such as the climate or highway traffic, so precise mathematical predictions are impossible for most of the important phenomena.
“It is tempting to conclude from this that the enterprise of physics is doomed from the outset,” write Navot Israeli and Nigel Goldenfeld, of the University of Illinois at Urbana-Champaign. But precise predictions aren’t always necessary. For example, the temperature and pressure of a gas can be accurately described without knowing about the motion of every molecule. “We tried to see what would happen if you asked only approximate questions,” says Goldenfeld.
So Israeli and Goldenfeld sought ways to replace several cells of an automaton with a single cell, “fuzzing out” the details of the picture–like making a low-resolution digital image from a higher-resolution version. The team also devised a new rule for the low-resolution automaton that would lead to the same long-term behavior as the original automaton if it were fuzzed at the end.
The researchers found that for some rules, the low-res version behaved simply and predictably, even when the high-res version was computationally irreducible and therefore unpredictable. In other words, the complexity was only in the unimportant details. Goldenfeld concludes that if you only need approximate results, they are predictable in many complex problems, and “computational irreducibility is not the right way to measure complexity.”
Wolfram says the “nice, small paper” is useful, if not very surprising. The interesting issue, he says, is “under what circumstances will large-scale rules emerge” that allow a simple, predictable description of a complex phenomenon.
–Don Monroe
Don Monroe is a freelance science writer in Murray Hill, New Jersey.
References
- M. Gardner, Scientific American 223, 120 (October 1970); Martin Gardner’s “Mathematical Games” http://ddi.cs.uni-potsdam.de/HyFISCH/Produzieren/lis_projekt/proj_gamelife/ConwayScientificAmerican.htm column described the Game of Life, invented by John Horton Conway of the University of Cambridge, UK.
More Information
Stephen Wolfram’s A New Kind of Science Online
Java applet demonstrating the Game of Life