There’s a time in every geek’s development when they learn of Conway’s Game of Life. This is usually followed by an afternoon spent on discovering that the standard rule set has been chosen because most of the others just don’t do interesting things, and that every idea you have has already been implemented. Often enough this episode is then remembered as ‘having learned about cellular automata’ (CA). While important, the Game of Life is not the only CA out there and it’s not even the first. The story starts decades before Life’s publication in 1970 in a place where a lot of science happened at that time: the year is 1943, the place is Los Alamos in New Mexico and the name is John von Neumann.

Recap: What is a CA?

The ‘cellular’ part in the name comes from the fact that CAs represent a grid of cells that can be in a number of defined states. The grid can have any number of dimensions, but with three dimensions the visual representation starts to get into the way, and above that most human brains stop working, so two-dimensional grids are the most common — with the occasional one-dimensional surprise. The cells’ states are in most cases discrete but a subset of continuous CAs exists. During the operation of a CA the future state of every cell in the grid is determined from each cells state according to a set of rules which in most cases take into account the states of neighboring cells.

History of the CA

The first CA was implemented in the late 1950s by John von Neumann and Stanislav Ulam, and was invented for science rather than for fun. It modelled a volume of liquid as a network of discrete units that influenced each other. This was followed up by James M. Greenberg and Stuart Hastings who developed a model to simulate wave propagation in excitable media with three states and a very simple set of rules:

1. A resting cell will change to the exited state when at least one neighbour is in the exited state
2. An exited cell will enter the refractory state
3. A cell in the refractory state will enter the resting state.

A variant of this algorithm with a continuous refractory state can be used to solve mazes on a GPU. The cyclic model extends this idea, allowing any number of states and raises each cell’s state if a neighbor is in the next higher state. The ‘cyclic’ part here means that highest state is considered to be succeeded by the lowest state. For certain setups the behaviour of this class of CA resembles that of oscillating chemical reactions like the  Belousov–Zhabotinsky reaction.

Simulating more or less complex phenomena governed by simple, local rules is the guiding principle of the CA. Even with more accurate numerical analysis methods available, CAs continue to shine through their simplicity and accessibility.

Life After Life

The ability to produce complex behaviour from simple rules may well be what made Conway’s CA so popular. And to give credit where it’s due, this popularity may have pulled CAs from the fringes of computer science onto the center stage. In the wake of Life several new CAs emerged and the hype culminated in [Stephen Wolfram] announcing the discovery of a ‘new kind of science’ in a book with exactly that title.

One of these modern CAs is Langton’s Ant, which is a special case because it only looks at a single cell in the grid, ignoring its neighbors. This cell is considered the position of an ant that may be looking in one of four cardinal directions. in the following steps the movement of the ant is governed by just two rules:

1. If the floor beneath the ant is white, the insect will color it black, turn 90° right and move forward to the next cell
2. If the floor is black, it will become white before the ant turns left and proceeds to the next tile.

One might note that this isn’t an accurate model of the behaviour of ants. The same is true for Conway’s simulation and the way cells reproduce. The good news is that they were never supposed to be. The new breed of CA was tailored to more theoretical applications than simulating fluids. By choosing the initial states of the floor tiles in the ant’s world one is able to program its movements. The ant will then transform this input into something else, acting like a computer. Langton’s Ant has been proven to be Turing complete in 2000, fourteen years after its invention. With an arbitrary supply of cells, Langton’s Ant can be a general-purpose computer.

What is This? A CA for Ants?

But Langton’s Ant isn’t the smallest useful CA. So-called “Elementary CAs” are the most basic design there is, being one-dimensional with cells that can have only two states. Of these, the most notable is probably the Rule 110 elementary cellular automaton.

The simplicity of Elementary CAs limits the number of possible rule sets to 256 possible different implementations. Most of these rules are equivalent to each other, either being mirror images or having ones and zeroes swapped. Weeding out the duplicates we are left with 88 distinct elementary CAs. That number 110 exists among these 88 distinct types is an artifact of the numbering system [Stephen Wolfram] proposed for elementary CA. He was really into these tiny machines, using Rule 20 as pseudorandom number generator in the Wolfram language is one testimony to that.

The coolest aspect of elementary CAs is that they exhibit all kinds of behaviour their bigger cousins are known for, ranging from reducing random initial conditions to static output in a few generations to continuously producing chaotic patterns.

Applications and Implications

The CA that ran fluid simulations was the first CA that von Neumann and Ulam implemented but wasn’t the first von Neumann designed. His first CA was a thought experiment called ‘universal constructor’, a device that could create any other machine, including itself, given the instructions. It had been designed without access to a computer before von Neumann joined the Manhattan Project in 1943.

The design was first published in 1966 after his death. From then it took until 1995 until a variation of the universal constructor was implemented for the first time. It is estimated that in that on contemporary hardware letting the machine replicate itself would have taken around two years. Today the program Golly run on a desktop computer with sufficient RAM can perform the replication in mere minutes.

Other self-replicating CAs exist, such as Langton’s Loops and Life has been made to replicate itself. CAs have been proposed as one-way function in public key cryptography, based on the fact that even when the rules are known, calculating the previous state of a CA is verging on the impossible while calculating the following state is trivial. As mentioned, CA can be used to produce pseudorandom numbers, and certain types of artificial neural networks can be considered CAs.

Today CAs exist on the fringes of computing again. The revolution that Wolfram and others heralded didn’t come to pass. Although there have been hardware implementations, other computer architectures dominate the scene. But with modern GPUs featuring great numbers of rather small cores operating in parallel and thus being a perfect platform for CA, Life might find a way.

[Editor’s Note: The featured image represents automata cells assembling themselves into robots. We know it’s a stretch, but Joe made this cool art for us and we’re running it. Better than another black-and-white glider, right?]