Automata Bending: Applications of Dynamic Mutation and Dynamic Rules in Modular One-Dimensional Cellular Automata

A cellular automaton (CA) is often considered a software model of a machine (e.g., a computer) that runs a set of procedures (e.g., software). Such a model is implicit in the sophisticated demonstrations of universal computation that cellular automata can perform, such as John von Neumann's model of a two-dimensional, 29-state CA (1966); Edwin Roger Banks's model of a two-dimensional, binary-state CA (1971); and Matthew Cook's model of a one-dimensional, binary state, rule-110 CA (2004). Others, using CA for a wide range of alternative applications, have often followed this approach, using strict and fixed rule sets to produce systems capable of reliable computations. In artistic applications of CA, however, there is no mandate to use "pure" implementations: the question of whether a CA functions as a proper machine, capable of universal computation or otherwise, has no significance on the extraction of artistically useful value streams.

Bending or even breaking the rules of a CA, introduced here as "automata bending," is analogous to the circuit-bending techniques demonstrated by Qubais Reed Ghazala and others (Ghazala 2004; Collins 2006). As with circuits, applying such techniques to CA permits transforming simple and elementary systems into more-dynamic generators. There can be no objective measure of aesthetic advantage in bending an automaton; such an approach, however, expands the parametric interface of the CA, giving the user more-flexible controls to shape and even direct CA evolution. The parametric interfaces of generative systems must be adapted to the needs of composers; this is an important component of research in computer-aided algorithmic composition (CAAC).

The utility and diversity of CA are frequently overstated. For example, Eleonora Bilotta and Pietro Pantano offer the unqualified claim that CA "display rich and complex patterns, whose organization is completely unpredictable" (2002, p. 156). The majority of CA, in many formats, produce trivial repeated patterns or plain "chaotic" randomness (Wuensche 1999, p. 54); it is the minority of CA that display rich and complex behavior. Furthermore, traditional CA are deterministic: they may be capable of producing randomness (Wolfram 1985), but this randomness is entirely predictable. With the application of automata-bending techniques, however, even repetitive or static CA can be used to generate dynamic data.

In the rare cases that CA do exhibit emergent behavior, this behavior is often realized only in large data spaces, covering expanses of cell state histories easily on the order of tens of thousands, if not significantly more. Except in applications of CA data to audio-rate parameter values, practical usage requires obtaining values from the CA on much smaller numerical scales. Automata-bending techniques, as well as flexible methods of extracting values from the CA, reduce the data space necessary to obtain practical value streams.

This article introduces a language-independent string notation for, and a flexible implementation of, a variable format one-dimensional CA. This CA model permits two types of automata bending: random cell-state mutation, and dynamic, probabilistic rule-sets. Numerous formats of one-dimensional CA (such as standard, totalistic, and continuous), as well as all k and r values (within hardware performance constraints), are supported. The application of CA values to musical parameters is facilitated by diverse methods of masking cell data and extracting one-dimensional value sequences. Rather than the common approach of hard-wiring CA values to fixed mappings or musical parameters, this model promotes a modular approach, making the CA into a flexible and dynamic one-dimensional value generator. These values can be applied to a wide range of musical parameters, such as event amplitude, panning, rhythm, or pitch; synthesis configurations, envelopes, or wave tables; or direct waveform specification. As a modular component, CA parameter inputs may be controlled by lower-level embedded generators, and CA output values may be used as input for higher-level generators. Ultimately, a modular design promotes using CA-derived values in the same manner as a simple component of a modular synthesizer. While the approach presented here may be implemented in a variety of systems, high-level object interfaces to...