Ist die Notenschrift Turing-Complete?

63

Ich frage mich, ist Notationssprache Turing-Complete ?

Mein erster Gedanke ist, dass es Loops in der Notenschrift gibt, aber es gibt keine Möglichkeit, bedingte Zweige zu schreiben, oder?

Ich bin kein Musiker, also kann vielleicht jemand helfen, die Lücken zu füllen?

Klaim
quelle
7
Was ist Musikpartitionssprache ? irgendeine Form von Notenschrift ?
gnat
4
Ich weiß nicht viel über Musiknotation: Können Sie irgendwie eine unbegrenzte Anzahl von "veränderlichen Variablen" (oder "Band") codieren? Ansonsten sehe ich nicht, wie es vollständig sein könnte.
Nikie
Nein, das tut es nicht
Shabunc
@nikie Ich bin mir nicht sicher, ob ein Refrain als gespeicherte Funktion oder ähnliches fungiert ...
Klaim
2
Natürlich ist es Turing-komplett, verwenden Sie einfach 8 verschiedene Noten, um die 8 Charaktere von Brainfuck darzustellen. :)
Chris Burt-Brown

Antworten:

37

Ja, wenn Sie ein paar Anweisungen zur Umsetzung zugeben - ungewöhnlich, aber nicht unbekannt.

Sie können ein Stück dann als Choon interpretieren , was Turing-complete ist. Der Interpret ist die Erinnerung: Er muss sich die Anzahl der Noten merken, um die das Stück gerade transponiert ist, und alle Noten, die er bisher gespielt hat. Offensichtlich ist es nur für einen Computer oder vielleicht einen Gelehrten machbar.

Aus dem Choon-Handbuch:

  • Transpositionen

    Es gibt drei Transpositionsbefehle: up ( +), down ( -) und cancel ( .). Eine Transpositionsanweisung transponiert alle nachfolgenden gespielten Noten um den Betrag der zuletzt gespielten Note. Die Cancel-Anweisung ( .) setzt die Transposition auf Null zurück.

    Transponierungen sind kumulativ, so dass der Choon-Code, um zukünftige Noten zu transponieren, 2-mal höher ist b+und 4-mal höher wäre b++. Der verwendete Wert ist auch der Wert der vorherigen Note, nachdem die Transpositionen angewendet wurden, sodass b+b+zukünftige Noten um 6 und nicht um 4 transponiert werden.

  • John Cage

    Der John Cage-Befehl ( %) bewirkt eine Stille von einer Note im Ausgabestream. Der Transpositionswert eines John Cage ist Null - %-und %+es handelt sich um No-Ops (mit der Ausnahme, dass der Ausgabe eine einzelne Stille hinzugefügt wird).

  • Wiederholen Sie Bars

    Die Repeat Bars-Anweisungen ( ||:und :||) schließen eine Schleife ein. Die Schleife wird so oft ausgeführt, wie es die zuletzt gespielte Note angibt, bevor sie ||:angetroffen wurde. Eine Null oder ein negativer Wert bedeutet, dass Choon sofort springt, um mit dem Matching zu beginnen :||. Ein John Cage bedeutet immer wiederholen - %||::||ist eine Endlosschleife.

  • Stimmgabel

    Die Tuning Fork-Anweisung ~bietet eine Möglichkeit, aus Loops auszubrechen. Wenn eine Stimmgabel in einem Loop angetroffen wird und die zuletzt gespielte Note eine AWertnote war, springt Choon sofort nach der nächsten :||Anweisung zum Spielstart. Wenn es keine weiteren :||Anweisungen gibt (die Bedeutung ~wurde außerhalb von Wiederholungsbalken verwendet), wird die Aufführung sofort beendet.

  • Marker

    Markierungen bieten einen hervorragenden Programmierkomfort. Ein Marker ist ein Kleinbuchstabe oder ein Wort, das sich an einen Punkt im Ausgabestream erinnert. Wenn Sie auf einen Marker verweisen (siehe unten), wird die Note, die nach dem erneuten Spielen des Markers gespielt wurde, erneut abgespielt. Beachten Sie, dass Transpositionen diese neu gespielte Note beeinflussen.

    Treten zwei oder mehr Marker nacheinander auf oder folgt ein Marker einer Play-from-Marker-Anweisung, müssen sie durch Leerzeichen getrennt werden.

  • Wiedergabe vom Ausgang

    Mit der Anweisung Play From Output ( =) können Sie Noten, die bereits im Ausgabestream abgespielt wurden, erneut abspielen. Sie können sich auf die Noten nach der Nummer beziehen - die 5. gespielte Note seit Beginn des Programms wäre =5, nach der relativen Nummer - die 3. zuletzt gespielte Note wäre =-3oder nach dem Marker - die Note wäre, die nach dem Marker gespielt xwird =x.

    Es ist ein gemeinsames Idiom eine Markierung wieder zu verwenden und dann sofort beziehen sich darauf, wie folgt aus : x=x. Dies ist vergleichbar mit x=x+yeiner herkömmlichen Programmiersprache (wobei yder aktuell wirksame Transpositionswert dargestellt wird).

