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
• See how it 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 see 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 small and stable structures that flip between 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 starting conditions of the simulation.

You can explore a live version of the clock here. Remember there are only three things at play: the starting conditions, 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 basically no predictive shortcuts.

Then chaos theory also 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 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 three-dimensional grids or graphs, 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 automaton that can 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, it self-reassembles, or grows into new ones.

This close replication of morphogenesis is still encoded in particularly simple starting conditions and 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 bare bones 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 plausible theories to back them up.

If our reality is not simulation based, then it raises another beguiling question – why is our reality so replicable through this form of emergence?

Note this potentially extends to physics. To give a cursory idea, quantum mechanics purports that space itself is quantized at the Planck scales. So rather than moving through a fluid medium, particles jump from one discrete spatial pixel to the next.

Whatever the takeaways, 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.