"To play life you must have a fairly large checkerboard and a plentiful supply of flat counters of two colors.”
Martin Gardner, Scientific American (October 1970)
A cellular automaton (CA) is a model of a system of cell objects with the following characteristics.
Perhaps the most significant scientific (and lengthy) work studying cellular automata arrived in 2002 Stephen Wolfram’s A New Kind of Science, available online in its entirety for free.
What is the simplest cellular automaton we can imagine? Let’s build Wolfram’s elementary CA from scratch. What are the three key elements of a CA?
The most important detail of how cellular automata is work—time. We’re not really talking about real-world time here, but about the CA living over a period of time, which could also be called a generation and, in our case, will likely refer to the frame count of an animation. The figures above show us the CA at time equals 0 or generation 0. The questions we have to ask ourselves are: How do we compute the states for all cells at generation 1? And generation 2? And so on and so forth.
A cell’s new state is a function of all the states in the cell’s neighborhood at the previous moment in time (or during the previous generation). We calculate a new state value by looking at all the previous neighbor states.
In Wolfram’s elementary CA, we look at all the possible configurations of a cell and its neighbor and define the state outcome for every possible configuration. We have three cells, each with a state of 0 or 1. How many possible ways can we configure the states? Up to 8. We therefore define a “ruleset” as a list of 8 bits.
Eight 0s and 1s means an 8-bit number. How many combinations of eight 0s and 1s are there? 256. In terms of a Wolfram elementary CA, we have now discovered that there are 256 possible rulesets. The above ruleset is commonly referred to as “Rule 90” because if you convert the binary sequence—01011010—to a decimal number, you’ll get the integer 90. The low-resolution shape we’re seeing above is the “Sierpiński triangle.” It’s a fractal pattern.
In [11]:
%%HTML
<iframe src="https://www.openprocessing.org/sketch/431488/embed/" width="750" height="358"></iframe>
The vast majority of elementary CA rulesets produce uninspiring results, while some result in wondrously complex patterns like those found in nature. Wolfram has divided up the range of outcomes into four classes:
Class 1 CAs end up, after some number of generations, with every cell constant. This is not terribly exciting to watch. Rule 222 is a class 1; if you run it for enough generations, every cell will eventually become and remain black.
Like class 1, class 2 remain stable, but the cell states are not constant. Rather, they oscillate in some regular pattern back and forth from 0 to 1 to 0 to 1 and so on. In rule 190, each cell follows the sequence 11101110111011101110.
Class 3 appears random and have no easily discernible pattern. In fact, rule 30 is used as a random number generator in Wolfram’s Mathematica software. Again, this is a moment where we can feel amazed that such a simple system with simple rules can descend into a chaotic and random pattern.
Class 4 can be thought of as a mix between class 2 and class 3. One can find repetitive, oscillating patterns inside the CA, but where and when these patterns appear is unpredictable and seemingly random. Class 4 exhibits the properties of complex systems that we described earlier in this chapter and in Chapter 6. If a class 3 wowed you, then a class 4 like Rule 110 above should really blow your mind
Try discovering the patterns of different rulesets and the computer code that generates them at https://www.openprocessing.org/sketch/431488/
Can you classify them?