Ein John Cage ist nur eine Pause , eine Stimmgabel ist (ungefähr) ein Segno und ein Marker ist ein Segno. Ich nehme an, die Stimmgabel könnte von einem zusätzlichen Interpreten gespielt werden, auf den der Hauptinterprete reagiert, aber das Prinzip ist dasselbe.

Jon Purdy
quelle
1
Ich würde sagen, dies ist die beste Antwort auf die Frage: Keine der anderen Antworten beweist, dass die Notenschrift nicht vollständig ist.
K.Steff
24

Um die Vollständigkeit zu gewährleisten, sind mindestens drei Dinge erforderlich: eine Endlosschleife, ein bedingter Sprung (if-then) und eine Möglichkeit, die Ergebnisse von Berechnungen irgendwo im Speicher abzulegen. Selbst wenn die Notenschrift bedingte Sprünge hatte, hat sie keinen Zustand, also nein, sie ist nicht Turing-vollständig.

Mason Wheeler
quelle
13
Es verfügt über bedingte Sprünge, die in Kombination mit Wiederholungszeichen verwendet werden: "Bei der ersten Wiederholung spielen Sie diesen Teil, bei der zweiten Wiederholung spielen Sie diesen Teil". Der Wiederholungszähler (den Sie beim Spielen im Kopf halten würden) lautet state. Aber es hat in der Tat kein endloses Band, das den Status enthält.
Jesper,
49
Unterhaltsame Tatsache: Lambda-Kalkül hat keine Schleifen, keinen bedingten Sprung und keine Möglichkeit, Berechnungsergebnisse irgendwo im Speicher zu speichern.
Trotzdem
11
@ Nikie: Verwechsle Abstraktionen nicht mit Realitäten. Der Lambda-Kalkül hat ein Konzept der bedingten Auswertung, die Rekursion wird sowohl für das Schleifen als auch für das Springen verwendet, und der Zustand wird als Ergebnis der Auswertung von Ausdrücken berechnet. Die Konzepte sind da; Sie werden nur auf eine ganz andere Art und Weise als echte Computerprogrammierung implementiert.
Mason Wheeler
5
@ MasonWheeler: LC hat keine grundlegenden Konzepte für Schleifen, Status und Bedingungen, aber Sie können Dinge ableiten, die einem ähnlichen Zweck dienen. Das ist nur eine andere Art zu sagen, dass Turing vollständig ist. Die Frage ist also nicht: Hat die Musiknotation diese Konzepte, sondern: Können Sie sie irgendwie herleiten? Sie haben einfach behauptet, dass Sie ohne Beweise nicht können. (Ich stimme Ihrer Schlussfolgerung zu, ich glaube nur nicht, dass Ihre Argumentation gültig ist.)
Nikie
9
@ MasonWheeler: Lambda-Kalkül ist echte Computerprogrammierung.
Dan_waterworth
23

Der Standardnachweis für die Vollständigkeit einer Sprache in Turing besteht darin, eine Turing-Maschine in dieser Sprache zu schreiben. Dies beweist, dass es eine Äquivalenz zwischen der Sprache (normalerweise eine Teilmenge der Sprache) und der Turing-Maschine gibt.

Der Begriff "Musikalische Notation" ist etwas rutschig. Es wird viel standardisierte Gravur verwendet. Jedoch. Es gibt umschlagdrückende Komponisten, die alle möglichen verrückten Sachen auf Papier schreiben.

Nehmen wir an, Sie möchten sich auf die Teilmenge der Musiknotation konzentrieren, die als Standard für Finale, Sibelius oder andere gängige Gravurwerkzeuge gilt.

Damit.

Für Python (oder C oder was auch immer) definieren Sie die Symbole, das Band, die Übergangsregeln und die verschiedenen Aktionen, mit denen das Band aktualisiert wird, um Statusänderungen und Bandbewegungen widerzuspiegeln. Sie lesen und schreiben Symbole auf das Band.

