Skip to content

more musical Turing machines

During the Anathem music project, I tried to imagine many different ways that music might be integrated into the daily lives of the avout, not only in the obvious celebratory liturgical uses, but also as a tool for learning, remembering, and computing. One manifestation of this, geometric games for exercising the learning mind, I’ve already posted about. In this post, I’ll cover another: how the avout might perform calculations using music. A warning and an apology in advance: this post contains a pretty high proportion of propeller-head material.

The age of enlightenment brought with it the hope that all problems, be they physics or metaphysics, could be reduced to the logical manipulation of symbols. As we learned in The Baroque Cycle, Gottfried Leibniz was obsessed not only with metaphysics, with mining technology, with claiming precedence as the inventor of calculus, and with escorting globe-trotting princesses, but also with building a machine that could, by manipulating symbols, separate truth from falsehood. High hopes, such as his, for the power of symbolic representation thrived over the next 200 years as mathematicians, armed with the scientific method, picked apart the basics of arithmetic, algebra, rhetoric, and geometry, teasing out their underlying structures and essential concepts, and coincidentally spawning entire new disciplines such as group theory and mathematical logic. But in the early 20th century, the search for the everything-solver unraveled. Kurt Gödel started the ball rolling with his incompleteness theorem, and around the same time, David Hilbert posed his infamous Entscheidungsproblem (paraphrased by Roger Penrose as “is there some mechanical procedure for answering all mathematical problems?”) Two mathematicians, Alonzo Church and Alan Turing (who appears in Cryptonomicon), independently delivered the coup de grâce by answering Hilbert’s question in the negative, proving once again that there is no free lunch.

As an unintended but very useful side-effect, these guys effectively invented the modern computer.

As part of his proof, Alan Turing invented a “device” capable of executing a finite series of instructions in order to perform a calculation. This device, described using prose alone, was the specification for a very general model of computation now referred to as a Turing machine. A Turing machine has two parts, a “head” and a “tape.” The head can read and write symbols to spots on the tape, and can move along the tape left and right one spot at a time. The head embodies a table of instructions, or “states,” that it uses to perform its computation. The state of the head, plus the value of the symbol currently under the head, completely determine the next action taken, which is determined using a set of transition rules. The initial state of the head and the tape, plus the transition rules, define the computational process.

Because of their generality, it is possible to implement operational Turing machines in diverse ways. (In fact, producing bizarre Turing machine implementations has been a bit of a longtime hobby for computer science grad students with too much time on their hands.) So it should be no surprise that they can be built using musical materials. As an arbitrary example, imagine a solo singer and a long line of choristers. The solo singer plays the role of the Turing machine head, while the individual choristers represent individual storage locations on the tape. The choristers share a palette of distinguishable and repeatable musical events amongst themselves with which to represent symbols, and these symbols are read and written by the soloist as he or she moved left or right along the chorus line. The soloist, in addition to transmitting and receiving symbol values via song, is also free to express both the state of the head and the act of reading and writing as additional musical material, interwoven with and related to the choral sound being emitted by the “tape.”

At the Anathem launch event in San Francisco, I demonstrated exactly how this scenario might sound by leading a choral performance of a three symbol, two state machine that computed binary addition. On the tape, blank spots were indicated by silence, the digit zero was indicated by singing a repeated stacatto note pattern, and the digit one was indicated by singing a sustained tone. The pitches, dynamics, and vowels for these patterns were chosen at liberty by the singer representing the head, who sequentially taught each tape singer what they should be singing as he moved along the tape executing his algorithm. In this performance, the singer playing the “head” had control over changes in musical texture, since changes could not be instigated by the singers constituting the tape. The “head” had additional control: he could move at whatever speed he chose, and could select pitches and patterns based upon the currently sounding musical texture. The result was musically interesting, but the performing life of a member of the tape was pretty boring and unrewarding, since he or she did nothing but repeat motives passed on by the soloist.

A cardboard tetrahedral Turing machine head

A cardboard tetrahedral Turing machine head

To make life as a member of the tape more interesting, I then demonstrated a variation on this technique which reversed these roles and put the individual singers of the tape in control. Rather than embodying the head as a separate all-powerful singer, the “head” in this variation was a physical token that could be passed from singer to singer along the tape, and which was read and interpreted by the singers themselves. It is easier to show this by example than to explain it; look at the photograph to the left to see a token in the form of a tetrahedron, each face of which is a different color. The colors represent the states that the head can take, and the flow of logic within each state is represented by flowcharts printed on each face of the tetrahedron. Changes of state and movement of the head along the tape are meant to be accomplished by the singers as they change the exposed upper face of the tetrahedron (the “current state”) and pass it to their neighbors, following the instructions printed on the token.

In a token-passing performance of this sort, the musical interest is generated by the movement of the tetrahedron along the line of singers, and the decisions that they make while interacting with it. It is easy to adapt such a machine to two dimensions, which also adds depth. In this case the tetrahedron is not only passed left and right, but also forward and backwards. (Two dimension Turing machines such as this are often called Turmites – this link shows the plan for a tetrahedral head for a four state, two symbol, Turmite.) Although the performance is very sensitive to the algorithm used (members of the tape can still be stuck singing the same thing over and over again) the process of producing the music is slightly more interactive, and this technique definitely shows promise as a basis for collaboratively produced generative music.

Turing’s machine was one of the first in a long line of what those of us who study computers or discrete math call finite automata. In another post, I will examine some of the musical features of another form of automaton: the cellular automaton. This machine, coupled with music-specific algorithms, has already proved a fruitful source of structure for many composers, generative musicians, and instrument builders.