Binary counting and cellular automaton rules

In my last post introducing the idea of a cellular automaton (CA), I described a CA as a system that evolves on a turn-by-turn basis according to a set of simple rules. Conway's Game of Life is a 2D grid on which cells are born, survive, and die from one step in time to the next.

I summarized the rules of Conway's game in five bullet points. The CA systems I use in my music are 1D instead of 2D, and instead of the rules being summarizing the rules as bullet points, they exist in chart form. One such chart was shown in the "rule 90" image from my last post (again, many of these images come from here):

The summary of rule 90 is at the top, and it looks like a bunch of colored Tetris pieces. These pieces tell us everything we need to know about the rule. To see a cell's status on the next "turn," you need to know the cell's current status and the status of its two nearest neighbors. For example, look at this part blown up from the upper left:

This piece tells us two things: (1) if a cell is currently black and its two neighbors are as well, it will be white on the next turn and (2) if a cell is currently black and has a black cell on its left and a white cell on its right, it will be black on the next turn. You can go to the right along that chart and see all the other possibilities for bunches of three cells—there are eight of them because there are 2^3 or 8 possibilities for each set including a cell and its neighbors.

You might fairly ask, "What about the edges?" Typically, we solve that problem by using what is called periodic boundary conditions. Briefly summarized, that means that wrap-arounds work.  So if you're a cell on the right edge, you have a left neighbor as usual, and your "right neighbor" is the cell on the far left of the pattern - that's the other cell that dictates your color next turn.

So why is this picture called rule 90?  If you look at the numbers below the rule picture, you see a series of zeroes and ones:

Notice the blocks with zeroes involve a cell being white on the next turn and blocks with ones involve a cell being black on the next turn. The eight possibilities are arranged in the same order for each rule set, but the ones and zeroes change. Read left to right, we get a number 01011010. This is a binary number.

Our normal counting is done with a ones place, tens place, hundreds place, etc., with each place filled by a digit 0-9. Binary numbers have a ones place, twos place, fours place, etc., with each place filled with a digit 0-1 (corresponding to "off" and "on" in a circuit - something computers understand for sure.) So 01011010 = 0x128 + 1x64 + 0x32 + 1x16 + 1x8 + 0x4 + 1x2 + 0x1 = 64+16+8+2 = 90.

We can represent any number from 0-255 in binary using eight binary places, so there are 256 rules we can make using different combinations of ones and zeroes. Rule 0 would mean that no matter what the state of a cell and neighbors is, the next turn will yield a white cell. Rule 255 means that no matter what the state of a cell and neighbors is, the next turn will yield a black cell. So those two rules form pretty boring patterns (all white or all black)—it's the ones in between that became interesting to me.

Check out the picture of rule 90 again. Go down the rows and see how one row evolves to the next - use the rule table to check! We see that as the pattern evolves, we get a picture that looks like the fractal Sierpinski's Triangle. That link gives some very technical details, but a cool thing to see from it is that more than one CA rule gives the triangle.

I became interested in what kind of patterns could come from different rules and starting conditions, and so my next step was to get on a computer and start playing around with numbers by trial and error. Many rules and starting states of the CA "game" are boring, but a few inspired some music, as my next two posts will discuss.