La notazione musicale Turing-Complete?

Sì, se ammetti alcune istruzioni per la trasposizione - non comuni ma non sconosciute.

Puoi quindi interpretare un pezzo come Choon , che è completo di Turing. L'esecutore è la memoria: devono ricordare il numero di note con cui il brano è attualmente trasposto e tutte le note che hanno suonato fino a quel momento. Ovviamente è fattibile solo per un computer, o forse un savant.

Dal manuale Choon:

• 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 è solo un riposo , un diapason è (approssimativamente) dal segno e un marker è un segno. Suppongo che il diapason possa essere riprodotto da un esecutore aggiuntivo a cui risponde il primo esecutore, ma il principio è lo stesso.

La completezza della Turing richiede almeno tre cose: un loop infinito, un salto condizionale (if-then) e un modo per memorizzare i risultati dei calcoli in qualche punto della memoria. Anche se la notazione musicale ha salti condizionali, non ha stato, quindi no, non è completa di Turing.

La prova standard per completare una lingua con Turing è scrivere una macchina di Turing in quella lingua. Ciò dimostra che esiste un'equivalenza tra la lingua (di solito un sottoinsieme della lingua) e la macchina di Turing.

La nozione di "notazione musicale" è un po 'scivolosa. C'è un sacco di incisioni standardizzate che vengono utilizzate. Però. Ci sono compositori che spingono le buste e scrivono su carta tutti i tipi di cose pazze.

Facciamo finta di voler concentrarti sul sottoinsieme della notazione musicale che è considerata abbastanza standard da far parte di Finale o Sibelius o di un set di strumenti per incisione principale.

.

Per Python (o C o altro) definisci i simboli, il nastro, le regole di transizione e le varie azioni che aggiornano il nastro in modo che riflettano il cambiamento di stato e il movimento del nastro, leggendo e scrivendo simboli sul nastro.

Usando "Notazione musicale", dobbiamo definire i simboli e il nastro di stato, le regole di transizione e le varie azioni che aggiornano il nastro.

Ciò che ci manca è un nastro di stato e regole che dicono ai musicisti come rispondere ai simboli sul nastro e come aggiornare quel nastro.

In un certo senso, i rumori che scorrono nell'aria potrebbero essere il nastro di stato. Ma. Non esiste un modo semplice per riavvolgere il nastro. Questa mancanza di riavvolgimento significa che l'esecutore dovrebbe mantenere un "nastro" privato di qualche tipo.

Questo ottiene fuori la notazione musicale e in alcune altre istruzioni extra-musicali per il performer.

Gran parte della notazione è aperta all'interpretazione e le istruzioni del linguaggio naturale sono un aspetto accettato della notazione musicale - e sono state durante la maggior parte se non tutta la storia della musica occidentale notata.

Fermatas per definizione dipendono dalla discrezionalità dell'esecutore, il che significa che dipenderebbe dal loro stato, che è quasi sempre alterato dalla musica in congiunzione con fattori esterni - quindi questo solleva alcune domande sulla natura apolidia della notazione musicale.

Canon a 2 per Tonus dell'offerta musicale di Bach è un brano infinitamente loop la cui tonalità sale di un intero gradino ogni volta fino a quando il brano viene eseguito.

Più di recente, è comune vedere istruzioni come "ripetere per ogni solista" in, ad esempio, versioni notate di brani jazz come " Prendi cinque .

Detto questo, a parte gli aspetti intrinsecamente arbitrari come la fermata, come le altre risposte, la notazione musicale con nient'altro che i simboli generali probabilmente non è completa Turing.

Non è correlato alle lingue complete di Turing in quanto è un linguaggio descrittivo. Non ci sono comandi in termini di calcolo o modifica dei dati, nessuno stato, nessun input, nessun output eccetto per il risultato della descrizione stessa.

Inoltre non ci sono salti condizionali a seconda dell'input. Quando risolvi tutti i salti ottieni una struttura lineare, non un albero. Quindi tutti i "programmi" che possono essere modellati da questo linguaggio sono lineari senza loop o salti.