The Wonderfully Fascinating World of Cellular Automata

If you find fractals like the Mandelbrot set fascinating, yet don’t know about cellular automata, then fasten your seat belt. Here we will introduce this undeservedly esoteric domain of mathematics, explore examples in action, uncover why this type of bare bones simulation generates astonishing forms of complexity, and holds the keys to unlocking deep scientific phenomena. The wonderful world of cellular automata may even yield proof that we are living in a simulation.

The Simplest Most-Complex-Clock Ever?

Before we dive in, let’s pique your curiosity with this video. As you will see, it gradually forms from a bunch of moving pixels, into a functioning digital clock.

So what?

First of all, note that the clock represents a true form of emergence. Emergence is found in nature, where simple systems mysteriously give rise to highly complex behaviors.

For example, ants, bees and termites are basic creatures with very limited simple behaviors. However en masse, they form super organisms with behaviors arising that are highly complex, such bees precisely modulating the temperature of a hive, and ants gathering themselves into a raft to cross a river or to survive a flood.

The clock above similarly emerges out of a super-simple simulation (you can think of the pixels like ants), giving an interesting example of cellular automata. Now let’s get into what it actually is.

What Are Cellular Automata?

Cellular automata were originally devised by John von Neumann. Then in 1970, Cambridge mathematician John Conway refined the approach to create Conway’s Game of Life.  By the way, if you want to discover an Easter egg from the geeks at Google, try googling ‘Conway’s Game of Life’.

This version is also the easiest to understand, and comprises just four very simple rules about the way cells behave on a square grid. The rules basically instruct cells to be alive or dead (black or white), according to the states of neighboring cells. And that’s it.

You can try out the real thing in your browser here. Just stop the simulation, click on any number of cells to make them alive, then click start.

If you give it a try, you’ll likely notice one of three things.

1. The cells die out or become stagnant, and the simulation effectively ends.

2. The cells form into interesting small and stable structures that flip between two states.

3. The cells seem to come alive and start doing unusual things such as forming small spaceship-like structures that glide off into the unknown (aptly termed ‘gliders’).

Novel, but not exactly inspiring.

However, depending on the cells you select, weird things can begin happen. Testament to this, the clock we introduced earlier, is actually generated from one specific configuration of Conway’s Game of Life. Hence it’s likely the simplest functioning digital clock ever created.

Except that technically, it wasn’t created. Rather it self-organized out of the basic starting conditions of the simulation.

You can explore a live version of the clock simulation here. Remember there are only three things at play: the starting cells, the basic rules, and iterative repetition.

What’s Happening?

Cellular automata have fascinated brilliant minds for decades because, unlike nature, they are a clearly defined and deterministically bounded system. Which according to intuition, shouldn’t be capable of doing anything complex. Yet they do.

Therefore, they represent a very pure form of emergence that’s amenable to study. However, this is where things get deep, because they also display something referred to as irreducible computability.

This means, that although the simulation is super-simple and completely determined, there is fundamentally no way to predict what will happen, other than running a specific simulation to find out. There are essentially no predictive shortcuts.

This is also where chaos theory comes in (think butterfly’s wings), because a minuscule change in the starting conditions can dramatically change the outcomes. For example, having just one cell in a different position for the clock above, could prevent it from emerging at all.

And There’s More…Much More

There appears to be no upper boundary on the complexity that can be generated using only this approach. With sufficient computing power, the grid can be far larger with more starting cells, and the simulation run for much longer.

Stephen Wolfram provided mathematical proof that cellular automata are Turing complete, in that eventually all possible states can be realized using certain rules.

Now this is where things get really interesting from both a scientific and computational perspective, because even something as basic as Conway’s Game of Life, can also generate functional computations.

Certain types of cell structures are more likely to emerge, such as gliders. These can move into other structures, and either interact then fly out of the structure intact, or effectively get swallowed up and disappear.

This behavior mimics a logic gate, that is, an interaction which produces a 1 or 0, which is a critical aspect of the way our computers process information. Similarly, NAND gates can also be generated, which both computers and neurons use to trigger a signal only when a certain threshold is achieved.

Such characteristics allow cellular automata to be capable of becoming Universal Turing machines, meaning they can potentially emulate any other machines or computers.

Extrapolating these concepts to the nth degree, with enough computing power and time, it’s theorized that cellular automata could generate highly complex simulations capable of producing intelligence, possibly providing a more organic route to artificial general intelligence.

Going Next Level

We mentioned earlier that Conway’s Game of Life is one of the most basic forms of cellular automata. There are many ways this simulation approach can be varied based on the rules applied, or for instance, using a three-dimensional grid, or even more dimensions (which mathematics perfectly allows).

They can also be combined with neural networks to guide the simulations towards desired outcomes. In recent years research in this area has been progressing, quickly with some astonishing results.

Exploration of these variations has revealed automata that display surprisingly organic behavior, including the equivalent of biological cells with functional membranes. Here are some examples.

One particular landmark paper titled ‘Growing Neural Cellular Automata’, applied such techniques to replicate a mystery of nature called morphogenesis. Morphogenesis is found in creatures like flatworms, whereby if they are cut in half, two new complete flatworms will grow.

In this research, they used neural network training to discover cellular automata patterns than can create a stable image, within a simulation that is interactive.

When the image is perturbed, such as cutting it in half, it self-reassembles, or grows into two new ones. This close replication of morphogenesis is still encoded in very simple starting conditions and simulation rules.

You can try the interactive simulation for yourself here, aptly using the image of a lizard.

What Does It All Mean?

There are a few deep takeaways.

Firstly, John von Neumann painstakingly created the first iterations of cellular automata using only pen and paper. This highlights a key point that the simulations are extremely rudimentary, yet out of barebones simplicity, arises deeply complex behaviors. This hidden dimension of complexity seems to be inherent – we are just discovering it.

Secondly, the chaotic systems and emergence seen in natural systems can be mimicked through cellular automata, which means it’s very likely they hold some secrets to the nature of life itself. If so, then because the simulations are essentially based on information processing, the richness we see rise out of nature may also be the same.

Last but not least, it’s likely we’ve barely scratched the surface of what cellular automata can become. Through the application of vast increases in computation, it’s viable that simulations exhibiting the richness and complexity of our world could emerge. It’s even possible they hold the virtual computational power to create copies or iterations of new such simulations within themselves.

If we hypothesize this to be achievable, then it begs the very serious question ‘are we living in the Matrix’. If you’re not familiar with simulation theory, many esteemed scientists across different disciplines believe our reality may well be simulated – with very plausible theories to back them up.

If not, then it raises another question – why is our reality so replicable through this form of emergence? Whatever the takeaway, cellular automata are wonderfully fascinating.

If you’d like to take a deep dive into this subject, then Machine Learning Street Talk produced a fabulous video interviewing subject matter experts at the cutting-edge.

‍