< Blog

Elementary Automata

Imagine a bunch of cells lined up in a row, some are set to 1, some to 0. Each cell has a neighborhood consisting of itself, the cell to its left, and the cell to its right. And there's a concept of time (just like in Conway's Game of Life), where whenever time advances, each cell looks at its neighborhood and decides what its next state should be.

This setup is called an elementary cellular automaton.

How the cells decide what their next state should be is captured in the rule, which is basically a lookup table. You line up the cell's left neighbor, then its own value, then its right neighbor, and look up what the next state should be, based on that.

Here's the lookup table for Rule 30. (That's the rule pictured in the diagram above when you first load the page.)

Current 111 110 101 100 011 010 001 000
New 0 0 0 1 1 1 1 0

So if a cell starts out alive (1), with an alive cell to its left and a dead (0) cell to its right, then its current state is 110 (first 1 for the alive cell to its left, second for the cell itself being alive). We look up "110" in the table, and its entry is "0", so our new value for this cell will be 0, or dead.

There is the question of what to do at the edges. My preferred approach is to pretend that we're on a circular strip, so rightmost and leftmost cells are next to each other. (If you want to see what I mean, change the "Rule" in the diagram at the top of the page to "2", and make sure that "Starting Points" is "One Point", and you'll see the one living cell drift right past the end of the screen and reappear on the left.)

Oh, and as for why it's called "Rule 30"... notice how the "New" row is just eight 1's and 0's? Well if you line them up like "00011110", then that's how you write 30 in binary. Notice how, as you change the rule in this diagram, the 1's (darker cells) and 0's (white cells) in the rule chart at the bottom also read like a binary number.

Since those eight values completely characterize how the rule works, that means that there are 256 (2 raised to the 8'th power) possible rules, and you can completely capture the rule with a single number from 0 to 255.

Well, there are 256 possible rules, but some of them behave basically the same. If you count rules as the same if they differ either by flipping left and right, or by swapping all 1's and 0's, then there are 88 distinct rules. If you want to see what I mean, go up to the top diagram and see what happens with rules 30, 86, 135, and 149.

Here's a visual to show how the rule gets applied. It defaults to Rule 30, but you can change it to another one if you want (anything from 0 to 255 is fair game). You can also add the next generation of cells to see how a rule builds on itself through more than one generation.

That row of palomino-like things at the bottom is the lookup table. For rule 30, it captures the same thing as the table above, just using light and dark cells instead of ones and zeroes.

I find this stuff so fascinating because even though the rules are so simple and in a sense, so similar to each other, there's a huge amount of variety in how they behave. Play around with the diagram at the beginning of the page and you'll see what I mean. You can change the rule, and also the starting cell layout, so you can see what happens if the world starts out with one cell alive and the rest dead, and also what happens if the world starts out with a kind of random assortment of cells.

It's only kind of random because I wanted to be able to look at how the same "random" cell layout was changed by different rules, so it won't change between page reloads or re-renders. Sort of like decided by fair dice roll.

Here are a couple of rules that I find particularly fascinating:

Play around with the rules. Which ones seem the most interesting to you?