Listening to Elementary Cellular Automata
In this post I’m going to discuss elementary cellular automata, their history, why they are so fascinating, and how we can squeeze some music out of them. I’ll also look at what(in my opinion) is and is not interesting about these sonifications.
What are cellular automata?
Broadly speaking, a cellular automaton is a system containing a grid of cells, where each cell has a state. The system progresses by discrete time steps and at each new time step cells may change their state depending on the some rule or condition (usually related to the states of neighboring cells). The most famous cellular automaton is Conway’s Game of Life, which uses a 2D square grid. I will look at a few of my favorite CA in future posts, but for this post I’ll talk about Elementary 1-dimensional cellular automata (ECA).
Elementary cellular automata
In the case of elementary cellular automata, our ‘grid’ is essentially a 1-dimensional array of cells, and each cell can have one of two possible states. The rules that determine state changes at each time step are concerned with the position of the cell itself and its immediate neighbors. So if we’re at time step t and we want to know the new state of a cell in position n at time t +1, we need to look at the state of cells in positions n-1, n, and n+1, at time t. Since there are only two possible states for each cell, there are only eight possible ways that the triple n-1, n, and n+1 can be configured. If we define what can happen in each of those eight configurations, we can exhaustively define how the CA will behave. States are often displayed visually using colors, for example, white for one state and black for the other. Rule systems can then easily be displayed by showing these eight triples and what state they result in. For example, in the following rule system, we see from the rule on the left, that if n-1, n, and n+1 are all black at t, then n will be white at t +1. The second from the left rule says that if n-1 and n are black, but n+1 is white, at t+1, n will be black and so on.
If we start with a single black cell at the centre of a row of white cells and iteratively apply this rule system for about 15 steps we get the following result:
Rule numbering
Following Stephen Wolfram (more on him later), rules are often referred to with a conventional numbering system. Since there are only eight configurations, each of which can have two values, we can express all of the possible rule systems with an 8-bit number. If we say white is 0 and black is 1, we could express the rule system above with the 8-bit number 01101101.(i.e., black-black-black generates 0, black-black-white generates 1, black-white-black generates 1, and so on). If we convert this to base 10, we get 109, so we can refer to this rule system as rule 109.
What is interesting about 1D elementary cellular automata?
In his 2002 book, A New Kind of Science, Stephen Wolfram makes some very strong claims about cellular automata and the nature of universe. The book is somewhat controversial, and I’m agnostic about many of Wolfram’s claims. The two things I would say about the book is that much of it is absolutely fascinating and much of it is highly infuriating. I’m going to run with a dramatically weaker version of Wolfram’s claims that I think most people can agree with. Basically, he claims that in the past, we tended to always assume that complex phenomena were only understandable in terms of complex underlying systems, for example, using partial differential equations for explaining fluid dynamics. Algorithm-based systems, like cellular automata, can be remarkably simple and yet produce incredibly complex results, as we can easily see. Here is an image of rule 126 (01111110) which generates the fractal pattern known as a Sierpinski gasket:
If we just toggle the 4th bit, we get rule 110 (01101110). Rule 110 has predictable periodic components, but other parts are chaotic, that is, unpredictable except by actually cranking out every intermediate step in the derivation.
On a personal level, I find these endlessly fascinating, and exploring CA was one of the reasons I learned to code. The very first substantial program I ever wrote was a musical sonification of ECA in the Pure Data language which can be found here. Since then, each time I learn a new language, my go-to project is implementing some kind of CA (usually ECA). In addition to Pure Data, I’ve implemented musical ECA in Java, Python, Chuck, SuperCollider, Swift, and JavaScript.
The Sonification Of Cellular Automata
There are two basic approaches that are often taken when sonifying ECA, one is to generate parameters that can be used to control, for example, a synthesizer. The other approach is to map cell states to musical events (MIDI note, drum sample etc.), and this is approach that I have explored in depth.
There are many ways that these events can be mapped. For example, we could take a grid of eight cells, and play them sequentially from left to right, with a black cell signifying an event (e.g., a drum hit) and a white cell signifying a rest. This eight cell grid would generate a single bar of rhythm — from which we could derive a second bar and so on. This approach is more interesting if we have a CA with many states (i.e., not ECA) where we can map each state to a different pitch (I’ll explore an example of this using a modular arithmetic CA in a future post).
The other approach would be to map each cell to a specific pitch or sample and play that note or sample if the cell is black and not play it when it is white. All the relevant events in one step of the derivation are played (or stopped) simultaneously. As we proceed through the derivation at a regular speed, we trigger or stop notes according to their state at that step. This approach allows us to hear cyclic patterns that might come up in the derivation. This is also more or less the approach taken by WolframTones (it’s a fascinating wormhole, but what is actually going on there can be frustratingly opaque).
How to map the cells?
This leaves us with the issue of how to map the cells. If we have a short array of cells we can map each cell to a note in a scale, for example, C major. The first cell would be C, the second D, and so on. And this basically works, but we have many rule sets that might result in numerous adjacent cells being on at the same time — resulting in some serious cluster chords. In general, I find using pentatonic scales a little safer in this respect. Another alternative that sounds nice is mapping each cell to the next diatonic third in a scale, for example, first cell is C, second is E, third is G, then B, D, F, A, and finally the C two octaves up. This gives a little more space to those clusters.
This works well enough if we have a small array, but the visually interesting CA, the fractals and so on, occur on large arrays, and we will quickly run out of notes. If we have 7 cells comprising an octave, then 100 cells would be just over 14 octaves — we don’t enough notes. The solution that most people (e.g., WolframTones) have taken for this is to use a large array to generate the CA, but only sonify a 5–15 cell window contained within.
Here is a CodePen I made that takes this approach (clicking on the CodePen should let you run it in the page here). It will let you hear these results. You can move the window with the left and right arrow keys.
Results
Wolfram classifies CA into four categories. The first category are rules that generate homogenous stable states (i.e., always on or always off), and the third are rules that generate pseudo-random or chaotic patterns, both of which don’t really need to be explored. His second category is rules that generate orderly or periodic patterns, these are the ones most worth exploring from a musical point of view. So we need to think carefully about which rules to use.
Rule 126, the Sierpinski gasket shown above, is a fascinating pattern. But the pattern is global, not local. There really isn’t any position to put our window that won’t miss out on most of the action:
On the other hand, rules 105 and 150 have more local patterns, so we could easily set up a window (or a few windows) here and get some interesting patterns.
Starting with a random array
So far the patterns that I have been displaying have all started with a single ‘on’ cell. If we start with a random array of on cells, then many of these rules will generate events that can be observed within a local window, often displaying characteristic recurring figures. But the system determining how these figures fit together is still global rather than local, so that considering only the local window, the result is still fairly chaotic, even though patterns are distinguishable. Here are a few example of such rules:
My favourite rule: 109/73
But there is at least one rule system that I came across where the local patterns are both self-contained and somewhat interesting, and this is rule 109 (also rule 73, to some extent). For this system, a random array will quickly develop multiple independent local repeating patterns which, because of the left/right symmetry of the rules, do not interfere with each other. Some of the patterns are stable single on or off cells, but many of the patterns are wider bounded patterns with varying periodicity. Small patterns with repeating periods of two, three, and four are quite common. Wider patterns which repeat every 5, 10, 11, 12 steps are not at all rare. Here are a two example derivations:
In the above system, we have repeating sections with periods of 18, 2, 24, and 3.
And here we have repeating periods of 8, 12, 3, and 2.
I found that by moving the window of cells that we are listening to, we can have it straddle multiple patterns with different periodicity, creating interesting polymeter. For example, if the above image, the leftmost column has a period of 8, and its right neighbour has a period of 12. If we include parts of both of them in one window, we have a ‘meta-pattern’ with a period of 24 that will contain 3 repetitions of the left pattern and 2 on the right. These kinds of rhythms can sound very cool.
I wrote some SuperCollider scripts for exploring this rule, which are in an old Github Repo. I had the window traverse the array automatically, detecting when it found a repeating pattern, letting it play two or four times (depending on the length) then moving one cell to the right. This lets it skip quickly through the trivial parts and spend more time at the interesting bits. Here is a video demonstrations. The videos not much to look at (and sorry the audio is a little quiet), but it generates some very cool rhythms:
While we’re talking about repeated local patterns. . .
After discovering rule 109, I went looking for other rules that generate cool local patterns — there aren’t any as far a I know. But you can force local patterns by using very small arrays. One particularly cool phenomenon that I noticed is when you generate patterns with rule 105, using a circular array (i.e., the leftmost cell is treated as adjacent to the rightmost) consisting of 12 cells, you will almost always end up in one of three perpetual loops with a period of 64. This isn’t surprising in itself. CA with a finite array will always fall into a repeating pattern eventually. 12 cells with 2 states allow for a 4096 possible combinations. CA are deterministic, so if any configuration recurs within the same derivation, all the states between the first time that pattern occurred and the second time it occurred will loop endlessly; it will keep cranking out new states until it inevitably produces something from its history, at which point it is deriving a pattern. And in fact, if we think about these configurations as necklaces (i.e, there are 12 configurations with a single ‘on’ cell, but these are all rotations of the same necklace), then there are not many unique necklaces that should expect to see.
Anyway, it is not surprising that rule 105 with 12 cells has these three prominent periodic ‘attractors’. But what is fascinating about them is that all three, after 32 steps, are followed another 32 steps which are the inversion of the previous 32, i.e., they derive their own inversions. The total period of each is 64.
I admit, that this doesn’t have much musical application. But it’s very cool and if you’ve read this far into the post, you’re probably the kind of person who would find this interesting — so I thought I’d share it.