Mit "Musiknotation" müssen wir Symbole und das zustandsbehaftete Band, die Übergangsregeln und die verschiedenen Aktionen definieren, die das Band aktualisieren.

Was uns fehlt, sind ein statusbehaftetes Band und Regeln, die den Musikern mitteilen, wie sie auf Symbole auf dem Band reagieren und wie sie dieses Band aktualisieren.

In gewissem Sinne könnten die Geräusche, die in der Luft herumfließen, das zustandsbehaftete Band sein. Aber. Es gibt keine einfache Möglichkeit, das Band zurückzuspulen. Dieser Mangel an Zurückspulen bedeutet, dass der Darsteller eine Art privates "Band" aufbewahren müsste.

Dies gelangt außerhalb der Notenschrift und in einige andere außermusikalische Anweisungen an den Interpreten.

S.Lott
quelle
Nun, Sie können ein laufendes Programm auch nicht wirklich zurückspulen ... (Aber ja, ich verstehe, was Sie mit dem Aktualisieren des Status meinen, aber könnte das wiederum eine funktionierende Sprache sein?)
Izkata
2
Sie spulen das Programm nicht zurück. Sie spulen das Band zurück. Der Punkt ist, dass das Turing-Band alle Positionen zugänglich hat. Es ist "Direktzugriffsspeicher", vereinfacht zu einer linearen Zeit mit Vorwärts- und Rückwärtsbewegungen.
S.Lott
Ohhh, ich erinnere mich jetzt, sorry. Ich dachte an "Tape" als das, worauf die Musik aus irgendeinem Grund geschrieben wurde =)
Izkata
Der Bau einer Turing-Maschine ist die Standardmethode, um zu beweisen, dass etwas vollständig ist. Das Gegenteil ist jedoch nicht der Fall. Nur weil Sie nicht herausfinden können, wie eine Turing-Maschine gebaut wird, bedeutet dies nicht, dass etwas nicht vollständig ist. Eine Turing-Maschine (mit einem Band und allem) ist nur eine willkürliche Abstraktion, die über genügend Rechenleistung verfügt. es gibt andere Abstraktionen, die ebenso mächtig sind und keine Vorstellung von Bändern haben. Werfen Sie einen Blick auf Lambda-Kalkül, SKI-Kalkül oder einige esoterische Sprachen (Fractran ist cool).
Tikhon Jelvis
3

Ein Großteil der Notation ist offen für Interpretationen, und Anweisungen in natürlicher Sprache sind ein anerkannter Aspekt der Musiknotation - und waren in den meisten, wenn nicht in der gesamten Geschichte der westlichen notierten Musik zu finden.

Fermaten hängen per definitionem vom Ermessen des Interpreten ab, was bedeutet, dass es von seinem eigenen Zustand abhängt, der fast immer durch die Musik in Verbindung mit externen Faktoren verändert wird - dies wirft also einige Fragen zur Staatenlosigkeit der Musiknotation auf.

Canon a 2 per Tonus aus Bachs musikalischem Angebot ist ein Stück in einer Endlosschleife, dessen Tonalität sich jedes Mal um einen Schritt erhöht, solange das Stück aufgeführt wird.

In jüngerer Zeit ist es üblich, Anweisungen wie "Wiederholung für jeden Solisten" in notierten Versionen von Jazzstücken wie Dave Brubecks Take Five zu sehen .

Abgesehen von inhärent willkürlichen Aspekten wie den Fermaten, wie die anderen Antworten besagen, ist die Musiknotation mit nichts als den allgemeinen Symbolen wahrscheinlich nicht vollständig.

Rei Miyasaka
quelle
1

Es hat nichts mit Turing complete languages ​​zu tun, da es sich um eine beschreibende Sprache handelt. Es gibt keine Befehle zum Berechnen oder Ändern von Daten, keine Zustände, keine Eingaben, keine Ausgaben außer dem Ergebnis der Beschreibung.

Abhängig vom Eingang gibt es auch keine bedingten Sprünge. Wenn Sie alle Sprünge auflösen, erhalten Sie eine lineare Struktur, keinen Baum. Alle "Programme", die mit dieser Sprache modelliert werden können, sind also linear ohne irgendwelche Schleifen oder Sprünge.

Mononess
quelle
1
Was Sie aufgelistet haben, ist für eine vollständige Sprache von Turing nicht erforderlich. Die Lambda-Rechnung enthält nur Anwendungen, Variablen und Lambdas (z. B. keine Schleifen, Zustände oder Befehle), ist aber vollständig. Gleiches gilt für eine Reihe anderer Berechnungsmodelle wie SKI-Kombinatoren.
Tikhon Jelvis