Beyond Conway: Cellular Automata from All Walks of Life

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?

A cyclic CA making some waves

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.
The same cyclic CA, this time spiraling out of control

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.

Langton’s ant wreaking havoc on a world of vertical stripes

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.

Wireworld is a CA that models digital circuits. These are five clocks producing pulses at different rates.

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?]

22 thoughts on “Beyond Conway: Cellular Automata from All Walks of Life

  1. “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.”

    Time is a dimension.

    “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.”

    One can wonder if biology uses CA?

    Also Infinifactory is a fun way of building things.

    1. Not just biology, the entire universe is a cellular automata, with the grid and rules being most easily visualised as a continuous web of interconnected Feynman diagrams. The big unknown is if any of the rules are subject to true randomness or if it simply appears that way due to complexity. Most toy CA do not have a rule with random output, but there is nothing stopping you from constructing one.

    2. We know pretty well the cellular automata that generate zebra/tiger stripes, giraffe spots, patterns on the shells, etc. — each skin cell only knows about its immediate neighbors and has to decide what color to be…

    1. To clarify what I meant: Conway carefully fine tuned the standard rule set to balance it. Changing the rules for reproduction and overpopulation usually leads to quickly deserted grids or crowded messes.
      “every idea you have has already been implemented” is giving credit to the versatility that stems from Conway’s algorithm, as illustrated by your videos- we may actually be on the same page here ;)

      1. I still disagree. It will somewhat commonly in terms of sheet numbers tend to do less interesting things but they will do quite interesting things when cleverly setup to do so. Most of the outputs of, say, a NES or Xbox game ROM would do almost nothing interesting at all. However, some of them when cleverly coded, will output thousands of vastly different but still quite playable games.

  2. CAs are fun. I like how they balance Dionysian and Apollonian ideals. For example, the strict rules set forth are quite in the spirit of Apollonian arts. They are simple clean and beautiful. But as patterns progress, they startle you with their complexity and biological-esque diversity. Much like the Dionysian ideals. Much like real biological systems.

  3. CA may seem like an abstract exercise in math but it’s possible to make CA based on quantum dots. If we could mass produce quantum dot cellular automata then consumer electronics would change fundamentally because of their extremely low power consumption.

  4. I love CAs. When I 1st read about Langton’s loops, Something that would’ve been hard to achieve when I 1st read about them, but the internet made quite easy by the time I actually got round to it.

    As for 1DCAs, I’ve Tunisian crocheted them, which works rather well, except that it’s not very quick.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s