Este es un desafío de policías y ladrones 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 concurso de popularidad , 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 queP
(aunque puede serlo).Un "conjunto de salida"
O
, que de manera similar será un conjunto infinitamente contable, y puede o no ser lo mismo queP
oI
Un procedimiento determinista, mecanicista para producir una salida
o
de programap
y de entradai
, dondep
,i
yo
son miembros deP
,I
yO
respectivamente. 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
, I
y O
deben 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
f
deI
aO
, existe un programap
enP
tal que dadop
y entradai
, la salida esf(i)
sif(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 I
y O
seamos los números de la Iglesia . (No es completo de Turing si tomamos I
y O
para 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.
Respuestas:
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
, yi
.Al comienzo del programa,
a
ae
inclusivo cada uno se inicializa a 0, yi
se inicializa a un entero positivo tomado de la entrada del usuario. (Si no hay entrada disponible,i
se inicializa a 1.)Si el programa deja de ejecutarse (esto solo puede ocurrir debido a la división por cero), el valor de
i
inmediatamente 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/
vTenga 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.
fuente
i
modo 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.