71

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?

8
  • 7
    what is music partition language? some form of musical notation?
    – gnat
    Feb 21 '12 at 12:46
  • 4
    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.
    – nikie
    Feb 21 '12 at 12:47
  • no, it does not
    – shabunc
    Feb 21 '12 at 13:04
  • @nikie I'm not sure if a refrain act as a stored function or something similar...
    – Klaim
    Feb 21 '12 at 15:29
  • 4
    Of course it is Turing-complete, simply use 8 different notes to represent the 8 characters of Brainfuck. :) Mar 12 '12 at 12:28
48

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.

5
  • 2
    I'd say this is the best answer to the question: none of the other answers prove that musical notation is not Turing complete.
    – K.Steff
    Jun 3 '12 at 4:03
  • This is the most interesting question I’ve seen all year Apr 12 '20 at 21:26
  • 2
    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.
    – JacquesB
    Apr 23 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.
    – Jon Purdy
    Apr 23 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.
    – JacquesB
    Apr 24 at 9:48
25

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.

11
  • 13
    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.
    – Jesper
    Feb 21 '12 at 14:00
  • 53
    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 ;-)
    – nikie
    Feb 21 '12 at 15:40
  • 12
    @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. Feb 21 '12 at 17:10
  • 7
    @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.)
    – nikie
    Feb 21 '12 at 22:50
  • 9
    @MasonWheeler: Lambda calculus is real computer programming. Feb 24 '12 at 7:37
24

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.

4
  • 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?)
    – Izkata
    Feb 21 '12 at 15:22
  • 2
    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.
    – S.Lott
    Feb 21 '12 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 =)
    – Izkata
    Feb 21 '12 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). Jun 3 '12 at 21:08
4

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.

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.

3
  • 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".
    – Esther
    Apr 23 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.
    – JacquesB
    Apr 23 at 9:44
  • 1
    @Esther: I have updated the answer with a more detailed proof taking repetitions and D.S. into account.
    – JacquesB
    Apr 23 at 12:21
2

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.

1
  • 1
    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. Jun 3 '12 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.