Escapar de la tarpit (policías)

9

Este es un desafío de basado en la definición de lenguajes y la prueba de que están completos.

Este es el hilo conductor de la policía. El hilo de los ladrones está aquí .

Policías

Como policía, prepararás dos cosas:

  • Una especificación formal de un lenguaje de programación u otro sistema computacional. (Los sistemas computacionales se definen a continuación).

  • Una prueba de que su sistema está Turing completo, de acuerdo con la definición algo estricta a continuación.

Publicará su especificación de su idioma, y ​​los ladrones intentarán "descifrarla" demostrando su integridad de Turing. Si su envío no se resuelve en una semana, puede marcarlo como seguro y publicar su prueba. (Su respuesta puede ser invalidada si alguien encuentra un defecto en su prueba, a menos que pueda solucionarlo).

Este es un , por lo que el ganador será la respuesta que tenga más votos, y que no esté descifrada o invalidada. El desafío es abierto: no aceptaré una respuesta.

En aras de este desafío, un sistema computacional se definirá como cuatro cosas:

  • Un "conjunto de programas" P. Este será un conjunto infinitamente contable, por ejemplo, cadenas, enteros, árboles binarios, configuraciones de píxeles en una cuadrícula, etc. (Pero vea la restricción técnica a continuación).

  • Un "conjunto de entrada" I, que también será un conjunto infinitamente contable, y no necesita ser el mismo conjunto que P(aunque puede serlo).

  • Un "conjunto de salida" O, que de manera similar será un conjunto infinitamente contable, y puede o no ser lo mismo que PoI

  • Un procedimiento determinista, mecanicista para producir una salida ode programa py de entrada i, donde p, iy oson miembros de P, Iy Orespectivamente. Este procedimiento debe ser tal que, en principio, pueda implementarse en una máquina de Turing u otro modelo abstracto de cómputo. El procedimiento puede, por supuesto, no detenerse, dependiendo del programa y su entrada.

Los conjuntos P, Iy Odeben ser tales que pueda expresarlos como cadenas de manera computable. (Para las elecciones más sensatas, esto no importará; esta regla existe para evitar que elija conjuntos extraños, como el conjunto de máquinas de Turing que no se detienen).

La integridad de Turing se definirá de la siguiente manera:

  • Para cualquier función parcial computable fde Ia O, existe un programa pen Ptal que dado py entrada i, la salida es f(i)si f(i)tiene un valor. (De lo contrario, el programa no se detiene).

La palabra "computable" en la definición anterior significa "se puede calcular usando una máquina de Turing".

Tenga en cuenta que ni la regla 110 ni la etiqueta cíclica bit a bit están completadas por Turing por esta definición, porque no tienen la estructura de entrada-salida requerida. El cálculo de Lambda es Turing completo, siempre que definamos Iy Oseamos los números de la Iglesia . (No es completo de Turing si tomamos Iy Opara ser expresiones lambda en general).

Tenga en cuenta que no tiene que proporcionar una implementación de su idioma, pero puede incluir una en su respuesta si lo desea. Sin embargo, no debe confiar en la implementación para definir el lenguaje de ninguna manera: la especificación debe estar completa en sí misma, y ​​si hay una contradicción entre la especificación y la implementación, esto debe tratarse como un error en la implementación.

Nathaniel
fuente
99
Lo siento chicos, pero el concurso de popularidad es un criterio objetivo ganador. Ser un pop-con no hace un desafío fuera del tema, y ​​nunca lo ha hecho. La meta discusión más reciente tiene un consenso de +27 a favor de esto, por lo que aunque los cinco de ustedes prefieran que sea diferente, realmente no tienen nada en qué apoyarse. Dado que esta pregunta se ha cerrado contra la política acordada, solicito que se vuelva a abrir.
Nathaniel
2
(tenga en cuenta que WhatWizard lo cerró por una razón diferente)
user202729
2
No utilice los votos cerrados como un botón "No estoy de acuerdo" o "No me gusta". Los votos cerrados se utilizarán para hacer cumplir la política del sitio. Si no está de acuerdo con una política, llévela a meta - no cierre los desafíos sobre el tema por consenso de la comunidad.
Mego
1
@Mego Voté para cerrar esto como demasiado amplio, pero también creo que esto está fuera de tema según nuestras reglas existentes para pop-cons. Esperamos que los concursos de popularidad tengan una "Una especificación clara del objetivo que debe lograrse", esta pregunta es un do X de la manera más creativa. Para mí está claro que no hay otro objetivo que no sea ser una respuesta válida y que la etiqueta pop-con se adjunta solo para mantenerla abierta.
Ad Hoc Garf Hunter
2
@WhatWizard, el objetivo que debe lograrse es no estar obviamente completo durante Turing, y la no evidencia se evalúa al no ser descifrado en una semana. ¿Eso no está claro?
Nathaniel

