# Cellular Automata

The best-known automaton is probably Conway's *Game of Life*. It's a simple system which describes a game-board of cells: each cell can either be *alive* or *dead*. For each generation following the first, each cell is either alive or dead depending on the 8 cells around it:

- 0 or 1 living neighbours means the cell will die in the next generation, as if caused by underpopulation;
- 2 or 3 living neighbours means the cell will survive; and
- more than 3 living neighbours means the cell will die, as if caused by overpopulation.

These rules, although simple, give rise to some really interesting patterns - check out the [wiki page] for more examples than you could ever hope for. For instance, the Gosper Glider:

and the Pentadecathlon:

But this is all fairly well-explored territory - although in fairness, there's still some work being done on fully self-replicating patterns. I'm more interested in the way that cellular automata are actually *defined* - how we can predict their behaviours for every possible situation, and categorise them accordingly. Let's stick to one-dimension cellular automata for the moment - they're not quite as exciting, but they give us a good opportunity to work through the maths without getting overwhelmed.

Luckily, most of the groundwork for that is done already - Stephen Wolfram (namesake of Wolfram Alpha) devised a system of categorising "elementary" (one-dimensional) cellular automata by a single number in the range [0, 256):

- Each cell can be affected by the state of three other cells: the cell directly above it (i.e. the cell itself, in the previous generation), and the two cells on either side of that one.
- Each cell can be in one of two states: dead or alive.

Therefore, we can define a cell's surroundings - everything that determines its state in the next generation - with just 3 boolean values. That translates directly into 3 bits, and so we can represent every possible configuration of the surroundings with a 3-bit integer.

This is relatively easy to check; a 3-bit integer can represent 8 discrete values [0, 8) and there are 8 possible configurations of 3 dead/alive cells. If you don't see the link: there's two possible cell values (dead and alive), and 3 independent cells - that means there's 2^3=8 configurations.

But we're not done yet - all we've done is represent a *single* configuration with a number; whereas what we need to do is map *every* configuration onto a single on-off value: a single bit. Let's work through the (relatively simple) maths, and see how we can do just that.

If we need to map every 3-bit configuration onto a single on-off value, then we'll need a bit for each configuration. We already worked out that there'd be 8 different configurations, so we'll need 8 bits - one for each of the configurations, to tell us whether the cell will be 'dead' or 'alive' in the next cycle.

To define a 1-dimensional automaton completely, we'll need to use each of those 8 bits to describe what happens when the cell is in a particular situation - will it die, or will it survive? That makes it pretty easy to work out how many possible 1-dimensional automatons there are: we just work out the number of distinct numbers representable by an 8-bit number. As it turns out, this is pretty easy - it's just 2^8=256, or the numbers [0, 255].

That's all very well for one-dimensional automata, but aside from Wolfram's Rule 90 generating what looks like a Sierpinski triangle, there's not all that much to see. What about the more interesting two-dimensional automata, like the Game of Life?

Well, the Game of Life is really multiple two-dimensional celllular automata in one. It doesn't care about *which* cells around it are dead or alive, just about *how many* there are. But we can make them more specific than that, just like with the one-dimensional automata: say, if we wanted cells only to be born if the neighbouring cell in the top-left corner was alive (and no other).

We can do this programmatically fairly easily - if we've implemented the Game of Life already it's trivial to alter the program to change the rules, especially if we've abstracted out the code to yield a cell's neighbours. But just how many two-dimensional cellular automata *are* there?

It turns out this is a question we've done all the hard work for - the only change from the one-dimensional automata calculations is the number of cells affecting the cell in question's state in the next generation (instead of 3 cells, we now care about 8 neighbours - notice that our model doesn't use the cell's previous state; this simplifies things somewhat). So instead of 2^(2^3) distinct rules, we can define 2^(2^8). Which is just a mind-blowingly huge number, even considering that some of them will be pretty much symmetrical and act the same way - instead of a number between 1 and 255, we'll need a number between 1 and... uh... 115792089237316195423570985008687907853269984665640564039457584007913129639936. Exactly.

That means it's easy to calculate the number of possible 3D automata too - it's just 2^(2^26), since there's 26 neighbouring cell-cubes which can affect the cell's state in the next generation. But since 2^26 is about 67 million, that means just to store the number I'd need about 8 megabytes. Might not sound like much, until you consider that the vast majority of modern operating systems store numbers in 64 bits - that's around a hundred and twenty-five *thousand* times less.

And of course for a four-dimensional automaton, we could have 2^(2^80) possibilities. But here we're getting into the realms of science fiction - it'd take 0.1511 YB (yottabytes) just to store that number. For comparison, that's about 1.7 *million* times the estimated size of the entire visible and non-visible internet. I think I'll stick to 2-d "glider guns".

*(also, I wouldn't really know how to draw a 4-dimensional cellular automaton. But that seems like a secondary concern.)*