Emergence in the Game of Life: a lesson for machine learning?

Or why you don't always need large models to do complex things

I realise a lot of my subscribers are interested in machine learning, but when I started this Substack, the plan was to talk about computer science more generally. So, here’s an attempt to do this, yet still keep it relevant to the ML lovers amongst you.

The game of… what?

The Game of Life is a thing in computer science that’s been around for over half a century. I could tell you that it’s a cellular automata. I could tell you that it’s a simple simulation of life. But neither of these facts would tell you much.

Instead, I like to think of it as an accessible model of emergence. Emergence is common in natural systems, and pretty much standard practice when it comes to biological systems. It happens when the overall behaviour of a system bears little resemblance to the behaviour of its underlying components. So much so, in fact, that you have no hope of predicting what the system will do just by peering at its bits-and-pieces. Emergence is not very common in human-designed systems. We prefer to design things from the top down, so that their behaviour flows upwards from their bits-and-pieces in a predictable way. But biology doesn’t do things this way — it only really cares about high-level behaviour, and how this is implemented at a low-level is entirely up to the open-ended wanderings of evolution.

And it turns out that emergent systems can be very efficient, in that pretty complex things can be achieved from pretty simple bits-and-pieces. Consequently, it’s no great surprise that evolution — which is essentially a lazy process that only cares about getting things done rather than how they’re done — prefers emergent systems to top-down systems. And so we see emergent systems throughout nature, from the workings of our brains and bodies up to the functioning of entire ecosystems.

In the case of the Game of Life, the bits-and-pieces are particularly simple. They’re arranged in a grid of cells, and each of them can be on (white) or off (black). At each time step, each decides whether to remain on or off based on what their neighbours are up to. Specifically, if they’re currently on, they will stay on if 2 or 3 neighbours are on; otherwise they’ll turn off. If they’re off, they will only turn on if exactly 3 of their neighbours are on.

As it happens, this is a loose model of organisms living within a two-dimensional space, in which the on state represents an organism being alive and the off state represents it being dead. Transitions between these states represent things like over-crowing and reproduction. But I don’t think this matters. It doesn’t help to understand the high-level behaviour of the Game of Life at least, which bears little resemblance to any conventional simulation of population growth and decline.

So what does its overall behaviour look like? Well, the most interesting thing from a computational perspective is probably the presence of moving patterns called gliders. The best known example of this phenomenon comprises five on cells that walk diagonally across the grid. That is, it’s a particular oscillating pattern of five cells will translates itself one position down and one position to the right at each time step.

Which is a little odd, since the underlying “rules” of the system, i.e. cells turning on and off depending how many of their neighbours are on and off, gives no indication that it will lead to movement. And this is precisely why it is considered to be an emergent system — its high-level behaviour is not predictable from its low-level parts.

Computing with the Game of Life

Things get interesting when these gliders collide, both with each other and with other patterns within their environment. So much so, in fact, that this turns out to be the basis of showing the Game of Life is Turing complete.

Those of you who have been following my posts for a while may remember the one about Turing machines and the limits of computation, in which I describe how a Turing machine is a simple computer that can do anything that any other computer can do, if rather slowly and impractically. A popular way of showing that something has the same computational abilities of any other computer is to show that it can implement a Turing machine. This is known as being Turing complete, or computationally universal. And, indeed, someone has shown that the Game of Life can implement a Turing machine. Specifically, it is implemented as a large¹ and complex pattern in the initial on/off states of the cells in the Game of Life grid.

Below is a video of one in action. The diagonal structure is the Turing machine’s tape, the bit at the bottom-left is the read-write head and control logic, and the moving things are streams of gliders.

Doesn’t do much, right? Maybe if you left it a few years, the read-right head might move down the tape a little, but basically implementing a Turing machine is seriously overkill. A much simpler way of demonstrating that something is computationally universal is to show that it can implement logic gates. Pretty much all the computers we see around us are built from logic gates, so we know that if we can implement logic gates, we can implement a computer.

In the case of the Game of Life, this has been demonstrated by implementing AND, OR and NOT gates². An important element of these implementations, which I’ve not mentioned yet, is glider guns. These are patterns that repeatedly oscillate in a small part of the grid, and after each cycle they generate a single glider. Positioning these carefully allows you to create streams of gliders that interfere in specific ways. Another important ingredient is the way in which the input(s) and output of the gate are represented — this is again done using gliders; specifically, the presence of absence of a stream of gliders. I won’t show you the actual patterns used to implement these logic gates, since there’s already an excellent summary — and a nice demo of a circuit in motion — on Nicholas Carlini’s website. But, by carefully positioning these patterns on the Game of Life grid, you can build up circuits of arbitrary complexity.

But would you really want to do this in practice? A computer requires a lot of logic gates, so you’d need a huge pattern to do anything useful. And implementing a huge pattern within the Game of Life in order to implement a computer makes no sense, since you’re probably already running the Game of Life on a perfectly good computer. Instead, the important thing is that you can implement a computer in the Game of Life. Which is rather surprising. After all, who would have thought that a bunch of really simple rules running in a grid could do anything useful, let alone compute?

Don’t forget about emergence

Implementing logic gates also makes little sense from an emergence perspective. The whole point of systems like the Game of Life is that they display emergence — and we know from biology that emergent systems can express complex behaviour much more compactly than the kind of top down systems we design. So, implementing a conventional model of a computer in an emergent system is not a sensible thing to do.

Instead, we might look at ways in which complex behaviour can emerge from simple patterns within the Game of Life. A well-known example of this is something called a Methuselah, which is basically a large complex pattern that emerges, over a series of iterations, from a simple pattern. The best known of these is Acorn, whose name reflects the idea that something big emerges from something small — the small thing in this case being an initial pattern of seven on cells. The name is even more appropriate if you stack the patterns from subsequent iterations on top of each other, since the resulting structure looks not entirely unlike a tree. Take a look at the following visualisation from YouTube to get a sense of this:

So, you might consider this simple initial pattern, combined with the simple underlying rules of the Game of Life, to be a very compressed representation of this structure, and a nice example of how something complex can emerge from something simple.

But more generally, the point I’m trying to make is that you don’t always need big complicated things to produce complex behaviour. And this philosophy is very much in opposition to the status quo of machine learning, in which bigger is most often seen as better — that is, larger and larger neural networks to solve more and more complex tasks. Imagine instead that we could get more complex behaviour by designing simpler systems that take advantage of emergence. Doing so could lead to considerable savings in computational resources at both training and inference time, and perhaps do something to address the environmental costs of deep learning.

However, the devil is in the details, and how you go about designing emergent systems is still an open question. There’s been plenty of work on this over the years in the more peripheral parts of machine learning and artificial intelligence — notably the bio-inspired computing and artificial life communities — but the idea has yet to gain much uptake within the mainstream. In part I think this is because humans struggle with the concept of emergence. After all, we’re used to designing things in a top down manner, and it seems natural to take this approach when we design machine learning systems. So, future progress in machine learning may well require us to challenge our assumptions about how we design complex systems.

If you want to play around with the Game of Life, I’d recommend grabbing a copy of Golly. There’s also a bunch of online simulators, including this one.

1. Oddly, I couldn’t find a figure for this, but it’s in the order of thousands of on cells.

2. Although you can actually demonstrate universality just by implementing NAND gates.