[This workshop is partly adapted from Shiffman et al (2012)]
A cellular automaton is a collection of "colored" cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells. The rules are then applied iteratively for as many time steps as desired. John von Neumann was one of the first people to consider such a model, and incorporated a cellular model into his "universal constructor" (which we will recall in Workshop 2.1. Cellular automata were studied in the early 1950s as a possible model for biological systems (Wolfram 2002, p. 48). Comprehensive studies of cellular automata have been performed by S. Wolfram starting in the 1980s, and Wolfram's fundamental research in the field culminated in the publication of his book A New Kind of Science (Wolfram 2002) in which Wolfram presents a gigantic collection of results concerning automata, among which are a number of groundbreaking new discoveries.
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 [13]:
%%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
Some biological processes occur—or can be simulated—by cellular automata.
Patterns of some seashells, like the ones in Conus and Cymbiola genus, are generated by natural cellular automata. The pigment cells reside in a narrow band along the shell's lip. Each cell secretes pigments according to the activating and inhibiting activity of its neighbor pigment cells, obeying a natural version of a mathematical rule.[ The cell band leaves the colored pattern on the shell as it grows slowly. For example, the widespread species Conus textile bears a pattern resembling Wolfram's rule 30 cellular automaton.
Plants regulate their intake and loss of gases via a cellular automaton mechanism. Each stoma on the leaf acts as a cell.
Moving wave patterns on the skin of cephalopods can be simulated with a two-state, two-dimensional cellular automata, each state corresponding to either an expanded or retracted chromatophore.
Threshold automata have been invented to simulate neurons, and complex behaviors such as recognition and learning can be simulated.
Fibroblasts bear similarities to cellular automata, as each fibroblast only interacts with its neighbors.
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)