¿La notación musical es Turing-Complete?

Sí, si admite algunas instrucciones para la transposición, poco frecuentes pero no desconocidas.

Luego puedes interpretar una pieza como Choon , que es Turing-complete. El intérprete es la memoria: deben recordar el número de notas con las que se transpone actualmente la pieza y todas las notas que han tocado hasta ahora. Obviamente, solo es factible para una computadora, o quizás para un experto.

Del manual de Choon:

  

• Transposiciones

       

  Hay tres instrucciones de transposición, arriba ( + ), abajo ( - ) y cancelar ( . ). Una instrucción de transposición transpone todas las notas posteriores tocadas por la cantidad de la última nota tocada. La instrucción de cancelación ( . ) establece la transposición de nuevo a cero.

       

  Las transposiciones son acumulativas, por lo que el código de Choon para transponer las notas futuras un 2% es b+ y un 4% sería b++ . Además, el valor utilizado es el valor de la nota anterior después de que se hayan aplicado las transposiciones, por lo que b+b+ transpone las notas futuras hasta en 6, no en 4.

  

• John Cage

       

  La instrucción John Cage ( % ) provoca un silencio de una nota en el flujo de salida. El valor de transposición de una jaula John es cero: %- y %+ no son ops (excepto que se agrega un solo silencio a la salida).

  

• Barras de repetición

       

  Las instrucciones de barras de repetición ( ||: y :|| ) encierran un bucle. El bucle ejecutará el número de veces indicado por la nota más reciente tocada antes de que se encuentre el ||: . Un valor cero o negativo significará que Choon saltará inmediatamente para comenzar a jugar desde el correspondiente :|| . Una jaula de John significa repetir para siempre: %||::|| es un bucle infinito.

  

• Horquilla de ajuste

       

  La instrucción Tuning Fork ~ proporciona una manera de romper los bucles. Si se encuentra una bifurcación de afinación en un bucle, y la última nota tocada fue una nota de valor A , Choon saltará inmediatamente para comenzar a tocar después de la siguiente instrucción :|| . Si no hay más instrucciones :|| (lo que significa que ~ se ha usado fuera de las barras de repetición), el rendimiento terminará de inmediato.

  

• Marcadores

       

  Los marcadores proporcionan una conveniencia de programación maravillosa. Un marcador es una letra o palabra en minúscula que recuerda un punto en el flujo de salida. Al referirse a un marcador (ver más abajo), la nota tocada después de que ocurrió el Marcador se reproducirá nuevamente. Tenga en cuenta que las transposiciones afectarán esta nota recién reproducida.

       

  Cuando dos o más marcadores aparecen de forma secuencial, o un marcador sigue una instrucción de juego de marcador, deben estar separados por espacios en blanco.

  

• Reproducir desde la salida

       

  La instrucción Reproducir desde salida ( = ) le permite reproducir nuevamente las notas que ya se han reproducido en el flujo de salida. Puede referirse a las notas por número. La quinta nota tocada desde que comenzó el programa sería =5 , por número relativo. La tercera nota más reciente tocada será =-3 o por marcador: la nota tocada después del marcador x sería =x .

       

  Es un lenguaje común reutilizar un marcador y luego referirse a él, como este: x=x . Esto es similar a decir x=x+y en un lenguaje de programación convencional (donde y representa el valor de transposición actualmente efectivo).

  

Un John Cage es solo un rest , un Tuning Fork es (aproximadamente) dal segno, y un marcador es un segno. Supongo que la bifurcación podría ser ejecutada por un intérprete adicional al que responde el intérprete principal, pero el principio es el mismo.

La integridad de Turing requiere, como mínimo, tres cosas: un bucle infinito, un salto condicional (if-then) y una forma de almacenar los resultados de los cálculos en algún lugar de la memoria. Incluso si la notación musical tuvo saltos condicionales, no tiene estado, así que no, no es Turing-complete.

La prueba estándar para que un idioma se complete con Turing es escribir una máquina de Turing en ese idioma. Esto demuestra que existe una equivalencia entre el idioma (generalmente un subconjunto del idioma) y la máquina de Turing.

La noción de "Notación musical" es un poco resbaladiza. Hay una gran cantidad de grabado estandarizado que se utiliza. Sin embargo. Hay compositores que escriben sobre sobres que escriben todo tipo de cosas locas en un papel.

Supongamos que desea centrarse en el subconjunto de la notación musical que se considera lo suficientemente estándar como para formar parte de Finale o Sibelius o de un conjunto de herramientas de grabado de flujo principal.

Entonces.

Para Python (o C o lo que sea) usted define los símbolos, la cinta, las reglas de transición y las diversas acciones que actualizan la cinta para reflejar el cambio de estado y el movimiento de la cinta, leyendo y escribiendo símbolos en la cinta.

Usando "Notación musical", tenemos que definir los símbolos y la cinta con estado, las reglas de transición y las diversas acciones que actualizan la cinta.

Lo que nos falta es una cinta y reglas con estado que le digan a los músicos cómo responder a los símbolos en la cinta y cómo actualizar esa cinta.

En cierto sentido, los ruidos que fluyen en el aire podrían ser la cinta con estado. Pero. No hay una manera fácil de rebobinar la cinta. Esta falta de rebobinado significa que el artista tendría que mantener una "cinta" privada de algún tipo.

Esto se lleva a cabo fuera de la notación musical y en algunas otras instrucciones extra-musicales para el artista.     

Gran parte de la notación está abierta a la interpretación, y las instrucciones en lenguaje natural son un aspecto aceptado de la notación musical, y han estado presentes en casi toda la historia de la música notada de Occidente, si no toda.

Fermatas por definición, depende de la discreción del intérprete, lo que significa que dependerá de su propio estado, que es casi siempre alterado por la música en relación con factores externos, por lo que esto plantea algunas preguntas sobre la naturaleza sin estado de la notación musical.

Canon a 2 por Tonus de la Ofrenda Musical de Bach es una pieza con un bucle infinito cuya tonalidad se eleva en todo un paso cada vez que se realiza durante el tiempo que se realiza la pieza.

Más recientemente, es común ver instrucciones como "repetir para cada solista" en, por ejemplo, versiones notadas de piezas de Jazz como Dave Brubeck's Take Five .

Dicho esto, aparte de los aspectos intrínsecamente arbitrarios como los fermata, como indican las otras respuestas, la notación musical con nada más que los símbolos generales probablemente no esté completa.     

No está relacionado con los idiomas completos de Turing, ya que es un lenguaje descriptivo. No hay comandos en términos de cálculo o modificación de datos, ningún estado, ninguna entrada, ninguna salida excepto el resultado de la descripción en sí.

Tampoco hay saltos condicionales dependiendo de la entrada. Cuando resuelves todos los saltos, obtienes una estructura lineal, no un árbol. Así que todos los "programas" que pueden ser modelados por este lenguaje son lineales sin ningún tipo de bucles o saltos.