Respuestas:

10

Aritmética con los ojos vendados

Posiblemente un lenguaje bastante fácil para comenzar, relativamente hablando. (Hay límites en lo difícil que puedo hacer un idioma porque tengo que demostrarlo Turing: ¡completarlo yo mismo!)

Para este lenguaje, el conjunto de programas es el conjunto de programas aritméticos con los ojos vendados como se indica en la sección "programa" a continuación, el conjunto de entrada es el conjunto de enteros positivos, y el conjunto de salida es el conjunto de enteros (todo el conjunto, no solo los enteros positivos)

Este lenguaje es bastante interesante, tal vez incluso prácticamente útil, porque tiene una falta más o menos total de flujo de control, ya que se basa completamente en cálculos de números que no puede ver. Eso lo hace potencialmente útil como lenguaje para implementar programas dentro de sistemas de cifrado homomórficos .

Especificación

La aritmética con los ojos vendados es un lenguaje de programación esotérico con las siguientes especificaciones:

Almacenamiento de datos

El estado de un programa aritmético con los ojos vendados en ejecución consta de seis variables, cada una de las cuales puede almacenar un número entero. (No hay límites a lo grande o pequeña estos enteros pueden obtener, en particular, pueden ser negativo.) Las variables se llaman a, b, c, d, e, y i.

Al comienzo del programa, aa einclusivo cada uno se inicializa a 0, y ise inicializa a un entero positivo tomado de la entrada del usuario. (Si no hay entrada disponible, ise inicializa a 1.)

Si el programa deja de ejecutarse (esto solo puede ocurrir debido a la división por cero), el valor de iinmediatamente antes de intentar la división se utiliza como salida del programa.

Programa

Un programa aritmético con los ojos vendados es una lista de comandos, cada uno de los cuales tiene una de las siguientes formas (donde v puede ser reemplazado por cualquier nombre de variable, potencialmente un nombre diferente cada vez que se usa):

  • v = v + v
  • v = v - v
  • v = v * v
  • v = v / v

Tenga en cuenta que cada operando de los comandos debe ser una variable; Este lenguaje no permite el uso de enteros literales.

La ejecución del programa se realiza ejecutando cada uno de los comandos en secuencia, y luego regresando al inicio y continuando ejecutando los comandos en secuencia nuevamente, hasta el infinito (o hasta que haya un intento de dividir por cero, lo que finaliza el programa) .

Cada comando tiene la misma semántica que esperaría de la notación, que no es diferente de la utilizada por la mayoría de los lenguajes de programación prácticos: se toman los valores de la segunda y tercera variables mencionadas en el comando, una operación aritmética (suma / resta / multiply / divide respectivamente para las cuatro formas de comando) se les aplica y el valor resultante se almacena en la primera variable. La división aquí es división entera, redondeando hacia 0.

No hay flujo de control de ningún tipo, excepto la salida del programa; los comandos siempre se alternan en secuencia, hasta que se produce una división por cero (si corresponde) y finaliza el programa. En particular, no hay forma de leer directamente las variables, solo usarlas como fuente de cálculos cuyos resultados impactan los valores asignados a otras variables.

ais523
fuente
¿Pueden verificar si falta algo en mi respuesta ?
user202729
@ user202729: (comentando aquí ya que no tengo el representante para comentar allí) No puede simular un "movimiento si es falso" de un "flip" y un "movimiento si es verdadero" porque no puede deshacer el flip después de que te muevas. Por lo tanto, necesitará alguna otra forma de manejar eso (por ejemplo, una forma de invertir las pruebas, eso no debería ser difícil). Sin embargo, más notablemente, esa es una prueba de integridad de Turing en términos de comportamiento de detención, pero la definición en la pregunta requiere que también puedas hacer E / S, por lo que debes demostrar que puedes hacerlo.
ais523
Espero que la parte de E / S (ahora) esté bien. En cuanto al otro problema, me doy cuenta de que los estados internos, si ni siquiera son necesarios, resuelven todos los problemas (aunque no estoy seguro de cómo
decirlo
@ user202729: todavía no es del todo correcto (por ejemplo, la pregunta requiere que pueda generar números negativos, y también necesitaría cambiar el propósito de imodo que el número de estado, que siempre será "alto") no ser parte de la salida), pero está lo suficientemente cerca como para no marcarlo como seguro, ya que claramente obtendría una grieta completa con el tiempo suficiente y con suficiente aclaración de las reglas. No quiero ganar este desafío en tecnicismos.
ais523
Esto está muy cerca de las restricciones que usa de.ioccc.org/years-spoiler.html#1992_buzzard.1 . Esa implementación usa números enteros de tamaño fijo y, por lo tanto, no es completa de Turing, y esta está seriamente restringida en la cantidad de variables que tiene, pero creo que la prueba es similar.
b_jonas