- Fundamental Insights on Complex Systems Arising from Generative Arts Practice

Algorithmic-based music underwent a paradigm shift over the last two decades of the 20th century with the advent of complex systems research. Complex systems such as cellular automata (CA) produce global behaviour from rule-based interactions of simple cells. CA have had a distinguished and esoteric history—in computer science since its foundation to their present-day influence in Artificial Life, as well as numerous other important disciplines. They are fascinating objects, producing more pattern than a single human is capable of observing within their own lifetime. The different classes of behaviour they produce, whether ordered, complex or chaotic, make them interesting to artists and scientists alike. This wide variety of behaviour represents an important generative tool for the artist. However, chaotic behaviour dominates rule space, which has serious implications for application and investigation. Obtaining a variety of *pattern for free* is thus a challenge to the artist and scientist alike.

CA are discrete dynamical systems in terms of space, time and values assigned to cells. The set of all possible global states of these cells is termed the *state space*. The set of all possible rules for any particular CA architecture is termed the *rule space*. A concise definition of CA is given by Andrew Wuensche and Mike Lesser [1]:

*A cellular automaton (CA) is a discrete dynamical system which evolves by the iteration of a simple deterministic rule*.

Wuensche has stated: "Traditional mathematical methods and analysis cannot in general provide a description of the long term behaviour of discrete dynamical networks except for the simplest special cases" [2].

Stephen Wolfram has proposed twenty key unsolved problems in the theory of CA [3]. The seventh problem asks: *How is different behaviour distributed in the space of cellular automaton rules*? The task of assigning behaviour to a rule is known to be undecidable [4], but a number of approximations have been attempted. An extensive amount of research by the CA scientific community has been conducted towards producing behaviour prediction parameters to discern the structure of rule space. Unfortunately, as the size of the CA rule space is increased the total number of rules becomes astronomical and the amount of chaotic behaviour increases dramatically.

The magnitude of the numbers of rules is extremely large, increasing in a dramatic manner even if only neighbourhood size or the number of possible cell states is increased. Tommaso Toffoli and Norman Margolus also discussed the problems of rule choice [5]. They point out that binary rules with just 9 neighbours, amounting to 2^{512} rules, is "the square of the estimated number of elementary particles in the universe!" Wentian Li has commented on the binary one-dimensional 5 neighbour rules: "Even if we can produce a spatial-temporal pattern from each rule in 1 second, it is going to take about 138 years to run through all the rules. Considering the redundancy due to equivalence between rules upon 0-to-1 transformations, which cut the time by half, it still requires a solid 69 years" [6] .

This problem continues to engage the scientific community and is the subject of much debate.

In confronting systems of such behavioural complexity for the purpose of art, the artist is placed in a possibility space of truly vast proportions. Given that the potential for random behaviour increases with rule space, choosing CA rules at random does not represent a successful artistic strategy, unless one is actively seeking randomness. This problem has great implications for the use of CA in both scientific and generative arts practice.

I approached the problem of rule space structure from an artist's perspective in the context of generative music practice. Hal Chamberlin noted that the production of algorithmic data for musical control "may be highly ordered, totally random, or somewhere in between" [7]. It follows then that all CA behaviours are "interesting"; the music practice problem is to find a mixture of behaviour from the overwhelming chaos. This is in contrast, but not in opposition to, the scientific approach of predicting behaviours in order to locate complexity within rule space.

The techniques are based on recent perspectives of CA theory called...