What is a Cellular Automaton?

When I think of the term automaton, I picture something like a robot, but another context in which the word is used is the idea of a cellular automaton, which is a dynamical system involving an array or grid (that's the "cellular" part) that evolves in discrete time steps according to simple rules. The way cellular automata most resemble robots is in the rules, or "programming," if you will.

What's a dynamical system? Basically any system that changes in time. We can call something like the weather a dynamical system. What makes weather different from cellular automata is that we can analyze the weather of whatever size space we want and time passes essentially continuously.

CAs are simpler—space is divided into clearly separate cells and time evolves in a step-wise fashion, almost as though each step is a turn in a game. In fact, the most famous cellular automaton is probably Conway's Game of Life which can be "played" here. It consists of a 2D grid of cells, with different colors for "alive" and "dead" cells.  The rules by which it evolves are:

• start with some arrangement of live cells
• any live cell with fewer than two live neighbors dies
• any live cell with two or three live neighbors lives on to the next generation
• any live cell with more than three live neighbors dies
• any dead cell with exactly three live neighbors becomes a live cell

One layout possible at the link above looks like this:

To get this, select "Gosper Glider Gun" from the pulldown at the bottom.  This pattern is so named because as it evolves, the live cells form patterns of "bullets" that shoot in the direction of the picture's bottom left.

Steven Wolfram (of Wolfram Alpha and Mathematica fame) and collaborators studied one-dimensional versions of these. Think of a few cells along a line instead of a grid, and each cell evolves according to its own status and that of its nearest neighbors. And instead of one set of rules, we have 256 of them. Wolfram MathWorld is an incredible resource for many topics in math, but this one especially.

I will explain some of the specific rules in later posts about my songs that use CAs. But here it is worth asking the question: why are these cool and why would a musician be interested in them?  

CA patterns evolve in one of four ways: (1) the diagram quickly turns all one color or the other, (2) the configuration freezes into a regular pattern such as diagonal lines, (3) the cells seem to evolve chaotically, and (4) there isn't a regular pattern to the cells but they do have complex local structures. For item (1) I chose the simplest rules since those get to one color quickly with a single colored cell starting us off, but different initial conditions evolve this way for other rules.

Some rules even evolve into patterns that look like fractals. More on those later.

With one point and a specific rule, a fractal pattern emerges!  (reference)

So what I did was play around with some initial conditions and patterns to see what emerged. I then converted the patterns to rhythms with black cells corresponding to eighth notes and white cells to quarter notes. In one song ("Rule 34"), there are two sections, each with an intro pattern setting up the main pattern of the section. A different time signature is needed for each introduction and section. In another (called "Room 101" but using Wolfram's Rule 101), an initial condition appears to evolve chaotically, and the music's pattern is equally crazy. It's basically a different rhythm and time signature for each measure. After some of this, though, the pattern stabilizes into what I call the main groove of the song.

People make up different rhythmic ideas for sections all the time, but I think CAs gave me some interesting ideas to play with. Even hearing them with a simple clave track made me hear melodies in my head I normally wouldn't have had access to.