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