Музыкальная нотация Turing-Complete?

63

Мне интересно, является ли язык музыкальной нотации Turing-Complete ?

Моя первая мысль: в музыкальной нотации есть петли, но нет способа написать условные ветки, верно?

Я не музыкант, так что, возможно, кто-то может помочь заполнить пробелы?

Klaim
источник
7
что такое язык музыкальных разделов ? какая-то форма нотной записи ?
комнат
4
Я не очень разбираюсь в музыкальной нотации: можете ли вы каким-то образом кодировать неограниченное количество «изменяемых переменных» (или «ленты»)? В противном случае, я не понимаю, как это может быть завершено.
nikie
нет, это не так
шабун
@nikie Я не уверен, что рефрен действует как хранимая функция или что-то подобное ...
Klaim
2
Конечно, он завершен по Тьюрингу, просто используйте 8 разных заметок, чтобы представить 8 символов Brainfuck. :)
Крис Бурт-Браун

Ответы:

37

Да, если вы принимаете несколько инструкций для транспонирования - редко, но не неизвестно.

Затем вы можете интерпретировать пьесу как Чун , которая завершена по Тьюрингу. Исполнитель - это память: он должен помнить количество нот, на которые в данный момент транспонируется пьеса, и все ноты, которые он сыграл до сих пор. Очевидно, что это возможно только для компьютера или, возможно, ученого.

Из руководства Choon:

  • транспозиций

    Существует три инструкции транспонирования: вверх ( +), вниз ( -) и отмена ( .). Инструкция транспонирования транспонирует все последующие ноты, сыгранные на сумму последней сыгранной ноты. Инструкция отмены ( .) возвращает транспонирование в ноль.

    Транспозиции являются кумулятивными, поэтому код Чуна для транспонирования будущих заметок вверх на 2 равен b+, а на 4 будет b++. Кроме того, используемым значением является значение предыдущей заметки после применения транспонирования, поэтому b+b+транспонирует будущие заметки вверх на 6, а не на 4.

  • Джон Кейдж

    Инструкция John Cage ( %) вызывает молчание в одну ноту в выходном потоке. Значение транспонирования John Cage равно нулю %-и %+не имеет значения (за исключением того, что к выходу добавляется единичная пауза).

  • Повторите Бары

    Инструкции Repeat Bars ( ||:и :||) заключают в себя цикл. Цикл будет исполняться столько раз, сколько указано самой последней нотой, сыгранной до того, как ||:была обнаружена. Нулевое или отрицательное значение будет означать, что Чон немедленно прыгнет, чтобы начать игру с соответствия :||. Джон Кейдж означает повторение навсегда - %||::||это бесконечный цикл.

  • Камертон

    Инструкция Tuning Fork ~предоставляет способ вырваться из петель. Если в цикле встречается камертон, а последняя сыгранная нота была ценной нотой A, то Чун немедленно перейдет к началу воспроизведения после следующей :||инструкции. Если дальнейших :||инструкций нет (значение ~было использовано вне каких-либо повторяющихся полос), исполнение немедленно прекращается.

  • Маркеры

    Маркеры обеспечивают изумительное удобство программирования. Маркер - это строчная буква или слово, которое запоминает точку в потоке вывода. Обращение к маркеру (см. Ниже) приведет к тому, что нота, сыгранная после появления маркера, будет воспроизведена снова. Обратите внимание, что транспонирование повлияет на эту вновь сыгранную ноту.

    Если два или более маркеров появляются последовательно или маркер следует инструкции воспроизведения из маркера, они должны быть разделены пробелами.

  • Воспроизвести с выхода

    Инструкция «Воспроизвести с выхода» ( =) позволяет снова воспроизводить ноты, которые уже были воспроизведены в выходном потоке. Вы можете обратиться к примечаниям по номеру - 5 - й сыгранной ноты , так как программа началась бы =5, по относительному числу - 3 - е самая последняя нота будет =-3или маркером - сыгранная нота после маркера xбудет =x.

    Это общая идиома повторно использовать маркер и немедленно после этого обратиться к нему, как это: x=x. Это похоже на x=x+yобщепринятый язык программирования (где yпредставляет текущее эффективное значение транспонирования).

Джон Кейдж просто отдых , камертон это (примерно) Dal Segno и маркер является Segno. Я предполагаю, что камертон мог сыграть дополнительный исполнитель, которому отвечает основной исполнитель, но принцип тот же.

Джон Перди
источник
1
Я бы сказал, что это лучший ответ на вопрос: ни один из других ответов не доказывает, что музыкальная запись не является полной по Тьюрингу.
К.Стефф
24

Полнота Тьюринга требует, как минимум, трех вещей: бесконечный цикл, условный переход (если-затем) и способ хранения результатов вычислений где-то в памяти. Даже если в музыкальной нотации были условные переходы, у нее нет состояния, поэтому нет, она не завершена по Тьюрингу.

