Complexity: The Emerging Science at the Edge of Order and Chaos

by M. Mitchell Waldrop

No, the Game of Life computer would exist entirely within the von Neumann universe, in exactly the same way that Langton’s self-reproducing pattern did. It would be a crude and inefficient computer, to be sure. But in principle, it would be right up there with Seymour Cray’s finest. It would be a universal computer, with the power to compute anything computable. Now, that’s a pretty astonishing result, says Langton—especially when you consider that only comparatively few cellular automaton rules allow it to happen. You couldn’t make a universal computer in a cellular automaton governed by Class I or II rules, because the structures they produce are too static; you could store data in such a universe, but you would have no way to propagate the information from place to place. Nor could you make a computer in a chaotic Class III automaton; the signals would get lost in the noise, and the storage structures would quickly get battered to pieces. Indeed, says Langton, the only rules that allow you to build a universal computer are those that are in Class IV, like the Game of Life. These are the only rules that provide enough stability to store information and enough fluidity to send signals over arbitrary distances—the two things that seem essential for computation. And, of course, these are also the rules that sit right in this phase transition at the edge of chaos.