# Is musical notation Turing-Complete?

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?

• what is music partition language? some form of musical notation?
– gnat
Commented Feb 21, 2012 at 12:46
• I don't know much about music notation: can you somehow encode an unbounded amount of "mutable variables" (or "tape")? Otherwise, I don't see how it could be turing complete. Commented Feb 21, 2012 at 12:47
• no, it does not Commented Feb 21, 2012 at 13:04
• @nikie I'm not sure if a refrain act as a stored function or something similar... Commented Feb 21, 2012 at 15:29
• Of course it is Turing-complete, simply use 8 different notes to represent the 8 characters of Brainfuck. :) Commented Mar 12, 2012 at 12:28

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.

• I'd say this is the best answer to the question: none of the other answers prove that musical notation is not Turing complete. Commented Jun 3, 2012 at 4:03
• This is the most interesting question I’ve seen all year Commented Apr 12, 2020 at 21:26
• If you are allowed to add your own processing rules (like this answer does) they you can trivially prove that anything is Turing complete. I can easily prove a bag of chips is Turing complete by that approach. But this does not tell you anything of interest. Turing completeness is only a meaningful criteria if you apply it to an automaton or language which consist of both symbols and rules for how the symbols are manipulated. Commented Apr 23, 2021 at 9:54
• @JacquesB: Right—it’s important to note that a notation on its own cannot be TC! The proofs that, for example, Magic: The Gathering is TC are based on using the rules of the game to implement the rules of a TM. So really, my answer only says that musical notation is syntactically equivalent to Choon, whose rules make it TC; it’s a proof by trivial compilation/“transpilation”, which is the best I could come up with. Commented Apr 23, 2021 at 17:39
• @JonPurdy But this is the case for any notation. If you just map the symbols in an arbitrary language to the symbols in a Turing-complete language, then you can prove that absolutely anything is Turing complete. Commented Apr 24, 2021 at 9:48

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.

• It sort-of has conditional jumps, used in combination with repeat signs: "on the first repeat, play this part, on the second repeat, play that part". The repeat counter (that you'd hold in your head while playing) is state. But it indeed doesn't have an infinite tape containing state. Commented Feb 21, 2012 at 14:00
• Fun fact: Lambda calculus has no loops, no conditional jump, and no way to store results of calculations somewhere in memory. Yet it is turing complete ;-) Commented Feb 21, 2012 at 15:40
• @Nikie: Don't confuse abstractions with realities. Lambda calculus has a concept of conditional evaluation, recursion is used for both looping and jumping, and state is computed as the results of evaluating expressions. The concepts are there; they're just implemented in a very different way from real computer programming. Commented Feb 21, 2012 at 17:10
• @MasonWheeler: LC doesn't have fundamental concepts of loops, state and conditionals, but you can derive things that serve a similar purpose. That's just another way to say that it's Turing complete. So the question is not: does musical notation have these concepts, but: can you derive them somehow? You simply claimed that you can't, without proof. (I agree with your conclusion, I just don't think your reasoning is valid.) Commented Feb 21, 2012 at 22:50
• @MasonWheeler: Lambda calculus is real computer programming. Commented Feb 24, 2012 at 7:37

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.

• Well, you can't really rewind a running program, either... (But yeah, I get what you mean about updating the state, but could that in turn be a functional language?) Commented Feb 21, 2012 at 15:22
• You don't rewind the program. You rewind the tape. The point is that the Turing tape has all positions accessible. It's "Random Access Memory" simplified to a linear time with forward and back motions. Commented Feb 21, 2012 at 16:19
• Ohhh, I remember that now, sorry. I was thinking of "tape" as the thing the music was written on for some reason =) Commented Feb 21, 2012 at 17:39
• Building a Turing machine is the standard way to prove something is Turing complete, but the converse is not true--simply because you cannot figure out how to build a Turing machine does not mean something is not Turing complete. A Turing machine (with a tape and all) is just an arbitrary abstraction that has enough computing power; there are other abstractions just as powerful with no notion of tapes. Take a look at lambda calculus, SKI calculus or some esoteric languages (Fractran is cool). Commented Jun 3, 2012 at 21:08

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.

• I hate to ask, but: is this true? Like, even very conservative notation has goto, in the form of D.S.; and storage and conditionals in the form of first-, second-, etc. "time" bars. I don't know enough to vouch for the accuracy of this answer on minimal features for turing-completeness, but my reading of it would say "yes, it's possible to use these features to write sheet music that cannot be determined to end". Commented Apr 23, 2021 at 7:40
• @Esther: The only kind of "state" in a music score is how far you are in the score. It is like a Turing machine which only read the tape but never store anything in a cell. This is not sufficient for Turing completeness. The repeated sections may look like loops and conditionals, but they are determined by fixed numbers (e.g. repeat n times, play this the second time), so they can be trivially expanded to a completely linear score. Commented Apr 23, 2021 at 9:44
• @Esther: I have updated the answer with a more detailed proof taking repetitions and D.S. into account. Commented Apr 23, 2021 at 12:21

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.

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.

• What you listed is not necessary for a Turing complete language. Lambda calculus only has applications, variables and lambdas (e.g. no loops, states or commands) but is Turing complete. The same goes for a bunch of other models of computation like SKI combinators. Commented Jun 3, 2012 at 21:10

I know this is an old thread - but to add in some things not considered here. Although with first ending, seconding ending scenarios you know how many times you are going to repeat, this isn't the case with all musical structures - Vamp measures are repeated with no particular numbers of repeats. It's entirely up to the conductor at the time it is played. Theoretically you could repeat a vamp measure infinitely (as long as you had additional players and alternate conductors to swap out with while you are in the act of playing you could literally go on for as long as there are human beings in existence)

It should also be noted that musical notation is not a science. While there are many rules for what to do, at the end of the day the person doing the notation can "fudge" things to make the score more readable by musicians (and they often do). Not only that but music notation can't even express everything that happens in music - it's really just an approximation. Take swung 8th notes - some people say it's the equivalent of an 8th note triplet with the first two notes tied (so a 2/3rds 1/3rd relationship). Others say its the equivalent of 16th notes with the first 3 tied. Still others say that "the upbeat should be played as close to the downbeat as possible" (so maybe more like a 64th note, or 128th note, or....) And then all of this also depends on the written instructions - do they say "swing" or "hard swing"?

Also of course there are many different music notation systems in existence. The standard Western Art Music notation system doesn't take into account quarter tones. (and really that's even arbitrary - you could also do 1/3 tones or 1/8 tones. You could even go down to cents. I don't know of any composer who has done so, but its entirely possible. You'd have to develop a new notation system to convey that (and you'd probably have to use instruments where you set the pitch up front and then it doesn't change (such as a piano) or something electronic.)

Of course when it comes to things like "Danger Music" the concept of a fixed notation breaks down almost completely.

Going back to standard Western Art Music, and performing only what is notated with it's limited set of notations, you can of course still take the same piece and perform it 10 different ways - not because of mistakes but because of how much the conductor chooses to accelerando and ritard. How long does the conductor hold a fermata? How long of a break does the conductor put in after a caesura?

Really music notation is a "rough" method of giving ideas to the musicians (conductors included) to try to make something musical sounding. But even if you ignore the actual performance of music and just look at notation, there are still many undetermined factors that even with textual explanations don't have a solid, consistent meaning.

I don't see how anything that unstructured could ever be close to being Turing complete.