Wolfram’s Four Classes of One-Dimensional Cellular Automata
Stephen Wolfram has intensively studied the behavior of cellular automata, including one dimensional ca. He found that they can be classified into four different behavior types. Wolfram: Four Classes of One-Dimensional Cellular Automata Stephen Wolfram studied the behavior of cellular automata in the simplest form possible, looking at one-dimensional, two-state cellular automata, either on or off, 1 or 0. This means that each cell is connected only to its two nearest neighbors. From this, he studied all the possible combinations of states, listed in binary. One example of this is the string 01101110, which is equal to the number 110 in decimal. He called this behavior Rule 110. Rule 30 is another example, from the string 00011110. Wolfram also used the computer program Mathematica to help with studying the behavior of these cellular automata. These all displayed complexity emerging from simple rules. He observed that the behavior of these fit into four different classes: 1) almost all initial configurations transform to the same final pattern. Rule 8 is an example of class 1. All cells in the lattice quickly switch to off or 0 and stay off. 2) almost all initial configurations become either a uniform final pattern or switch between several final patterns. The specific final pattern depends on the configuration at the beginning. 3) Most initial configurations produce random-looking behavior, but triangles and other regular structures are present. Rule 30 is an example of class 3. 4) This class involves a mixture of order and of randomness. Wolfram says that localized structures are produced which on their own are fairly simple, but these structures move around and interact with each other in very complicated ways. Rule 110 is an example of class 4. Matthew Cook later proved that rule 110 is universal, and it is one of the simplest known examples of a universal computer. Class three represents chaotic patterns, in the sense of chaotic systems; they may form patterns, but cannot be predicted and do not repeat in any regular way. Class four is extremely important because it represents “complex” patterns in the sense of the emergent patterns within complex systems. Mitchell, Melanie. 2009. Complexity. Oxford University Press.