Turing Completeness – Is Musical Notation Turing-Complete?

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.