blog.ddtor.com

Introduction to

The Edge of Chaos

http://math.hws.edu/xJava/CA/EdgeOfChaos.html

Cellular automata might seem like very simple things, but they are related to some very deep questions. For example (to get right to the big one): how do interesting, complex systems, such as living things, arise in a world where one of the most fundamental principles is that entropy, that is disorder, always increases?

Could CA's really have anything to do with such important philosophical questions? Some people think so, in particular people involved in the new field of "artificial life". These people would like to simulate life in a computer (or, maybe, create real computer life). Cellular automata--if they have enough states and rules to give them complex, interesting behavior--are seen as a candidate for artificial life. Patterns of cells in CA's can sometimes display lifelike behaviors, including reproduction. It might be that one-dimensional cellular automatons can never be complex enough to support artificial life, but two-dimensional CA's have been shown to be just as complex as computers themselves, so that if artificial life is possible in computers, then it should be possible in CA's too.

Christopher Langton, one of the founders of artificial life, began his work by studying one-dimensional cellular automata. He thought of one of the states of an automaton as being "dead". All the remaining states were thought of as "alive". Langton only worked with automata with the property that if a cell and are its neighbors are dead, then that cell will remain dead in the next generation.

Now, some CA's are boring because all the cells die out in a few generations or because they quickly settle into simple repeating patterns. Langton said that these CA's were highly "ordered". Their behavior is boring because it is extremely predicatable and easy to describe, so there is not much to say about them. Other CA's are boring because their behavior seems for all intents and purposes to be random. Langton called such CA's "chaotic". Their behavior is boring because it is completely unpredictable, and can only be described as a mass of unrelated details.

But some CA's display interesting, complex, almost lifelike behavior. Langton said that these CA's are near the border between order and chaos. If they were more ordered, they would be too predictable to be interesting; if they were less ordered, they would be too chaotic.

Langton defined a simple number that can be used to help predict whether a given CA will fall in the ordered realm, in the chaotic realm, or near the boundary, on the "edge of chaos." The number can be computed from the rules of the CA. It is simply the fraction of rules in which the new state of the cell is living. (The rule in which a cell and all its neigbors are dead is not counted, since Langton assumed that the new state in this rule is always death.) He called this parameter "lambda."

The lambda parameter of a CA is a number between 0 and 1. If lambda is 0, then all cells die immediately, since every rule leads to death. If lambda is 1, then any cell that has at least one living neighbor will stay alive in the next generation and, in fact, forever. More generally, values of lambda close to zero give CA's in the ordered realm. Values close to 1 give CA's in the chaotic realm. The edge of chaos is somewhere in between.

Unfortunately, we can't simply say that there is a value of lambda that represents the edge of chaos. It's more complicated than that. Here is what Langton found: Suppose you start with a CA with lambda equal to zero, where all rules lead to death. Now, suppose you randomly modify rules one-by-one so that the new rules lead to life instead of death. This causes the lambda value to increase. As you do this, you get a sequence of CA's with lambda values increasing from zero to one. At the beginning, the CA's are highly ordered; at the end they are chaotic. Somewhere in between, at some critical value of lambda, there will be a transition from order to chaos. It is near this transition that the most interesting CA's tend to be found, the ones that have the most complex behavior.

As I've said, though, the critical value for lambda is not a universal constant; it depends on the "path" chosen through the space of CA's. To apply Langton's ideas in the search for interesting CA's, you have to construct such a path and wander along it, looking for the transition between order and chaos. The EdgeOfChaosCA, which is described on the next page let's you do just that.

By the way, does this have anything at all to do with the origin of actual life? Some people think so. They claim that evolution tends to push systems towards the edge of chaos, where complex, interesting behaviors such as life can occur. If you are intrigued by this idea, see the bibliography page. You'll find some suggested readings on cellular automata, complexity, evolution, and the edge of chaos.

The next page describes an applet that you can use to explore cellular automata, Langton's lambda parameter, and the edge of chaos.

==========

Bibliography

Cellular Automata and the Edge of Chaos

Here are a few places you can go to read more about cellular automata and the idea that complex, interesting things happen on the edge of chaos, on the boundary between boring order and overwhelming disorder.

Steven Levy, Artificial Life. Pantheon Books, 1992. An exciting, interesting book, written for a general audience. Read it. You'll find cellular automata, the edge of choas, emergence, and lots more.

M. Mitchell Waldrop, Complexity: The Emerging Science at the Edge of Order and Chaos. Simon and Schuster, 1992. Another well-written book for a general audience, concentrating on the Santa Fe Institute. The edge of chaos is a central idea.

Stuart Kauffman, At Home in the Universe: The Search for Laws of Self-organization and Complexity. Oxford University Press, 1995. Kaufmann explains his ideas about how various forms of complexity, including life itself, can arise from simple rules. The "Edge Of Chaos" idea plays a large role in his thinking.

Christopher Langton, "Computation at the Edge of Chaos: Phase Transitions and Emergent Computation." In Emergent Computation, edited by Stephanie Forest. The MIT Press, 1991. Pages 12-37. A technical paper in which Langton explains his investigation of one-dimensional cellular automata and discusses his "lambda" parameter.

Christopher Langton, editor, Artificial Life. Addison-Wesley Publishing Company, Reading, 1989. The procedings of the first artificial life workshop, held in 1987 at the Los Alamos National Laboratory. Technical papers. Includes an introductory survey by Langton of the field of artificial life.