up vote 59 down vote favorite
11

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?

share|improve this question
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
    
@gnat Yes, sorry, thanks for the correction! – Klaim Feb 21 '12 at 14:50
2  
Of course it is Turing-complete, simply use 8 different notes to represent the 8 characters of Brainfuck. :) – Chris Burt-Brown Mar 12 '12 at 12:28
up vote 33 down vote accepted

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.

share|improve this answer
1  
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
up vote 23 down vote

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.

share|improve this answer
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
47  
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
10  
@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. – Mason Wheeler Feb 21 '12 at 17:10
5  
@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. – dan_waterworth Feb 24 '12 at 7:37
up vote 23 down vote

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.

share|improve this answer
    
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). – Tikhon Jelvis Jun 3 '12 at 21:08
up vote 3 down vote

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.

share|improve this answer
up vote 1 down vote

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.

share|improve this answer
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. – Tikhon Jelvis Jun 3 '12 at 21:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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