Escribe un simulador de máquina de Turing .
Para simplificar, podemos suponer estados como enteros, símbolos como caracteres, símbolos en blanco es igual a espacios en blanco
5-tuplas en forma de estado actual, símbolo de entrada, siguiente estado, símbolo de salida, dirección (izquierda o derecha) el pedido no es obligatorio, pero especifique si lo intercambia
La máquina debe detenerse cuando se alcanza un estado desconocido, no se permite ninguna otra condición de detención.
La cinta es infinita en ambas direcciones y siempre puedes leer un carácter vacío.
Entrada: la cinta inicial, un estado inicial y un programa. puede leer los datos desde cualquier lugar en el formato que desee
Salida: la cinta después de la ejecución del programa.
Requerido: un programa de ejemplo que se ejecuta en la parte superior de su simulador
Este es un código-colf, por lo que gana el código más corto.
Publicaré una implementación y algunos programas de ejemplo en las próximas horas.
fuente
Respuestas:
GolfScript, 92 caracteres
La máquina de Turing en GolfScript se hizo mucho más larga de lo previsto. Todavía jugando con diferentes representaciones de la cinta.
La primera línea de la entrada es el estado original, la segunda línea la cinta inicial, seguida de una matriz de transiciones (con el estado actual del pedido, el símbolo de entrada, el siguiente estado, la dirección, el símbolo de salida).
Ejemplo (también disponible en línea )
fuente
GNU sed con
-r-13311711193 caracteresSí, sed se está completando. GNU sed y
-r(regexps extendidos) es solo para guardar algunos caracteres, es solo un pequeño cambio para trabajar con POSIX sed.El formato de entrada es
Los delimitadores
@,#y el carácter de cabeza>no se pueden utilizar como un símbolo en la cinta. Las etiquetas estatales no pueden contener@>o#.Ejecutará todos los programas en la entrada, uno por línea
Ejemplos:
Marco es un n b n programa
Hola Marco! programa
fuente
Así que llego un poco tarde, pero pensé que dejaría esto aquí ...
Máquina de Turing Simulando una máquina de Turing: ¿370 bytes?
Aquí estoy usando la estructura que Turing usó en su artículo de 1936. Estoy usando un símbolo = un byte, incluidas m-configs y operaciones.
Este es uno de los ejemplos de Turing del documento anterior para mi máquina:
Pruébalo en línea! (Utiliza Python 3 como intérprete) --Editar: Acabo de comprobar el TIO, y no parece funcionar realmente bien ... Pruébelo en su máquina local y debería (con suerte) funcionar. Lo hace en el mío.
fuente
APL (110)
(Ni siquiera es tan corto ...)
Lee dos líneas del teclado: la primera es el programa y la segunda es la cinta inicial.
El formato es
y todos deberían estar en la misma línea. 'Movimiento' es 0 para moverse hacia la derecha y 1 para moverse hacia la izquierda.
Programa de ejemplo (saltos de línea insertados para mayor claridad, deben estar todos en una sola línea).
El programa agrega dos números unarios juntos, por ejemplo:
Ejemplo 2 (adaptado del programa de incremento binario de la entrada de Marco Martinelli):
fuente
Python,
101189152142byp son las entradas, b es la cinta inicial, p codifica las reglas como (representación de cadena de) una sentencia de tupla (en estado, en cinta) a tupla (fuera de estado, movimiento de cabeza, fuera de cinta) . Si mover es 0, el programa termina, 1 es mover hacia la derecha y -1 es mover hacia la izquierda.
Este programa de prueba prueba si la última letra de la cadena (antes de la cinta vacía) es 'a', si es así, escribe 'Y' al final de la cadena (primer espacio vacío).
Editar 1:
Cambió la cinta para que se representara como un dict, ya que parecía la forma más corta de escribir una estructura de datos extensible. La penúltima línea la está transformando principalmente en una forma legible para la salida.
Edición 2:
Gracias a Strigoides por una gran cantidad de mejoras.
Edición 3:
Lo había hecho innecesariamente para que 0 como salida dejara el lugar como está. Eliminé esto ya que siempre podemos escribir la salida igual que la entrada.
fuente
r=0;s=0puede volverser=s=0(y el punto y coma al final de esa línea es innecesario), puede eliminar la funciónw, ya que no se utiliza, los corchetes se pueden quitar(s,m,t)=r[s,c], el bloquetry/exceptse puede acortar usando dict.get;c=a.get(i,' '), ya quemes 0 o 1, puede usarif m-1:, y puede acortar sumap()llamada convirtiéndola en una lista de comprensión.Posdata
(205)(156)(150)(135)Probablemente esto sea trampa, pero la tabla de transición contiene código para realizar las transiciones. Y dado que la cinta está representada por una asignación de enteros a enteros, he representado estados como una asignación de nombres a diccionarios para que la cinta y el programa coexistan en el mismo diccionario anónimo.
Ahorros adicionales al hacer que todos los nombres de estado sean ejecutables, por lo que se cargan automáticamente .
Ungolfed con el programa integrado "Hello".
52 caracteres adicionales compran un bucle para leer la cinta de stdin.Corre congsnd -q tm.ps.Entonces el formato de tabla es
donde
in-statees un nombrein-tapeyout-tapeson caracteres (es decir, enteros o expresiones que producen enteros),movementes-1para izquierda o1para derecha, yout-statees un nombre ejecutable . Lain-tapetransición múltiple para el mismo estado debe combinarse como se indicó anteriormente.fuente
currentdict{search-for-min-and-max}forall juggle-params-for-for. :(0 1 0 not{(%stdin)(r)file read not{exit}if def}for. No estoy seguro de por qué pensé que podría escapar omitiendo eso de la versión de golf. : P0 notdebería ser16#7fffffff. Lo siento. ¡Ajá! por eso fue comentado! Salió directamente del cuaderno, no se hizo la prueba, y recorté todos los comentarios sin mirar cuando lo jugué. ¡No le digas al tipo Python! : PC (no golfizado aún)
Supongo que no puedo ganar con esto, aún así fue divertido hacerlo funcionar. Esto es aún más cierto ahora que lo que realmente hace el trabajo. :)
Excepto que solo es infinito en una dirección. Supongo que también necesita una cinta negativa. Suspiro....
Negativo no fue tan malo. Intercalamos los dos lados como pares e impares. La complicación es que ahora necesita mostrar la cinta en orden secuencial , ya que el archivo en sí está ahora mezclado. Esta es una alteración legítima para hacer, creo. Turing mismo simplificó de esta manera.
Y aquí está la prueba de funcionamiento:
El programa genera la cinta en orden secuencial, pero el archivo representa los lados negativo y positivo intercalados.
fuente
0 'a' 0 'b' R; 0 'b' 0 'a' Rcon la entrada aaa, la salida es bab en lugar de bbb. Y hay problemas para moverse a la izquierda.Groovy
234228154153149139124Formateado para facilitar la lectura
t es la función que configura la cinta e es la función que evalúa el programa
Ejemplo 1 - Imprimir "¡Hola!" en la cinta :)
Ejemplo 2: deje una T en la cinta si la cadena inicial tiene la forma de a n b n ; deténgase de lo contrario.
Ejemplo 3 - Incremento de un número binario
en los ejemplos 1 significa moverse hacia la derecha y -1 significa moverse hacia la izquierda
fuente