To start reading Chapter 6 of A New Kind of Science, go here
Starting from Randomness
The Emergence of Order [p. 223]
In this chapter, Wolfram prepares to show how certain systems seem to produce regular classes of behavior, regardless of the initial conditions at which their evolution begins.
He first introduces examples where the evolution always goes to all black or all white, and then examples of where the evolution repeats in some simple pattern.
Four Classes of Behavior [p. 231]
We find, in fact, there appear to be four classes of behavior (called Wolfram Classes) of the evolution of CAs. Completely stable, simple repetitive, complex-no-traveling-structures, and complex-with-traveling-structures.
“In class 1, the bahvior is very simple, and almost all initial conditions lead to exactly the same uniform final state.
“In class 2, there are many different possible final states, but all of them consist just of a certain set of simple structures that either remain the same forever or repeat every few steps.
“In class 3, the behavior is more complicated, and seems in many respects random, although triangles and other small-scale structures are essentially always at some level seen.
“And finally…class 4 involves a mixture of order and randomness: localized structures it produces which on their own are fairly simple, but these structures move around and interact with each other in very complicated ways.” [p. 235]
Can we know by looking at a rule which class of behavior it will produce? Generally not, but in certain cases we can prove rules won’t ever show anything different than a particular class of behavior [p. 241]. Additionally, rules that are close together tend to have similar behavior.
Continuous CAs show class behavior; and if you take one dimensional slice of the evolution of a two-dimensional CA, you’ll also get class behavior (in fact, a 1D slice of the Game of Life is a class 4 CA).
Fun question: What would you look at when trying to determine whether a three-dimensional CA has class behavior?
Sensitivity to Initial Conditions [p. 250]
In this section, we see that the difference patterns for each CA (the patterns produced when one flips a bit or block of bits of the initial conditions) are different for each class.
Class 1’s difference pattern always dies out; Class 2’s has very limited range; Class 3’s has a wide range and perpetuates; Class 4’s has a limited range and may or may not perpetuate. We see that the difference patterns give us indications of how information is handled in each system.
Class 1, in effect, “forgets everything”; Class 2 retains information in a highly localized manner; Class 3, in effect, “transmits nearly everything”; and in Class 4 long-range transmission is possible, but does not always happen. Again, Class 4 behavior seems like and intermediate between Class 2 and three, where there are localized structures that can transmit information in a long-range manner.
Systems of Limited Size and Class 2 Behavior [p. 255]
This section explains Class 2 repetitive behavior by noting that it is a general result that systems of limited size with discrete elements all eventually repeat.
“…the actual repetition period jumps around considerably as the size of the system is chaned. And as it turns out, the repetition period is again related to the factors of the number of possible positions for the dot — and tends to be maximal in those cases where this number is prime.” [p. 258]
Note: the max possible repetition period for any system is always equal to the total states of the given system.
“In a class 2 system with random initial conditions…since different parts of the system do not communicate with each other, they all behave like separate patterns of limited size.” [p. 260]
Randomness in Class 3 Systems [p. 261]
There are, however, certain special initial conditions that will make even randomness-generating CAs repetitive. For rule 30, only initial conditions consisting of a single block of black and white cells repeated forever can yield repetitive behavior. However, this is not true for all randomness-generating rules.
Indeed, there are some initial conditions that can make one CA act just like another CA. There are also CAs that can self-emulate: additive rules, and other rules that show nested behavior. Examples: rules 90, 150, and 184.
The Notion of Attractors [p. 275]
An attractor for a CA are points to which the evolution will be drawn, regardless of initial conditions (like a pendulum, which will always end up pointing straight down, regardless of how it starts out).
In general, a CA could have many possible attractor states. In particular, it could have State 1 to which 4 sets of initial conditions lead, State 2 to which 90 sets of initial conditions lead, State 3 to which 13 sets of initial conditions lead, and so forth.
On the next few pages, Wolfram details a network convention that compactly describes the evolution of various CAs and their various initial conditions to particular attractor states. He uses the connectors to specify the colors. The networks are simple in class one and two systems — all initial conditions evolve to a contant, repetitive state. In class 3 and 4 systems, the networks can get very complicated, very quickly (in fact, the number of nodes seems to increase at a rate that is at least exponential).
It stands to reason that in many class 3 and class 4 systems, there really aren’t any attractor states — and that’s why the network complexity “blows up.” We note special initial conditions are needed to evolve most class 3 and class 4 systems to attractor states.
Structures in Class 4 Systems [p. 281]
Wolfram endeavors to show that moving structures are inevitable in class 4 systems, and he discusses the different kinds of moving structures that one sees in class 4 systems given particular initial conditions.
“Indeed, it is a general feature of class 4 cellular automata that with appropriate initial conditions they can mimic the behavior of all sorts of other systems.” [p. 291]
Rule 110 is the old standard that shows the above to be true.
