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

by M. Mitchell Waldrop

Now, what's beautiful about all this, said Langton, is that once you've made the link between life and computation, you can bring an immense amount of theory to bear. For example, Why is life quite literally full of surprises? Because, in general, it is impossible to start from a given set of GTYPE rules and predict what their PTYPE behavior will be—even in principle. This is the undecidability theorem, one of the deepest results of computer science: unless a computer program is utterly trivial, the fastest way to find out what it will do is to run it and see. There is no general-purpose procedure that can scan the code and the input and give you the answer any faster than that. That's why the old saw about computers only doing what their programmers tell them to do is both perfectly true and virtually irrelevant; any piece of code that's complex enough to be interesting will always surprise its programmers. That's why any decent software package has to be endlessly tested and debugged before it is released—and that's why the users always discover very quickly that the debugging was never quite perfect. And, most important for artificial life purposes, that's why a living system can be a biochemical machine that is completely under the control of a program, a GTYPE, and yet still have a surprising, spontaneous behavior in the PTYPE.