Aviso: estoy dispuesto a dar una recompensa por cualquier respuesta que me parezca interesante.
Su desafío es diseñar una computadora de conjunto de instrucciones de Turing-complete (OISC):
Un OISC es una máquina abstracta que usa solo una instrucción, lo que evita la necesidad de un código de operación de lenguaje de máquina. Con una elección juiciosa para la instrucción individual y recursos infinitos dados, un OISC es capaz de ser una computadora universal de la misma manera que las computadoras tradicionales que tienen múltiples instrucciones.
Aquí hay algunos ejemplos de comandos únicos que hacen un OISC completo de Turing.
Reglas:
Debe proporcionar una interpretación o prueba de ello.
Debe proporcionar un intérprete para su idioma. Este intérprete solo debe estar restringido por memoria / tiempo (por ejemplo, no debe tener restricciones impuestas por el usuario). Si no proporciona un intérprete para su idioma (por cualquier otro motivo que no sea la pereza), debe demostrar que es posible que se escriba uno. Un intérprete debe ser posible .
Debes demostrar su integridad de Turing
Debe incluir una prueba formal de que su idioma es Turing completo. Una forma sencilla de hacerlo es demostrando que puede interpretar o tener el mismo comportamiento que otro lenguaje completo de Turing. El lenguaje más básico para interpretar sería Brainf ** k .
Por ejemplo, un lenguaje normal que tiene los mismos comandos que Brainf ** k (y la misma falta de restricciones de memoria impuestas por el usuario) es Turing completo porque todo lo que se puede implementar en Brainf ** k se puede implementar en el idioma .
Aquí hay una lista de lenguajes completos de Turing muy fáciles de implementar.
Requisitos adicionales de OISC
Este OISC solo debe tener una instrucción: no puede tener varias instrucciones con una de ellas, lo que lo hace completo para Turing.
Su OISC puede usar cualquier sintaxis que desee. Debe definir en su respuesta qué es la instrucción, qué son los datos y qué es un no operativo (por ejemplo, espacios en blanco). ¡Ser creativo!
Los argumentos no solo necesitan ser enteros. Por ejemplo, /// es un hermoso ejemplo de un OISC completo de Turing.
Cómo y si la entrada y la salida son tomadas y dadas son dejadas a usted. La mayoría de los OISC implementan E / S a través de ubicaciones de memoria específicas, pero puede haber otras formas de hacerlo, y le recomendamos que encuentre una.
Una respuesta válida debe proporcionar un código de ejemplo en su OISC, ya sea incluyéndolo en la publicación o vinculándolo a un desafío simple resuelto en el idioma.
Votación
Votantes, por favor recuerden no votar las presentaciones aburridas. Ejemplos:
- Lenguage -equivalents
- Una implementación de un OISC existente (respondedores, ¡cree el suyo propio!)
- Un "OISC" en el que el primer argumento especifica un comando para llamar ( ejemplo )
Sin embargo, debe votar las presentaciones interesantes y creativas, como:
- Un OISC basado en una ecuación matemática
- Un ZISC completo de Turing basado en una red neuronal
- Un OISC en el que la E / S de salida ocurre de formas distintas a ciertas ubicaciones de memoria
Victorioso
Al igual que con el concurso de popularidad , ¡la respuesta con más votos gana! ¡Buena suerte!
Respuestas:
XOISC
Este OISC se basa en el combinador X de Fokker que se define de la siguiente manera:
Si reconocemos el hecho de que el cálculo de SKI está completando Turing, el combinador anterior también está completo. Esto se debe a que S , K y yo podemos escribir en términos de X , así:X S K yo X
Cómo funciona XOISC
Internamente, XOISC tiene una pila (inicialmente vacía), desde allí la instrucción que toma como argumento hace lo siguiente:norte
Una vez que no quedan más instrucciones, XOISC empujará todos los argumentos de la línea de comandos (si los hay) a la pila, por ejemplo:
El cálculo final será .( ... ( ( ... ( s1 s2) ... ) s METRO) a 1) ... ) anorte
Como la única instrucción en XOISC toma solo un argumento (desplazamiento de memoria), no hay razón para usar un nombre para esa instrucción. Por lo tanto, un archivo fuente válido constituirá únicamente enteros separados por líneas nuevas o espacios en blanco, como por ejemplo:
Pruébalo en línea!
Ejemplo
Tomemos el ejemplo anterior (la pila crece a la derecha):
Finalmente, evalúe la pila: o con menos paréntesis X ( X X ) ( X X ) ( X X ) que reconocemos como la buena identidad de S K K función.( ( X ( X X) ) ( X X) ) ( X X) X ( X X) ( X X) ( X X) S K K
Integridad de Turing
Idea de prueba
0
0
2
0
2
Así que terminamos con un programa XOISC diferente (pero semánticamente equivalente):
0 0 2 0 2 0 2
Pruébalo en línea!Prueba formal
Dado que el cálculo de SKI es Turing completo, debemos mostrar dos cosas:
La primera parte, que demuestra las tres igualdades en la introducción, es muy tediosa y requiere mucho espacio, y tampoco es muy interesante. Entonces, en lugar de ponerlo en esta publicación, puedes encontrarlo aquí * .
0
Interprete
Entradas
Dado que el cálculo lambda sin tipo requiere que definamos nuestros propios tipos de datos para todo lo que queremos y esto es engorroso, el intérprete conoce los números de la Iglesia ; esto significa que cuando proporciona entradas, transformará automáticamente los números a su correspondiente número de Iglesia.
Como ejemplo, aquí hay un programa que multiplica dos números: ¡ Pruébelo en línea!
También puede proporcionar funciones como argumentos mediante el uso de índices De Bruijn , por ejemplo, el
S
combinador\\\(3 1 (2 1))
(oλλλ(3 1 (2 1))
). Sin embargo, también reconoce elS
,K
,I
y por supuestoX
combinador.Salida
Por defecto, el intérprete verifica si la salida codifica un número entero; si lo hace, generará el número correspondiente (además del resultado). Por conveniencia, está la
-b
bandera que le dice al intérprete que intente hacer coincidir un booleano (vea el último ejemplo).Ensamblador
Por supuesto, cualquier lenguaje de bajo nivel necesita un ensamblador que convierta un lenguaje de alto nivel en él, simplemente puede usar cualquier entrada (ver arriba) y traducirlo a un programa XOISC usando la
-a
bandera, ¡ pruébelo en línea! ** *** En caso de que el enlace esté inactivo, hay una copia como comentario HTML en esta publicación.
** Esto da como resultado un programa que prueba la originalidad, ¡ pruébelo en línea!
fuente
Dibujar
Draw es un OISC que actúa en una cuadrícula 2D, marcando cuadrados de manera similar a la máquina Wang B. Sin embargo, para mantener el lenguaje lo más simple y OISC-y posible, todas las instrucciones (de las cuales hay un gran total de uno) marcan el cuadrado que acaba de pisar y, para poder detenerse, pisar un cuadrado marcado termina el programa
El programa consiste en una secuencia de líneas que contienen un identificador de línea (cadena arbitraria que no incluye # o espacios en blanco), dos enteros (
x
yy
) y dos identificadores de línea más (a
yb
).El programa se ejecuta de la siguiente manera:
A partir de la línea identificada como
start
con el puntero que apunta a la posición (0, 0), mover el puntero por la cantidad dada porx
yy
y marcan la plaza el puntero se encuentra ahora en adelante (a menos que la plaza ya está marcado, en cuyo caso la ejecución termina). Luego, salta a la líneaa
si al menos uno de los cuadrados directamente adyacentes también está marcado, y a la línea de lob
contrario.Se alienta a los intérpretes a mostrar el resultado final de la cuadrícula como algún tipo de imagen, lienzo, etc.
Integridad de Turing
Draw es Turing completo, ya que es posible compilar una versión modificada (llamada alternativa) de una máquina Minsky en el idioma.
Alternate actúa de manera similar a una máquina Minsky de dos contadores, pero existe una gran restricción en los comandos: los comandos deben alternar entre apuntar al primer y segundo contador. Para conseguir alrededor de esta modificación, un comando adicional se ha añadido:
nop
. Este comando no cambia el contador objetivo en absoluto, lo que hace posible "rellenar" los cambios consecutivos a un contador, satisfaciendo la restricción descrita anteriormente. Esto también significa que el registro que se va a modificar no tiene que ser dado y, para cualquier instrucción dada, se puede inferir directamente de las instrucciones desde las cuales la ejecución puede saltar a él.Ejemplo: esta máquina Minsky
se convierte en este programa alternativo:
Esta restricción es necesaria debido a la forma en que el programa Draw eventual maneja los registros, lo que quiere decir que no los diferencia en absoluto. En cambio, el programa Draw simplemente copia el registro que no ha sido modificado por la instrucción anterior, modificándolo de acuerdo con la instrucción que se está ejecutando.
Luego, el programa alternativo se traduce directamente en Draw de la siguiente manera:
El programa comienza con este bloque.
inc
,dec
ynop
se traducen casi de la misma manera entre sí. En todos los casos, no hay diferencia entre cambiar el primer o el segundo registro (como se explicó anteriormente). Aquí hay un incremento, equivalente ainc 2
:Cambie los números en las
i1_x
partes al índice de la instrucción actual, y en lasi2_x
partes al índice de la siguiente instrucción a ejecutar.La
nop
instrucción se puede traducir como tal:Esta es una disminución:
i3_x
se refiere a la instrucción a llamar si el contador ya es 1.Detener:
Cambie las etiquetas adecuadamente y simplemente encadene todo. Hacer esto para el ejemplo de arriba da el programa Draw en el repositorio de arriba.
Intérpretes
Actualmente hay dos intérpretes, ambos escritos en Python. Se pueden encontrar en el repositorio GitHub de Draw .
elresultado gráfico más fácil y con elpropósito equivocado, tomando la fuente a través de un cuadro emergente al iniciar el script. Golly puede ser un poco quisquilloso con Python, así que asegúrese de tener instalado Python 2 (y no mezcle Golly de 32 bits con Python de 64 bits o viceversa). La salida se proporciona a través de la cuadrícula de celdas incorporada de Golly.La siguiente imagen es un ejemplo para la salida del segundo intérprete. Ejecutar el programa de ejemplo en el repositorio da esto (o similar):
fuente
-3
Aquí está la esencia.
Memoria
La memoria es un mapa de cintas, donde las claves son cadenas y los valores son enteros de tamaño arbitrario.
Además, hay un conjunto de etiquetas, donde el programa puede saltar.
Hay una pila, que contiene los operandos, que son cadenas.
Hay una ofensa, que controla dónde puede acceder en las cintas de la memoria.
La única instrucción
-
. Primero, saca una cadenaLABEL
de la pila. Si esoLABEL
no está definido como una etiqueta, define la etiqueta y borra la fuente de esa etiqueta (es decir, de dónde fue empujada) y la instrucción actual. De lo contrario, realiza el siguiente cálculo, utilizando los dos valores superioresA
yB
:Tenga en cuenta que si hay argumentos en exceso o argumentos insuficientes, el programa generará un error, mostrando el estado del programa.
El desplazamiento se puede modificar accediendo al valor de
.
.Código de ejemplo
Esto establece la variable
i
en7
, incrementando los7
tiempos.Esto se multiplica
i+1
por la constante2
.Prueba de integridad de Turing
Sin tener en cuenta los tamaños int de C ++ (es decir, suponiendo que sean infinitos), -3 es Turing Completo por reducción a un brainfuck de 3 células . Puedo ignorar este tamaño porque se puede escribir un intérprete para -3 en una computadora con memoria infinita que tiene celdas arbitrariamente grandes.
También creo que cualquier BCT puede escribirse como un programa -3.
fuente