Computability Part 5: Elementary Cellular Automata
In the previous post we talked about Conway's Game of Life as a well-known cellular automaton. In this post we will cover even simpler automata - the elementary cellular automata. Stephen Wolfram covers them extensively in his book, A New Kind of Science.
To recap, we defined a cellular automaton as a discrete n-dimensional lattice of cells, a set of states (for each cell), a notion of neighborhood for each cell, and a transition function mapping the neighborhood of each cell to a new cell state.
An elementary cellular automaton is 1-dimensional - an array of cells. A cell can be either on or off (just like in Conway's Game of Life). The neighborhood of a cell, meaning the cells that we take into account when we determine the next state of the next generation, consists of the cell itself and its left and right neighbors.
For example, we can define an elementary cellular automaton with the following rules:
[ on, on, on] -> off
[ on, on, off] -> off
[ on, off, on] -> off
[ on, off, off] -> on
[off, on, on] -> off
[off, on, off] -> on
[off, off, on] -> on
[off, off, off] -> off
If we start with a single on cell and produce 10 generations, we get
(using # to mean on):
#
###
# #
### ###
# #
### ###
# # # #
### ### ### ###
# #
### ###
Rule encoding
The elementary cellular automata can easily be enumerated exhaustively:
the neighborhood of a cell can be in only one of 8 states, as we saw
above: [on, on, on], [on, on, off], ... [off, off, off]. The
transition function maps each of these possible states to either on or
off. If we think of the on/off as a bit, we need 8 bits to
represent the transition function.
[ on, on, on] -> off
[ on, on, off] -> off
[ on, off, on] -> off
[ on, off, off] -> on
[off, on, on] -> off
[off, on, off] -> on
[off, off, on] -> on
[off, off, off] -> off
can be represented as the binary number 00010110, which, in decimal,
is 22 (where [off, off, off] is the least significant bit). We can
represent numbers from 0 to 255 in 8 bits, so there are exactly 256
elementary cellular automata. This encoding is referred to as Rule as
in transition rule
. The elementary cellular automata in our above
example is called Rule 22 .
Elementary cellular automata behavior
A common way to plot the evolution of an elementary cellular automata
over multiple generation is to render each generation below the previous
one, like our above example using # for on. A more condensed version
with 1 pixel per cell of running rule 22 for 301 generations looks like
this:
At this level, we can clearly see patterns emerging in the automaton. We get an even more interesting view if, instead of starting with just a single on cell, we start with a random state - an array of random on and off cells. Here is rule 22 starting with 301 random cells and running for 301 generations:
We can also easily see some of the automatons are complements of other automatons: if we simply flip each bit, we end up with a complementary version. Rule 22's complement is Rule 151:
We can also reflect a rule by swapping the transitions for
[on, off, off] with [off, off, on] and [on, on, off] with
[off, on, on]. This doesn't work for rule 22, since its reflection is
still 22, but, for example, rules 3 and 17 are reflections of each
other.
Rule 3:
[ on, on, on] -> off
[ on, on, off] -> off
[ on, off, on] -> off
[ on, off, off] -> off
[off, on, on] -> off
[off, on, off] -> off
[off, off, on] -> on
[off, off, off] -> on
Renders as:
Rule 17:
[ on, on, on] -> off
[ on, on, off] -> off
[ on, off, on] -> off
[ on, off, off] -> on
[off, on, on] -> off
[off, on, off] -> off
[off, off, on] -> off
[off, off, off] -> on
Renders as:
That means that, even though there are 256 possible automata, from behavioral perspective, some are complements or reflections of others thus exhibit the same behavior. In fact, there are only 88 uniquely behaving automata, all others being complements and/or reflections of these.
Implementation
Let's look at a Python implementation. We will represent the state of
an automaton as a list of Boolean cells. We can encode the state of a
neighborhood as a 3 bit number:
left neighbor * 4 + cell * 2 + right neighbor. Given a list of cells
and the index of a cell, we have:
def neighbors(cells, i):
return (cells[i - 1] if i > 0 else False) * 4 + \
cells[i] * 2 + \
(cells[i + 1] if i < len(cells) - 1 else False)
If we run off the ends of the list, we assume the state of that cell is
off. In Python, False becomes 0 and True becomes 1 if we do
arithmetic with them, so this function will return a number between 0
and 7.
We can derive the transitions from the rule number by taking a rule number and expanding it into a dictionary that maps each value from 0 to 7 to the corresponding bit in the rule number value:
def transition(rule):
return {i: rule & (1 << i) != 0 for i in range(8)}
This might be a bit hard to understand, so let's work through an
example. Let's take Rule 22. The binary representation of Rule 22 is
00010110. We're iterating over the range 0...7 (i) and for each of
these values, we shift 1 exactly i bits left. Then we check if the
rule logic AND this shifted bit is different than 0.
For i == 0: 00010110 & (1 << 0), which is 00010110 & 00000001, we
get False, so transitions[0] = False.
For i == 1: 00010110 & (1 << 1), which is 00010110 & 00000010, we
get True, so transitions[1] = True.
...
For i == 7: 00010110 & (1 << 7), which is 00010110 & 10000000, we
get False, so transitions[7] = False.
Remember the keys of the dictionary are neighborhood states.
Now we just need a function that takes a rule, an initial state, and the number of steps we want to run. The function will start with the initial state, then at each step, update the list of cells using the transition function:
def run(rule, initial_state, steps):
t, cells = transition(rule), initial_state
for _ in range(steps):
yield cells
cells = [t[neighbors(cells, i)] for i in range(len(cells))]
We talked about two ways to look at cellular automata: starting with a single on cell, or starting with a random initial state.
Let's implement an initial_state function which takes a cell count as
input and returns a list of cells, all of which are off except the
middle one:
def initial_state(cell_count):
result = [False] * cell_count
result[cell_count // 2] = True
return result
We'll also want a random_initial_state which takes a cell count and
returns a random cell list. We'll take advantage of the fact that
Python supports arbitrarily large integers natively, so we'll just
generate a random number with cell_count bits, then derive the cell
list from that (if a bit is 1, the corresponding cell is on):
import random
def random_initial_state(cell_count):
seed = random.randint(0, 2 ** cell_count - 1)
return [seed & (1 << i) != 0 for i in range(cell_count)]
Here is all the code in one listing:
def neighbors(cells, i):
return (cells[i - 1] if i > 0 else False) * 4 + \
cells[i] * 2 + \
(cells[i + 1] if i < len(cells) - 1 else False)
def transition(rule):
return {i: rule & (1 << i) != 0 for i in range(8)}
def run(rule, initial_state, steps):
t, cells = transition(rule), initial_state
for _ in range(steps):
yield cells
cells = [t[neighbors(cells, i)] for i in range(len(cells))]
def initial_state(cell_count):
result = [False] * cell_count
result[cell_count // 2] = True
return result
import random
def random_initial_state(cell_count):
seed = random.randint(0, 2 ** cell_count - 1)
return [seed & (1 << i) != 0 for i in range(cell_count)]
Here is how we can use this to print the first 30 steps of Rule 22:
for state in run(22, initial_state(61), 30):
print(''.join(['#' if e else ' ' for e in state]))
Wolfram classification
Wolfram analyzed the behavior of cellular automata and classified them in 4 classes (called Wolfram classes). These go beyond elementary cellular automata to cover other cellular automata like, for example, ones where the next generation of a cell is not determined only by the cell and the two cells next to it, rather the neighborhood includes next-next cells. In this post we'll stick to elementary cellular automata though.
Class 1
Class 1 automata converge quickly to a uniform state. For example rule 0 becomes all off in one generation:
It's complement, rule 255, becomes all on in one generation:
Class 2
Class 2 automata converge quickly to a repetitive state. For example rule 4:
Class 3
Class 3 automata appear to remain in a random state, without converging. Rule 22, which we started with above, exhibits this type of behavior:
Class 4
The most interesting class of cellular automata, class 4, has a quite remarkable behavior: areas of cells end up in static or repetitive state, while some cells end up forming structures that interact with each other. Rule 110 is the only elementary cellular automaton that exhibits this behavior:
Turing completeness
The fact that Rule 110 has areas of cells that are static or repetitive
while some other cells form structures should remind you of the
Conway's Game of Life spaceships we discussed in the previous post. In
the previous post, we saw that the Game of Life is Turing complete, and
how a Turing machine was implemented
using spaceships as signals
processed
by other patterns.
Turns out Rule 110 is also Turing complete. Stephen Wolfram conjectured this in 1985, and the conjecture was proved in 2004 by Matthew Cook1. Cook uses Rule 110 gliders (interacting structures) to emulate a cyclic tag system. We saw in Computability Part 3: Tag Systems that cyclic tag systems can emulate tag systems, and an m-tag system with \(m \gt 1\) is Turing complete.
Rule 110, an elementary cellular automaton, is also capable of universal computation. And while this all might seem very abstract, cellular automata are so simple they show up in nature:
