Czy zapis nutowy Turinga jest kompletny?

63

Zastanawiam się, czy język notacji muzycznej Turing-Complete ?

Moją pierwszą myślą jest to, że w notacji muzycznej występują pętle, ale nie ma sposobu na napisanie gałęzi warunkowych, prawda?

Nie jestem muzykiem, więc może ktoś może pomóc wypełnić luki?

Klaim
źródło
7
jaki jest język partycji muzycznych ? jakaś forma zapisu muzycznego ?
komar
4
Nie wiem dużo o notacji muzycznej: czy możesz w jakiś sposób zakodować nieograniczoną liczbę „zmiennych zmiennych” (lub „taśmy”)? W przeciwnym razie nie widzę, jak mogłoby być kompletnie.
nikie
nie, nie robi
shabunc
@nikie Nie jestem pewien, czy refren działa jako funkcja przechowywana czy coś podobnego ...
Klaim
2
Oczywiście jest to kompletny Turing, wystarczy użyć 8 różnych nut do przedstawienia 8 znaków Brainfuck. :)
Chris Burt-Brown

Odpowiedzi:

37

Tak, jeśli przyznasz się do kilku instrukcji dotyczących transpozycji - niezbyt często, ale nie jest to nieznane.

Następnie możesz zinterpretować utwór jako Choon , który jest kompletny w Turinga. Wykonawca jest pamięcią: muszą pamiętać liczbę nut, o które dany utwór jest obecnie transponowany, i wszystkie nuty, które do tej pory grały. Oczywiście jest to wykonalne tylko dla komputera, a może i uczonego.

Z podręcznika Choon:

  • Transpozycje

    Istnieją trzy instrukcje transpozycji: up ( +), down ( -) i cancel ( .). Instrukcja transpozycji transponuje wszystkie kolejne nuty grane o ilość ostatnio granych nut. Instrukcja cancel ( .) ustawia transpozycję z powrotem na zero.

    Transpozycje są kumulatywne, więc kod Choon do transpozycji przyszłych notatek o 2 to b+, a o 4 to b++. Ponadto zastosowana wartość jest wartością poprzedniej nuty po zastosowaniu b+b+transpozycji , więc transponuje przyszłe nuty o 6, a nie o 4.

  • John Cage

    Instrukcja John Cage ( %) powoduje wyciszenie jednej nuty w strumieniu wyjściowym. Wartość transpozycji Johna Cage'a wynosi zero - %-i %+nie ma żadnych operacji (z wyjątkiem tego, że do wyjścia dodawana jest pojedyncza cisza).

  • Powtórz paski

    Instrukcje powtarzania pasków ( ||:i :||) zawierają pętlę. Pętla zostanie wykonana tyle razy, ile wskazuje ostatnia nuta zagrana przed ||:napotkaniem. Wartość zerowa lub ujemna będzie oznaczać, że Choon natychmiast przejdzie do gry od dopasowania :||. John Cage oznacza powtarzanie na zawsze - %||::||jest nieskończoną pętlą.

  • Kamerton

    Instrukcja kamertonu ~zapewnia sposób na wyrwanie się z pętli. Jeśli w pętli napotkany jest kamerton, a ostatnio grana nuta była nutą wartościową A, Choon natychmiast skacze, aby zacząć grać od następnej :||instrukcji. Jeśli nie ma dalszych :||instrukcji (znaczenie ~zostało użyte poza powtarzającymi się słupkami), wydajność natychmiast się zakończy.

  • Markery

    Markery zapewniają cudowną wygodę programowania. Znacznik to mała litera lub słowo, które zapamiętuje punkt w strumieniu wyjściowym. Odwołanie się do znacznika (patrz poniżej) spowoduje, że nuta zagrana po wystąpieniu znacznika będzie ponownie odtworzona. Pamiętaj, że transpozycje wpłyną na tę nowo odtwarzaną nutę.

    Jeżeli dwa lub więcej znaczników występuje kolejno lub znacznik postępuje zgodnie z instrukcją odtwarzania od znacznika, należy je oddzielić białymi spacjami.

  • Graj z wyjścia

    Instrukcja Play From Output ( =) pozwala ponownie odtworzyć nuty, które zostały już odtworzone w strumieniu wyjściowym. Można odwołać się do dodatkowej liczby - 5th nuta zagrana ponieważ program rozpoczął byłoby =5, według liczby względnej - 3rd najnowsza notatka będzie grał =-3lub markera - nuta zagrana po marker xbędzie =x.

    Jest to wspólny idiom, aby ponownie użyć znacznika i natychmiast potem odwoływać się do niego w ten sposób: x=x. Jest to podobne do powiedzenia x=x+yw tradycyjnym języku programowania (gdzie yreprezentuje aktualnie skuteczną wartość transpozycji).

John Cage jest tylko odpoczynek , o Kamerton jest (w przybliżeniu) dal segno, a znacznik jest segno. Przypuszczam, że kamerton może być odtwarzany przez dodatkowego wykonawcę, na który główny wykonawca odpowiada, ale zasada jest taka sama.

Jon Purdy
źródło
1
Powiedziałbym, że to najlepsza odpowiedź na pytanie: żadna z pozostałych odpowiedzi nie dowodzi, że notacja muzyczna nie jest kompletna w Turingu.
K.Steff
24

Kompletność Turinga wymaga co najmniej trzech rzeczy: nieskończonej pętli, skoku warunkowego (jeśli-to) i sposobu przechowywania wyników obliczeń w pamięci. Nawet jeśli notacja muzyczna zawierała skoki warunkowe, nie ma stanu, więc nie, nie jest kompletna w Turingu.

Mason Wheeler
źródło
13
To jakby skoki warunkowe, używane w połączeniu ze znakami powtarzania: „przy pierwszym powtórzeniu zagraj tę część, przy drugim powtórzeniu zagraj tę część”. Licznik powtórzeń (który trzymasz w głowie podczas gry) to stan. Ale tak naprawdę nie ma nieskończonej taśmy zawierającej stan.
Jesper
49
Ciekawostka: rachunek Lambda nie ma pętli, skoku warunkowego i nie ma sposobu na zapisanie wyników obliczeń gdzieś w pamięci. A jednak jest już kompletnie ;-)
nikie
11
@Nikie: Nie myl abstrakcji z rzeczywistością. Rachunek Lambda ma koncepcję oceny warunkowej, rekurencja służy zarówno do zapętlania, jak i przeskakiwania, a stan jest obliczany jako wyniki oceny wyrażeń. Istnieją koncepcje; są po prostu zaimplementowane w zupełnie inny sposób niż prawdziwe programowanie komputerowe.
Mason Wheeler
5
@MasonWheeler: LC nie ma podstawowych pojęć dotyczących pętli, stanów i warunków warunkowych, ale można uzyskać rzeczy, które służą podobnemu celowi. To tylko kolejny sposób na stwierdzenie, że Turing jest kompletny. Pytanie nie brzmi: czy w zapisie muzycznym są te pojęcia, ale: czy można je jakoś wyprowadzić? Po prostu twierdziłeś, że nie możesz bez dowodu. (Zgadzam się z twoją konkluzją, po prostu nie sądzę, żeby twoje rozumowanie było prawidłowe.)
nikie
9
@MasonWheeler: Rachunek lambda to prawdziwe programowanie komputerowe.
dan_waterworth
23

Standardowym dowodem kompletności języka jest napisanie maszyny Turinga w tym języku. Dowodzi to, że istnieje równoważność między językiem (zwykle podzbiorem języka) a maszyną Turinga.

Pojęcie „notacji muzycznej” jest nieco śliskie. Stosuje się wiele znormalizowanego grawerowania. Jednak. Są kompozytorzy pchający koperty, którzy piszą na papierze wszelkiego rodzaju szalone rzeczy.

Udawajmy, że chcesz się skoncentrować na podzbiorze notacji muzycznej, który jest uważany za wystarczająco standardowy, aby być częścią Finale lub Sibeliusa lub jakiegoś zestawu narzędzi do grawerowania głównego strumienia.

Więc.

W Pythonie (lub C lub cokolwiek) definiujesz symbole, taśmę, reguły przejścia i różne akcje, które aktualizują taśmę, aby odzwierciedlić zmianę stanu i ruch taśmy, odczytywanie i zapisywanie symboli na taśmie.

Za pomocą „notacji muzycznej” musimy zdefiniować symbole i stanową taśmę, reguły przejścia i różne działania, które aktualizują taśmę.

Brakuje nam stanowej taśmy i zasad, które mówią muzykom, jak reagować na symbole na taśmie i jak ją aktualizować.

W pewnym sensie odgłosy płynące w powietrzu mogą być stanową taśmą. Ale. Nie ma łatwego sposobu przewinięcia taśmy do tyłu. Ten brak przewijania oznacza, że ​​wykonawca musiałby zachować jakąś prywatną „taśmę”.

To wychodzi poza notację muzyczną i inne instrukcje pozamuzyczne dla wykonawcy.

S.Lott
źródło
Cóż, tak naprawdę nie możesz przewinąć uruchomionego programu, albo ... (Ale tak, rozumiem, co masz na myśli o aktualizacji stanu, ale czy to z kolei może być językiem funkcjonalnym?)
Izkata
2
Nie przewijasz programu. Przewijasz taśmę. Chodzi o to, że taśma Turinga ma wszystkie dostępne pozycje. Jest to „pamięć o dostępie swobodnym” uproszczona do czasu liniowego z ruchami do przodu i do tyłu.
S.Lott,
Ohhh, pamiętam to teraz, przepraszam. Myślałem o „taśmie” jako o tym, z czego muzyka została napisana z jakiegoś powodu =)
Izkata
Zbudowanie maszyny Turinga jest standardowym sposobem udowodnienia, że ​​Turing jest ukończony, ale odwrotność nie jest prawdą - po prostu dlatego, że nie możesz dowiedzieć się, jak zbudować maszynę Turinga, nie oznacza, że ​​coś nie jest kompletne. Maszyna Turinga (z taśmą i wszystkim) jest po prostu arbitralną abstrakcją, która ma wystarczającą moc obliczeniową; istnieją inne abstrakcje równie potężne, bez pojęcia taśm. Spójrz na rachunek lambda, rachunek SKI lub niektóre języki ezoteryczne (Fractran jest fajny).
Tikhon Jelvis
3

Znaczna część notacji jest otwarta na interpretację, a instrukcje w języku naturalnym są akceptowanym aspektem notacji muzycznej - i były obecne w większości, jeśli nie w całej historii zachodniej muzyki notowanej.

Fermaty z definicji zależą od dyskrecji wykonawcy, co oznacza, że ​​zależałoby to od ich własnego stanu, który prawie zawsze zmienia muzyka w powiązaniu z czynnikami zewnętrznymi - rodzi to więc pewne pytania dotyczące bezpaństwowości zapisu muzycznego.

Kanon 2 na Tonus z Muzycznej Oferty Bacha to utwór o nieskończonej pętli, którego tonacja wzrasta za każdym razem o krok, o ile utwór jest wykonywany.

Ostatnio często zdarza się, że instrukcje, takie jak „powtórz dla każdego solisty”, na przykład w notowanych wersjach utworów jazzowych, takich jak Take Five Dave'a Brubecka .

To powiedziawszy, oprócz z natury arbitralnych aspektów, takich jak fermata, jak twierdzą inne odpowiedzi, notacja muzyczna zawierająca tylko ogólne symbole prawdopodobnie nie jest kompletna.

Rei Miyasaka
źródło
1

Nie jest związany z kompletnymi językami Turinga, ponieważ jest językiem opisowym. Nie ma żadnych poleceń w zakresie obliczania lub modyfikacji danych, żadnych stanów, żadnych danych wejściowych, danych wyjściowych, z wyjątkiem wyniku samego opisu.

Ponadto nie ma żadnych skoków warunkowych w zależności od danych wejściowych. Po wykonaniu wszystkich skoków otrzymujesz strukturę liniową, a nie drzewo. Zatem wszystkie „programy”, które można modelować za pomocą tego języka, są liniowe bez żadnych pętli ani skoków.

Mononessa
źródło
1
To, co wymieniłeś, nie jest konieczne dla pełnego języka Turinga. Rachunek lambda ma tylko aplikacje, zmienne i lambda (np. Brak pętli, stanów lub poleceń), ale Turing jest gotowy. To samo dotyczy szeregu innych modeli obliczeniowych, takich jak kombinatory SKI.
Tikhon Jelvis