Мейсон Уилер
источник
13
Это своего рода условные переходы, используемые в сочетании с признаками повтора: «на первом повторе сыграйте эту часть, на втором повторе сыграйте эту часть». Счетчик повторений (который вы держите в голове во время игры) - это состояние. Но у него действительно нет бесконечной ленты, содержащей состояние.
Джеспер
49
Забавный факт: в лямбда-исчислении нет циклов, условных переходов и нет возможности хранить результаты вычислений где-то в памяти. И все же он завершен ;-)
nikie
11
@Nikie: не путайте абстракции с реальностями. Лямбда-исчисление имеет концепцию условной оценки, рекурсия используется как для циклических, так и для прыжковых операций, а состояние вычисляется как результат оценки выражений. Концепции есть; они просто реализованы совсем не так, как настоящие компьютерные программы.
Мейсон Уилер
5
@MasonWheeler: LC не имеет фундаментальных концепций циклов, состояний и условных выражений, но вы можете получить вещи, которые служат аналогичной цели. Это просто еще один способ сказать, что Тьюринг завершен. Таким образом, вопрос не в том, есть ли в музыкальной нотации эти понятия, а в том, можете ли вы их как-то получить? Вы просто утверждали, что не можете, без доказательств. (Я согласен с твоим заключением, я просто не думаю, что твои рассуждения верны.)
nikie
9
@MasonWheeler: лямбда-исчисление - это настоящее компьютерное программирование.
dan_waterworth
23

Стандартным доказательством того, что язык является полным по Тьюрингу, является написание машины Тьюринга на этом языке. Это доказывает, что существует эквивалент между языком (обычно подмножеством языка) и машиной Тьюринга.

Понятие «Музыкальная нотация» немного скользкое. Существует много стандартизированной гравировки, которая используется. Тем не мение. Есть композиторы, которые толкают конверты и пишут на бумаге все сумасшедшие вещи.

Давайте представим, что вы хотите сосредоточиться на подмножестве музыкальных обозначений, которое считается достаточно стандартным, чтобы быть частью Finale или Sibelius или некоторого основного набора инструментов для гравировки.

Так.

Для Python (или C или любого другого) вы определяете символы, ленту, правила перехода и различные действия, которые обновляют ленту для отражения изменения состояния и движения ленты, чтения и записи символов на ленте.

Используя «Музыкальную нотацию», мы должны определить символы и ленту с состоянием, правила перехода и различные действия, которые обновляют ленту.

Нам не хватает ленты состояния и правил, которые сообщают музыкантам, как реагировать на символы на ленте и как ее обновлять.

В некотором смысле шумы, распространяющиеся в воздухе, могут быть записью состояния. Но. Нет простого способа перемотать ленту. Отсутствие перемотки означает, что исполнителю придется хранить какую-то частную «ленту».

Это выходит за рамки музыкальной нотации и некоторых других дополнительных музыкальных инструкций для исполнителя.

С. Лотт
источник
Ну, вы также не можете перемотать запущенную программу ... (Но да, я понимаю, что вы имеете в виду при обновлении состояния, но может ли это, в свою очередь, быть функциональным языком?)
Изката
2
Вы не перематываете программу. Вы перематываете ленту Дело в том, что лента Тьюринга имеет все доступные позиции. Это «Память произвольного доступа», упрощенная до линейного времени с движениями вперед и назад
S.Lott
Оооо, я помню это сейчас, извините. Я думал о «ленте» как о том, что музыка была написана по какой-то причине =)
Izkata
Построение машины Тьюринга является стандартным способом доказать, что что-то является полным по Тьюрингу, но обратное неверно - просто потому, что вы не можете понять, как построить машину Тьюринга, не означает, что что-то не является полным по Тьюрингу. Машина Тьюринга (с лентой и всем) - это произвольная абстракция, обладающая достаточной вычислительной мощностью; Есть и другие абстракции, такие же мощные, без понятия о лентах. Взгляните на лямбда-исчисление, SKI-исчисление или некоторые эзотерические языки (Fractran это круто).
Тихон Джелвис
3

Большая часть нотации открыта для интерпретации, и инструкции на естественном языке являются принятым аспектом музыкальной нотации - и были на протяжении большей части, если не всей истории западной нотной музыки.

Fermatas по определению зависят от усмотрения исполнителя, что означает, что это будет зависеть от их собственного состояния, которое почти всегда изменяется музыкой в ​​сочетании с внешними факторами - так что возникает ряд вопросов о природе музыкальной нотации без состояния.

Canon a 2 per Tonus из музыкального предложения Баха представляет собой пьесу с бесконечной петлей, тональность которой увеличивается на целый шаг каждый раз до тех пор, пока исполняется пьеса.

Совсем недавно стали встречаться такие инструкции, как «повторить для каждого солиста», например, в нотных версиях джазовых произведений, таких как «Дайв Брубек», « Take Five» .

Тем не менее, помимо произвольно произвольных аспектов, таких как fermata, как утверждают другие ответы, музыкальная нотация только с общими символами, вероятно, не завершена по Тьюрингу.

Рей Миясака
источник
1

Это не относится к полным языкам Тьюринга, так как это описательный язык. Здесь нет команд с точки зрения расчета или изменения данных, нет состояний, нет ввода, нет вывода, кроме результата самого описания.

Также нет условных переходов в зависимости от входа. Когда вы решаете все прыжки, вы получаете линейную структуру, а не дерево. Таким образом, все «программы», которые могут моделироваться этим языком, являются линейными без каких-либо циклов или скачков вообще.

Mononess
источник
1
То, что вы перечислили, не обязательно для полного языка Тьюринга. Лямбда-исчисление имеет только приложения, переменные и лямбда-выражения (например, без циклов, состояний или команд), но является полным по Тьюрингу. То же самое касается множества других моделей вычислений, таких как комбинаторы SKI.
Тихон Джелвис