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?
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:
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.
The John Cage instruction (
%) causes a one note silence in the output stream. The transposition value of a John Cage is zero -
%+are no-ops (except that a single silence is added to the output).
The Repeat Bars instructions (
:||) 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.
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
~has been used outside any repeat bars), then the performance will immediately terminate.
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
=-3or by marker - the note played after marker
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+yin a conventional programming language (where
yrepresents 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.
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.
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.
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.
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.
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.
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.
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.