In a nutshell, a cellular automaton (CA) is a model of a system of cell objects with the following characteristics:
Here, we will simplify the neighborhood to just a single dimension, a straight line. The produced generation of the automata at the next time-step will be shown as a second line just below the first one, and son on, so finally we will obtain a 2D figure representing the time evolution of the automata.
There will appear different kind of figures, patterns that we will be able to recognize and classify according the rules of the automata. Some of them are very basic, but some other display an astonishing complex behaviour with such simple rules.
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? 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.
This sketch shows a Wolfram automata. Feel free to check the algorithm clicking on the </> icon inside the OpenProcessing link
In [1]:
%%HTML
<iframe src="https://www.openprocessing.org/sketch/433326/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
A way to measure the complexity of a system is to calculate the mutual information (MI) between a generation and its next generation. As more coincidences between the corresponding cells of both generation, as bigger the MI. In the example below:
In [4]:
%%HTML
<iframe src="https://www.openprocessing.org/sketch/433886/embed/" width="350" height="358"></iframe>
In [3]:
from ipywidgets import widgets
from IPython.display import display
import numpy as np
import re
from matplotlib import pyplot as plt
%matplotlib inline
def handle_submit(sender):
all = np.fromiter((item.group() for item in re.finditer(r'\d+', text.value)), dtype=np.int64).reshape((-1, 2))
plt.plot(all[:,0],all[:,1],'o-')
text = widgets.Text(description="Values")
text.on_submit(handle_submit)
display(widgets.Label("Enter list of (Lambda,C) values as a list of tuples. E.g. \"(0,10),(1,20),(3,25)\""))
display(text)