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:

- A resting cell will change to the exited state when at least one neighbour is in the exited state
- An exited cell will enter the refractory state
- 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:

- If the floor beneath the ant is white, the insect will color it black, turn 90° right and move forward to the next cell
- 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?]

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

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.

No time is half a dimension if that if you made a CA 4 dimensional in time you could describe an output run it backwards and see the machine create itself, that just doesn’t work.

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…

“[M]ost of the others just don’t do interesting things, and that every idea you have has already been implemented”

Oh really?

https://www.youtube.com/watch?v=C2vgICfQawE&t=1m10s

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 ;)

I believe the statement was correct. I think you may have misunderstood what was meant by it.

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.

Sheer numbers, rather.

The name of Ulam is Stanisław not Stanislav (there is not v in Polish alphabet)

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.

Complex patterns emerge? Apollo displeased!

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.

I would be remiss if I didn’t mention the work of Rudy Rucker and John Walker. Rudy, especially, has always been really interested in continuous CAs. You can try out a web version of the old AutoDesk Cellab online: http://fourmilab.ch/cellab/

Fantastic link! Everyone go check out Cellab.

Ed Fredkin of CMU and MIT pioneered the view he calls “Digital Philosophy”, that at the very smallest scale, below the level of subatomic particles, it’s all information, in CA form. Read more: https://en.wikipedia.org/wiki/Digital_philosophy

Whats a Conway?

Depends how good the prison food is.

Wolfram’s blog post earlier this year on 15 years since A New Kind of Science is pretty interesting…especially the later sections.

https://www.wired.com/2017/05/a-new-kind-of-science-a-15-year-view/

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.

I co-authored WWEJ3, a variant of WireWorld with replication capabilities.

https://github.com/gollygang/ruletablerepository/wiki/TheRules

Around 1996 I computed this picture with a Lattice Gas Automata (LGA), a special type of CA that obeys physical rules and shows Navier-Stokes behaviours at large scales :

http://ygdes.com/memoire/ecoule8b.gif (computed on a poor P100 PC)

Then for my master thesis with a P200MMX :

http://ygdes.com/memoire/flow-2g.gif