Is musical notation Turing-Complete?

Question

I'm wondering, is music notation language Turing-Complete?

My first thought is that there are loops in musical notation, but there is no way to write conditional branches, right?

I'm not a musician, so perhaps someone can help fill in the gaps?

Answer 1

Yes, if you admit a few instructions for transposition—uncommon but not unknown.

You can then interpret a piece as Choon, which is Turing-complete. The performer is the memory: they must remember the number of notes by which the piece is currently transposed, and all of the notes they have played thus far. Obviously it’s feasible only for a computer, or perhaps a savant.

From the Choon manual:

• Transpositions

  There are three transposition instructions, up (+), down (-) and cancel (.). A transposition instruction transposes all subsequent notes played by the amount of the last note played. The cancel instruction (.) sets the transposition back to zero.

  Transpositions are cumulative, so the Choon code to transpose future notes up by 2 is b+, and by 4 would be b++. Also, the value used is the value of the previous note after transpositions have been applied, so b+b+ transposes future notes up by 6, not by 4.

• John Cage

  The John Cage instruction (%) causes a one note silence in the output stream. The transposition value of a John Cage is zero - %- and %+ are no-ops (except that a single silence is added to the output).

• Repeat Bars

  The Repeat Bars instructions (||: and :||) enclose a loop. The loop will execute the number of times indicated by the most recent note played before the ||: was encountered. A zero or negative value will mean Choon will immediately jump to start playing from the matching :||. A John Cage means repeat forever - %||::|| is an infinite loop.

• Tuning Fork

  The Tuning Fork instruction ~ provides a way to break out of loops. If a tuning fork is encountered in a loop, and the last note played was a note of value A, then Choon will immediately jump to start playing from after the next :|| instruction. If there is no further :|| instruction (meaning ~ has been used outside any repeat bars), then the performance will immediately terminate.

• Markers

  Markers provide marvellous programming convenience. A marker is a lower case letter or word that remembers a point in the output stream. Referring to a marker (see below) will cause the note played after the Marker occurred to be played again. Note that transpositions will affect this newly played note.

  Where two or more markers occur sequentially, or a marker follows a play-from-marker instruction, they must be seperated by whitespace.

• Play From Output

  The Play From Output instruction (=) allows you to play again notes that have already been played in the output stream. You can refer to the notes by number - the 5th note played since the program began would be =5, by relative number - the 3rd most recent note played would be =-3 or by marker - the note played after marker x would be =x.

  It is a common idiom to re-use a marker and immediately then refer to it, like this: x=x. This is akin to saying x=x+y in a conventional programming language (where y represents the currently effective transposition value).

A John Cage is just a rest, a Tuning Fork is (roughly) dal segno, and a marker is a segno. I suppose the tuning fork could be played by an additional performer to whom the primary performer responds, but the principle is the same.

Answer 2

Turing completeness requires, at a minimum, three things: an infinite loop, a conditional jump (if-then), and a way to store the results of calculations to somewhere in memory. Even if musical notation had conditional jumps, it doesn't have state, so no, it's not Turing-complete.

Answer 3

The standard proof for a language to be Turing complete is to write a Turing machine in that language. This proves that there's an equivalence between the language (usually a subset of the language) and the Turing machine.

The notion of "Musical Notation" is a bit slippery. There is a lot of standardized engraving that is used. However. There are envelope-pushing composers who write all kinds of crazy stuff down on paper.

Let's pretend you want to focus on the subset of musical notation that is considered standard enough to be part of Finale or Sibelius or some main-stream engraving toolset.

So.

For Python (or C or whatever) you define the symbols, the tape, the transition rules, and the various actions which update the tape to reflect state change and tape motion, reading and writing symbols on the tape.

Using "Musical Notation", we have to define symbols and the stateful tape, the transition rules and the various actions which update the tape.

What we lack is a stateful tape and rules that tell the musicians how how to responds to symbols on the tape and how to update that tape.

In a sense, the noises flowing around in the air might be the stateful tape. But. There's no easy way to rewind the tape. This lack of rewind means that the performer would have to keep a private "tape" of some kind.

This gets outside musical notation and into some other extra-musical instructions to the performer.

Answer 4

No. You can always determine by looking at the sheet music if the piece goes on forever or eventually finishes. Therefore musical notation does not exhibit the halting problem, which proves it is not Turing-complete.

Turing completeness refers to a set of symbols and a set of rules for manipulating these symbols. The rules are the interesting part. The symbols can be anything, and it is well known that you can get away with just two symbols.

If we just consider musical notation a set of symbols and then make up our own set of rules then sure, we can easily create a turing-complete system. We can do that with any set of arbitrary symbols, so that doesn't say anything interesting about musical notation in particular.

But if we only accept the rules implicit in the musical notation (i.e. how musicians are supposed to interpret the notes and play them), then no, musical notation is not Turing-complete. We can always determine (in finite time) if a a piece of sheet music terminates or repeats indefinitely.

Repetitions does not help, since sections are always repeated a fixed number of times. Repetitions is just a more compact notation for a longer completely linear section.

The "jump to symbol" (D.S. or Dal Signo) notation can create an infinite loop, but it can always be determined (in finite time) if this leads to an infinite piece or not.

---

OK, someone asks for proof. Can we device an algorithm which for any arbitrary score can determine of playing the score will terminate or go on forever?

We are specifically concerned about repeated sections, alternate sections and "jump to symbol" since these affect the execution, and on the surface look like loops, conditionals and goto's.

1. Expand all repeated sections, taking alternate endings into consideration. Since sections are always repeated a fixed number of times this creates a longer, but still finite, score.

2. Now traverse the score from the beginning, keeping track of which parts we have visited. When there is a "jump to symbol", we follow the jump. If we visit a section of the score which we have already traversed, we know there is an infinite loop, since there is no other state which will cause the next iteration to be different. If we reach the end, we know the score terminates. We know this traversal can be done in finite time, since regardless of the number of jumps, we only visit any part of the score once.

Answer 5

Much of the notation is open to interpretation, and natural language instructions are an accepted aspect of musical notation -- and have been throughout most if not all of the history of Western notated music.

Fermatas by definition depend on the performer's discretion, which means that it would depend on their own state, which is almost always altered by the music in conjunction to external factors -- so this raises some questions on the stateless nature of musical notation.

Canon a 2 per Tonus from Bach's Musical Offering is an infinitely looped piece whose tonality rises by a whole step each time through for as long as the piece is performed.

More recently, it's common to see instructions such as "repeat for each soloist" in, for instance, notated versions of Jazz pieces such as Dave Brubeck's Take Five.

That said, aside from inherently arbitrary aspects like the fermata, as the other answers state, musical notation with nothing but the general symbols is probably not Turing complete.

Answer 6

It is not related to Turing complete languages as it is a descriptive language. There are no commands in terms of calculation or modifying data, no states, no input, no output except for the result of the description itself.

Also there are no conditional jumps depending on the input. When you resolve all the jumps you get a linear structure, not a tree. So all "programs" which can be modelled by this language are linear without any loops or jumps at all.