Un desafío que pensé que sería genial es hacer un intérprete para un lenguaje completo de Turing de su elección.

Las reglas son simples:

1. Puede usar cualquier idioma para crear este intérprete, incluso si es más nuevo que este desafío.
2. Puede usar cualquier lenguaje completo de Turing siempre que no sea el mismo con el que lo está escribiendo.
3. No puede simplemente evaluar el código, por ejemplo, usar las funciones de evaluación.
4. Una explicación de cómo abordaste esto será agradable pero no obligatoria.
5. Esto se puntuará en bytes.
6. Cada envío debe estar funcionando completamente, lo que significa que todas las funciones que tiene el idioma elegido deben estar presentes.

En pocas palabras:

Su tarea es crear un intérprete que funcione para cualquier idioma completo de Turing con cualquier idioma de su elección.

¡Buena suerte!

Brachylog (2) → Problema de correspondencia posterior , 9 bytes

~h=∋ᵐ\cᵐ=

Pruébalo en línea!

La entrada es una lista de listas de cadenas. (En el problema de la correspondencia posterior tal como se define en Wikipedia, las listas internas tienen dos elementos cada una, aunque este programa en realidad puede manejar una generalización a cualquier número de elementos). Este programa aplica soluciones brutas al problema, en orden de longitud, hasta Se encuentra una solución. Se sabe que el problema de la correspondencia posterior es capaz de simular una máquina de Turing y, por lo tanto, las soluciones de fuerza bruta para él son completas. Si se ejecuta como una función, en lugar de un programa, en realidad también produce resultados significativos.

El programa en el enlace TIO anterior es el [["a","baa"],["ab","aa"],["bba","bb"]]que copié de Wikipedia. La solución (que el programa encuentra bastante rápido) es ["bbaabbbaa","bbaabbbaa"].

Explicación

Esto es prácticamente solo una traducción directa del problema de correspondencia de Post a Brachylog.

~h=∋ᵐ\cᵐ=
~h         Find {the shortest possible} list which starts with {the input}
  =        and for which all elements are equal
   ∋ᵐ      such that taking an element of each element,
     \cᵐ   and concatenating elements in corresponding positions,
        =  produces a list all of whose elements are equal.

Básicamente, creamos una lista que es copias repetidas de la entrada (lo menos posible, lo que significa que no perdemos ninguna posibilidad cuando se fuerza bruta), tomamos un elemento de cada copia y luego concatenamos los elementos correspondientes (como en la correspondencia posterior problema).

Jelly → "Agregar mínimo para transponer", 5 4 bytes

+"Ṃẞ

Pruébalo en línea! (ejecuta solo una iteración, para evitar tiempos de espera)

Una construcción completa de Turing muy simple: tomamos una matriz cuadrada como un programa y hacemos un ciclo para siempre, identificando la fila lexicográficamente más pequeña, luego incrementamos cada elemento de la primera fila por el primer elemento de la lexicografía más pequeña, cada elemento de la segunda fila por el segundo elemento de la lexicografía más pequeña, y así sucesivamente. (El programa Jelly es " +"agregar elementos correspondientes {de la entrada y} Ṃel mínimo {del original}, ẞbucle"; este es un byte más corto que mi programa anterior Z+ṂZß, que hizo exactamente lo mismo. Claramente debería haberme centrado en jugar al golf Jelly, no solo jugando al lenguaje implementado.)

El lenguaje resultante es Turing-complete por la misma razón que Kangaroo. El primer elemento de cada fila actúa como un recuento de omisión (aunque en lugar de que el recuento de omisión de cada comando se reduzca cuando se omite, aumentamos el recuento de omisión de cada comando cuando se ejecuta, y buscamos el comando con el recuento de omisión más bajo que los comandos con cero conteo de saltos; esto llega a ser lo mismo). Nos aseguramos de que este primer elemento sea más alto que los otros elementos (que representan la cantidad de veces que aparece cada comando en el conjunto múltiple de cada comando), asegurando así que la primera fila nunca sea la mínima; El resto de la primera fila puede ser basura. El único problema que queda es modelar la forma en que los comandos con un recuento de omisión igual se ejecutan cíclicamente en secuencia, pero podemos hacerlo multiplicando todos los recuentos de omisión por una constante grande y luego agregando un pequeño "inicial" saltar cuenta a la primera columna para servir como desempate. Esto nos da un desempate de "primeras ejecuciones de comandos no omitidas", no de "comandos no omitidos que se ejecutan cíclicamente en secuencia", pero a la construcción de integridad de Turing para Kangaroo no le importa esta diferencia.

Mathematica interpretando Conway's Game of Life, 64 bytes

CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}~Nest~##&

Se sabe que el Juego de la vida de Conway es Turing completo; y los autómatas celulares son la verdadera obsesión de Stephen Wolfram. CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}es una regla que transforma una matriz bidimensional de 0 y 1 según un paso del Juego de la vida de Conway. (Creo que el comportamiento predeterminado es que esta matriz se envuelve alrededor de sus bordes, por lo que es realmente un toro discreto). ~Nest~##&Convierte esta regla en una función que, cuando se le da un estado de placa inicial (de cualquier dimensión) y un número entero ncomo argumentos, genera el resultado de niteraciones de la regla del Juego de la Vida.

Para su propio disfrute, puede usar la versión envuelta

b = RandomInteger[1,{50,50}];
Manipulate[ArrayPlot[
  CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}~Nest~##&
    [b, n] ]
, {{n,0}, 0, 100, 1}]

y desplázate a través de 100 generaciones en una tabla de 50x50.

Turtlèd interpretando CT , 49 bytes

Podría ser capaz de jugar golf

Además, esto no genera nada útil. solo se detiene si y solo si el programa de CT dado se detiene.

este es uno que hice hace un tiempo en realidad (luego jugué un poco ahora)

!-l[*+.r_]' !l[ l]r[ u.(;d' u)d(1[ r].[ l])( r)+]

Cómo funciona:

Turtlèd usa celdas de cuadrícula. Cuando digo "escribir algo en la cuadrícula" me refiero a que se coloca un grupo contiguo de caracteres en la cuadrícula. ejemplo

[ ][ ][ ][ ][ ][ ][ ]
[ ][H][E][L][L][O][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]

en el programa

los datos se ingresan primero:

!-l[*+.r_]' 

Esto es esencialmente un programa de gato. escribe la entrada en la cuadrícula.

entonces se ingresan los comandos:

!

qué hace con estos comandos:

Estos comandos son "producciones". si el bit de datos más a la izquierda es un 1, copia la producción al final de la cadena de datos. de lo contrario no pasa nada. luego se elimina el bit de datos más a la izquierda y utiliza la siguiente producción con el siguiente bit de datos más a la izquierda. el programa se detiene cuando no hay bits en la cadena de datos. Una forma de hacer estas producciones es lidiar con los bits y el final de las producciones por separado. Esto es lo que hace nuestro programa. copia por separado los bits de la cadena de comando al final de la cadena de datos y elimina por separado los bits de la cadena de datos

sobre cómo lo hace este programa. después de ingresar los comandos, el puntero de tortuga / cuadrícula retrocede al bit más a la izquierda de la cadena de datos. luego entra en un bucle

[ u.(;d' u)d(1[ r].[ l])( r)+]

lo que hace en este bucle es que se mueve hacia arriba desde la cadena de datos más a la izquierda y anota el carácter de comando actual (u.). si es así;, al final de una producción, se mueve hacia abajo y elimina el bit de datos más a la izquierda debajo de él y se mueve hacia arriba ( (;d' u)). entonces, de cualquier manera, se mueve hacia abajo uno ( d). si el bit no se eliminó, significa que debe verificar si se debe copiar un bit de los comandos al final. entonces, si este carácter que es o fue el bit de datos más a la izquierda es un 1, se moverá al final del extremo derecho de la cadena de datos, copiará el bit de la cadena de comando y volverá al espacio a la izquierda de los datos más a la izquierda bit ( (1[ r].[ l])). ahora, está en el bit de datos más a la izquierda, que era un cero, o a la izquierda del bit de datos más a la izquierda. entonces, nos movemos a la derecha si en un espacio (( r)) luego, el puntero del comando se incrementa, por lo que escribiremos el siguiente comando en la próxima iteración del bucle. Si no hay más cadenas de datos, esto significa que estaremos en un espacio y el ciclo finalizará. de lo contrario, volveremos a ejecutar el bucle.

Perl → Variante de programador de tres estrellas , 26 + 1 = 27 bytes

++$a[$a[$a[$_]]]for@F;redo

Pruébalo en línea! (Este enlace contiene un encabezado que sale del programa después de un número determinado de iteraciones (para que el TIO no se agote), y para imprimir el estado interno cada iteración (para que haga algo observable).

Corre con -a(penalización de 1 byte, ya que puedes encajarlo antes -M5.010de producir -aM5.010).

Específicamente, esto implementa el Programador de tres estrellas en el que los comandos están separados por espacios y no se permiten comentarios en el archivo, sin extensiones de E / S. (Estos cambios no hacen ninguna diferencia en la integridad del lenguaje de Turing, obviamente.) No hay una prueba de la integridad de Turing para el programador de tres estrellas en línea, pero es completo de Turing (he estado compartiendo un bosquejo de su prueba de Turing -completar con otros esoprogramadores, pero dejé de trabajar en el lenguaje cuando descubrí que en realidad era bastante fácil de programar una vez que había superado el shock original).

El programa realmente no necesita mucha explicación; Three Star Programmer tiene una especificación muy simple, y esta es una traducción directa de la misma. Los únicos puntos sutiles: @Fes la entrada al programa en forma de matriz (esto es una consecuencia de -a); y redorepetirá todo el programa ya que está en un bucle implícito (también una consecuencia de -a).

Ensamblaje x86 (sintaxis Intel / MASM) -Brainfuck 2127 bytes.

Todavía golf capaz

.386
.model flat,stdcall
.stack 4096
include \masm32\include\masm32.inc
includelib \masm32\lib\masm32.lib
ExitProcess proto,dwExitCode:dword
.data
bfsrc BYTE 200 dup(0) 
bfcells BYTE 100 dup(0) 
loopStack DD 5 dup(0) 
charBuf BYTE 5 dup(0) 
newline BYTE 10,0 
prompt BYTE "$",0 
hr BYTE 50 dup('-'),0 
space BYTE ' ',0
.code
EvalBf proc
    start:
    invoke StdOut, addr prompt
    invoke StdIn, addr bfsrc,200
    cmp bfsrc,0
    je exit
    mov eax,0 
    mov ebx,0 
    mov ecx,0 
    processInstruction:
    cmp BYTE PTR bfsrc[ebx], '+'
    je plus
    cmp BYTE PTR bfsrc[ebx], '-'
    je minus
    cmp BYTE PTR bfsrc[ebx], '>'
    je fwd
    cmp BYTE PTR bfsrc[ebx], '<'
    je back
    cmp BYTE PTR bfsrc[ebx], '['
    je open
    cmp BYTE PTR bfsrc[ebx], ']'
    je close
    cmp BYTE PTR bfsrc[ebx], '.'
    je dot
    jmp processNextInstruction
    plus:
    inc BYTE PTR bfcells[eax]
    jmp processNextInstruction
    minus:
    dec BYTE PTR bfcells[eax]
    jmp processNextInstruction
    fwd:
    inc eax
    jmp processNextInstruction
    back:
    dec eax
    jmp processNextInstruction
    open:
    mov loopStack[ecx*4],ebx
    inc ecx
    jmp processNextInstruction
    close:
    dec ecx
    cmp BYTE PTR bfcells[eax], 0
    je processNextInstruction
    mov ebx,loopStack[ecx*4]
    inc ecx
    jmp processNextInstruction
    dot:
    mov dl, BYTE PTR bfcells[eax]
    mov BYTE PTR charBuf[0], dl
    mov BYTE PTR charBuf[1],0anything
    push eax
    push ecx
    invoke StdOut, addr charBuf
    pop ecx
    pop eax
    jmp processNextInstruction
    processNextInstruction:
    inc ebx
    cmp BYTE PTR bfsrc[ebx], 0
    je done
    jmp processInstruction
    done:
    invoke StdOut, addr newline
    mov eax, 0
    printNext:
    cmp eax, 100
    jge reset
    push eax
    invoke dwtoa, BYTE PTR bfcells[eax], addr charBuf
    invoke StdOut, addr charBuf
    invoke StdOut, addr space
    pop eax
    inc eax
    jmp printNext
    reset:
    invoke StdOut, addr newline
    invoke StdOut, addr hr
    invoke StdOut, addr newline
    jmp start

    exit:
    invoke ExitProcess,0
EvalBf endp
end EvalBf

Pip que interpreta sistemas de etiquetas cíclicas , 16 bytes

YqWyyPBg@++vXPOy

Toma las producciones del sistema de etiquetas como argumentos de línea de comandos y la cadena de datos inicial de stdin.

El código anterior es un poco difícil de verificar porque no produce ningún resultado (por lo que el único comportamiento observable es "termina" frente a "no termina"). Por lo tanto, aquí hay una versión no protegida que genera la cadena de datos después de cada paso, y también termina después de 20 pasos para que TIO no tenga que lidiar con toneladas de salida de bucles infinitos: ¡ Pruébelo en línea!

Sistemas de etiquetas cíclicas

Los sistemas de etiquetas cíclicas son un modelo computacional extremadamente simple pero completo de Turing . Consisten en una lista de producciones que definen operaciones en una cadena de datos . Las producciones y la cadena de datos constan de 1 y 0.

En cada paso, se elimina el carácter más a la izquierda de la cadena de datos.

• Si el carácter es 1, la producción actual se agrega al lado derecho de la cadena de datos.
• Si el carácter es 0, no se agrega nada.

En cualquier caso, la producción actual pasa a la siguiente producción de la lista, cíclicamente: si estuviéramos en la última producción, daremos la vuelta al primero. La ejecución continúa hasta que la cadena de datos esté vacía.

Explicación

                  g is list of cmdline args; v is -1 (implicit)
 q                Read a line of stdin for the data string
Y                 and yank it into the y variable
  Wy              While data string is nonempty:
       g@++v       Retrieve the next production from g (using cyclic indexing)
             POy   Pop the first character of y
            X      String-multiply: result is the production if the first character of y
                   was 1, or empty string if it was 0
    yPB            Push that string to the back end of y

Funciones de Collatz generalizadas iteradas -> Python 2, 46 bytes

a,b,x,m=input()
while-~x%m:x=x/m*a[x%m]+b[x%m]

Llame a esta función con una lista de m-1 a's y b's, el valor inicial x, y el divisor m, que colectivamente constituyen un "programa" para IGCF. En lugar de tomar una tercera matriz para indicar en qué módulos detener, esto simplemente se detiene cada vez que el módulo es m-1. Esta simplificación significa que puede tomar un esfuerzo adicional convertir un programa Fractran dado en esta variante, pero ahorra un par de bytes en el intérprete.

Pruébalo en línea! Este TIO muestra cómo agregar 5 + 5 con este idioma. El programa a = [3], b = [0], m = 2 suma, y ​​comenzando con 7776 = 2 ^ 5 * 3 ^ 5 finalmente produce 59049 = 3 ^ 10.

Variante ResPlicate -> Python 2, 47 bytes

l=input()
while l:l=l[2+l[0]:]+l[2:2+l[0]]*l[1]

Esta función interpreta una variante de ResPlicate

• para el cual un programa es una lista de Python de longitud par con elementos pares en índices pares.
• sin E / S.
• para lo cual intentar copiar más valores de los que existen en el resto de la cola simplemente copia el resto de la cola (es decir, el bit copiado no se rellena con ceros a la longitud requerida).

El último cambio significa que algunos programas ResPlicate (que cumplen con la primera condición) no se comportarán igual en esta variante, pero afortunadamente, los intérpretes BCT no requieren la funcionalidad eliminada, por lo que el lenguaje sigue siendo TC.

Pruébalo en línea! Este TIO tiene una impresión en cuña para mostrar que funciona y un encabezado que mata el programa después de 1 segundo y un ejemplo que logra generar más resultados de los que TIO puede manejar en ese segundo.

Perl -a → máquina I / D , 24 bytes

$p=$a[$p]+=$_ for@F;redo

Pruébalo en línea! (contiene un encabezado que imprime el estado interno y se detiene después de 10 iteraciones, para que el comportamiento sea observable)

Sobre el idioma

He pasado los últimos días trabajando en la máquina I / D , una de mis últimas ideas para lenguajes de programación muy simples. Funciona de la siguiente manera: el almacenamiento de datos consiste en una RAM sin límites, inicialmente todos ceros. Cada elemento puede almacenar un número entero ilimitado (aunque en la práctica, la mayoría de los programas de máquina de I / D solo almacenarán números enteros pequeños en la mayoría de ellos, y utilizarán los números enteros ilimitados solo como una forma de direccionar celdas con direcciones grandes). También hay un puntero de datos, que apunta a una celda (es decir, contiene la dirección como una celda); Inicialmente también es cero.

Solo hay dos comandos:

• I: Incremente la celda a la que apunta el puntero de datos. (El puntero de datos en sí permanece sin cambios).
• D: Haga referencia al puntero de datos, es decir, lea el valor de la celda a la que apunta el puntero de datos. Luego almacene el valor resultante que leyó en el puntero de datos.

La ejecución simplemente ejecuta el programa en un ciclo repetidamente, para siempre.

Es bastante sorprendente que un lenguaje así de simple sea completo de Turing, así que he estado trabajando para demostrarlo. Aquí está la prueba . Es bastante similar (pero más simple que) la prueba para Three Star Programmer, un lenguaje muy similar (y de hecho, esta presentación utiliza el mismo "shell" básico de OISC alrededor del programa, que difiere solo en la instrucción real implementada).

Sobre el programa

Uso

La entrada debe darse en la entrada estándar, y es un programa de máquina I / D sin comentarios, y usando la sintaxis RLE / OISC. (La máquina I / D tiene dos sintaxis equivalentes diferentes, pero para el golf, este programa solo admite uno de ellos). En esta sintaxis, un programa es una secuencia de números en decimal, que representa la longitud de las ejecuciones de Icomandos entre Dcomandos. (Puede especificar dos o más Dcomandos consecutivos colocando una "ejecución de 0 Icomandos" entre ellos, por lo que la sintaxis es completamente general).

Explicación

Como se puede ver en el programa, esto no está implementando los comandos Iy Dindividualmente. De hecho, es un intérprete optimizador (muy levemente) (simplemente porque es más corto para escribir de esta manera). La clave es ver que una serie de comandos de incremento n incrementen el objetivo del puntero de datos n veces, es decir, agreguen n ; y una ejecución de comandos de incremento 0 también se puede implementar de esta manera, ya que agregar 0 a la memoria no tiene ningún efecto. Entonces, la operación que implementamos realmente es alternar entre implementar una serie de Is y una D. O en otras palabras, "agregue nal valor señalado por el puntero de datos (almacenándolo de nuevo en el valor señalado por el puntero de datos), luego lea el valor señalado por el puntero de datos y guárdelo en el puntero de datos ". Eso es claramente más detallado de lo que necesita ser, y podemos simplificar aún más esto para "agregar n al valor señalado por el puntero de datos, luego almacenar ese valor tanto en el objetivo del puntero de datos como en el puntero de datos en sí".

Eso hace que sea el núcleo de nuestro programa. Estamos usando una matriz $apara almacenar la RAM, y $pcomo puntero de datos (indexación en la matriz):

$p=$a[$p]+=$_
         + $_  add {the run length}
   $a[$p]      to the element of $a pointed to by $p
   $a[$p] =    storing the result back into that element
$p=            and also in the pointer itself

Convenientemente, Perl interpreta los elementos de la matriz no inicializados como 0 cuando se tratan como números, por lo que la matriz se inicializará perezosamente en ceros para nosotros sin ningún código explícito para eso. (Un problema potencial es la precisión numérica cuando los números aumentan; sin embargo, eso solo sucederá si la cantidad de la matriz que se usa excede el espacio de direcciones de la máquina (los enteros Perl son lo suficientemente grandes como para contener punteros), algo que no puede suceder en una máquina idealizada)

Finalmente, todo lo que necesitamos hacer es colocar este programa en un par de bucles. El for@Fbucle, combinado con la -aopción de línea de comando, recorrerá los campos de entrada estándar (la definición predeterminada de "campo" aquí se dividirá en espacios en blanco). El redobucle colocará todo el programa en un bucle implícito (que no sea, convenientemente, la lectura de la entrada estándar), lo que hará que el programa se ejecute en un bucle repetidamente, como lo requiere la semántica de la máquina I / D.

Jelly → sistema de 2 etiquetas , 8 bytes

µḢị⁴⁸;Ḋß

Pruébalo en línea!

Tengo una recompensa que favorece los lenguajes prácticos, pero pensé que podría tratar de ganar la tarea original mientras estaba en ella (ya que no puedo ganar exactamente mi propia recompensa).

Implementa una variante de sistemas de etiquetas sin estado de detención, ya que no es necesaria para la integridad de Turing. Los estados están numerados de 1, consecutivamente, y la cadena inicial viene antes del programa.

Por ejemplo, Wikipedia ofrece un ejemplo de un sistema de etiqueta { a, b, c}, { a→ bc, b→ a, c→ aaa} con la secuencia inicial aaa; en este formato de entrada, que es [1,1,1], [[2,3],[1],[1,1,1]]. (Los sistemas de etiquetas no tienen una sintaxis fija, y esta parece ser una forma razonable de hacerlo).

El enlace TIO tiene un agregado Ṅ("escribir estado interno y una nueva línea en stdout") para mostrar que el programa está funcionando.

Explicación

µḢị⁴⁸;Ḋß
           {implicit: initialise internal state from first argument}
µ          Disregard the second command-line argument by default
 Ḣ         Take the first element, removing it from the internal state
  ị⁴       Use the value to index into the second argument
    ⁸;     Prepend (the rest of) the internal state
      Ḋ    Discard the first element of the internal state
       ß   Loop forever

BF / P "implementado en una máquina de Turing, 842 bytes

Tabla de transición (vinculada por longitud)

Mesa de transición, versión menos golfizada

Simulador de máquina de Turing que utilicé

Ciertamente, esto no va a ganar ningún premio por la duración, pero es algo que siempre quise hacer, ya que BF es muy similar a una máquina de Turing. Cada celda almacena un valor de 0x0- 0xF. Sin embargo, el ancho puede llegar al sitio web de Turing Machine sin bloquear su navegador. Las funciones ,y .(entrada y salida) no están definidas, por lo que se parece un poco más a P "que a BF verdadero.

Para ejecutarlo, pegue la tabla de transición en el simulador de Turing Machine, configure la entrada en algún código BF y presione ejecutar.

La cinta de la TM almacena tanto el código BF como los datos BF, con un solo espacio en el medio. Realiza un seguimiento de su posición en el código modificando el carácter que está ejecutando actualmente ( [-> (, etc.) y su posición en los datos con un ^frente de la celda. Una vez que lee un carácter de comando, se mueve hasta que golpea el cursor, mueve una celda a la derecha y realiza la función adecuada. Luego regresa, busca uno de los caracteres de comando "modificado" en el código BF, y pasa al siguiente, repitiendo todo el proceso. Una vez que se queda sin código, se detiene.

La mejor manera de entender cómo funciona es ejecutando la versión no golfizada, poniéndola en modo paso a paso y observando qué líneas conducen a qué otros y qué hace cada estado / bloque de líneas.

Las versiones de golf y sin golf son exactamente iguales en términos de cómo funcionan, pero la versión sin golf tiene nombres más amigables para los humanos y se divide en secciones.

C implementando la (2,3) Máquina de Turing , 236 205 bytes ( 46 31 menos si no le importan las entradas incómodas)

Gracias a Appleshell por -11 bytes, VisualMelon por -12 bytes y Johan du Toit por -7 bytes.

CeilingCat hizo una versión que usa solo 144 bytes, mira aquí .

(He agregado algunos saltos de línea aquí para que no tenga que desplazarse, pero normalmente la mayoría de ellos se eliminarían)

#define c char
j;i;k;c s,d[256];c main(){c*p=d+128;gets(d);
for(;k<256&&d[k];)d[k++]-=48;for(;++j<256;)
{c t=*p;*p=-t*t+(2-s)*t+1+s;p+=(s^t==0)*2-1;s=s?t%2:!t%3;
for(i=0;++i<256;)printf("%d",d[i]);puts("");}}

Pruébalo en línea!

Para usar: ingrese una cadena de hasta 256 unos, ceros y dos para inicializar la cinta. Cualquier valor no inicializado será cero. (Los valores distintos de 0, 1 y 2 pueden causar un comportamiento indefinido). El programa repetirá más de 256 pasos. El número de pasos por los que se repite se puede aumentar modificando el código, pero obviamente eso requiere más caracteres.

Es una entrada bastante larga, pero esta es la primera vez que hago una de estas y no utilicé un lenguaje de golf dedicado. Me divertí mucho, incluso si resultó más de lo que esperaba.

Muchos de los bytes son de entrada y salida, y perdí 42 bytes enteros haciendo que acepte 0, 1 y 2 en lugar de NUL, SOH, STX. (Para cambiar eso, elimine k;desde el frente y for(;k<256&&d[k];)d[k++]-=48;desde la segunda línea).

La tabla de transición, especialmente la línea *p=-t*t+(2-s)*t+1+s;(que establece los valores en la cinta) probablemente también podría comprimirse más.

Röda implementando Fractran , 114 112 106 bytes

1 byte guardado gracias a @fergusq al reorganizar los parámetros

f&n,a{x=1{x=0;(a/" ")()|[_/`/`]|[parseInteger(_[0],_1[1])]|{|q,w|{n*=q/w;x=1}if[n%w<1,x<1]}_,_}while[x>0]}

Pruébalo en línea!

Llame a la función de este modo: f reference_to_input program. La salida se almacenará en la ubicación de input.

Clojure, 82 81 bytes (máquina de Turing)

Actualización: se eliminó un espacio de t{} s.

#(loop[p 0 t{}s 1](if-let[[S M N](%[(or(t p)0)s])](recur(+ p M)(assoc t p S)N)t))

Implementa la máquina de Turing como un bucle, devuelve la cinta cuando se alcanza el estado de detención. En las reglas de transición de estado esto se indica omitiendo el estado de transición. Esto se establece Nen nily el siguiente abortará if-letya que la transición de estado correspondiente no se encuentra en el hash-map de entrada %. En realidad, cualquier valor para este estado servirá, como :abort0 o -1.

Ungolfed con un ejemplo de 3 estados y 2 símbolos de castores ocupados de Wikipedia .

(def f #(loop[pos 0 tape {} state 1]
          (if-let [[sym move next-state](%[(get tape pos 0)state])]
            (do (println [pos tape state])
                (recur(+ pos move)(assoc tape pos sym)next-state))
            tape)))

(f {[0 1] [1  1 2]
    [0 2] [1 -1 1]
    [0 3] [1 -1 2] 
    [1 1] [1 -1 3]
    [1 2] [1  1 2]
    [1 3] [1  1]})

{0 1, 1 1, -1 1, -2 1, -3 1, 2 1}

Pruébalo en línea .

En un solo núcleo de 6700K, esto ejecuta el castor ocupado de 5 símbolos y 2 símbolos (47.1 millones de pasos) en aproximadamente 29 segundos, o 1.6 millones de pasos / segundo.

M → Consejo , 4 bytes

Ṅ×ịß

Pruébalo en línea!

El enlace TIO agrega un pie de página para llamar a la función con el programa Tip de ejemplo que se muestra en la página de Esolang ("envoltura automática" de M para llamar a funciones como si fueran programas que no pueden manejar números racionales o de punto fijo, o al menos no tengo no descubrí cómo decirlo, así que necesito hacer que la función sea un programa completo a mano para poder ejecutarla).

Esto realmente imprime resultados de depuración útiles; el programa no se puede escribir en 3 bytes en M porque un programa que consta de exactamente tres díadas activa un caso especial en el analizador, por lo que tuve que agregar un comando adicional para evitar el caso especial. Hacerlo Ṅ(imprimir con nueva línea) al menos le da un propósito útil.

ı$i=\sqrt{-1}$

No implementa E / S (que no sea detener / no detener). I / O es una extensión de Tip (no forma parte del lenguaje en sí) y no es necesario para completar Turing.

Explicación / antecedentes

Ṅ×ịß
Ṅ     Print {the left argument} and a newline; also resolves a parser ambiguity
  ị   {The left argument}th element of {the right argument}, wrapping on OoB
 ×    Multiply {the left argument} by {the chosen element}
   ß  Recursive call; arguments: {the product} and {the same right argument}

[1,2,3][1,2,3,1,2,3,1,2,3,…]$rx+s$, que es un polinomio, y la "conversión de base" incorporada que tienen muchos lenguajes de golf es en realidad un evaluador polinomial de uso general disfrazado. Entonces, todo lo que tenemos que hacer es indexar en una lista de listas de dígitos, convertirlos en base y listo, ¿verdad?

$x$$x$

ḅ$x\oplus(x\otimes y)$$x\otimes y$${\oplus}$. Claro, podríamos anular el comportamiento de encadenamiento a casi todo lo que queramos, pero eso costaría un byte completo, y las entradas del idioma de golf para esta pregunta se están volviendo tan cortas que un byte es mucho.

Así que miré hacia atrás y volví a evaluar un poco. ¿Hay alguna operación que podamos usar en lugar de una evaluación polinómica? Idealmente, los que son conmutativos, para que no tengamos que preocuparnos por el orden de los argumentos. Poco después de eso, me di cuenta de que las funciones de Collatz son más complejas de lo que deberían ser.

$s$

Y, por supuesto, a diferencia de la conversión de base ( ḅ), la multiplicación ( ×) es conmutativa y, por lo tanto, no importa en qué orden se coloquen los argumentos. Por lo tanto, todo lo que necesitamos escribir es ×ị, y luego colocar el programa en una recursión infinita con ß, y tenemos un lenguaje completo de Turing. ¿Correcto?

$(x\odot y)\oplus(x\otimes y)$¹×ịß¹¹Ṅ es una buena opción porque produce resultados de depuración útiles.

¿Son posibles tres bytes? A menos que me falte algo, no con esta elección específica de implementación y lenguaje implementado, pero en este punto seguramente parece que sería posible de alguna manera, ya que hay muchas maneras de hacerlo en cuatro y tantos Turing-complete idiomas que podrías implementar.

C interpretando Brainfuck, 187 bytes

t[999],*p=t,c,i,l;f(char*t){for(i=0;c=t[i];i++){c^62?c^60?c^43?c^45?c^46?c^44?c^91:(*p=getchar()):putchar(*p):--*p:++*p:--p:++p;if(c==93&&*p)for(l=1;l>0;)c=t[--i],c==91?l--:c==93?l++:0;}}

Pruébalo en línea

Lua interpretando Brainf ***, 467 bytes

b,r,a,i,n,s=0,io.read,{0},1,1,"><+-.,[]"c,f=r(),{function()n=n+1;a[n]=a[n]or 0;end,function()n=n-1;a[n]=a[n]or 0;end,function()a[n]=a[n]+1;end,function()a[n]=a[n]-1;end,function()io.write(string.char(a[n]))end,function()a[n]=io.read():byte()end,function()i=a[n]~=0 and i or c:find("]",i)end,function()if a[n]~=0 then b,x=1,""repeat i=i-1 x=c:sub(i,i)b=x=="["and b-1 or x=="]"and b+1 or b until b==0 and x=="["end end}repeat f[s:find(c:sub(i,i),1,1)]()i=i+1 until i>#c

Sé que todavía hay algo de adelgazamiento que puedo hacer más tarde, pero aquí es donde terminó mi primer pase. Toma el código brainf de la entrada estándar.

CJam → Variante Resplique, 15 14 13 bytes

^{-1 byte gracias a @ ais523}

l~{(/((*+e_}h

La variante es la misma que la de esta respuesta , excepto que el número de elementos retirados de la cola es uno menos que el número superior en la cola.

La l~{ ... }hparte solo toma una matriz como entrada y se repite hasta que esa matriz esté vacía.

Explicación para el bucle principal:

    e# Stack:             | [3 2 1 1 2 2 2 1]
(   e# Pop first element: | [2 1 1 2 2 2 1] 3
/   e# Split chunks:      | [[2 1 1] [2 2 2] [1]]
(   e# Pop first:         | [[2 2 2] [1]] [2 1 1]
(   e# Pop first:         | [[2 2 2] [1]] [1 1] 2
*   e# Repeat array:      | [[2 2 2] [1]] [1 1 1 1]
+   e# Concatenate:       | [[2 2 2] [1] 1 1 1 1]
e_  e# Flatten:           | [2 2 2 1 1 1 1 1]

Chip , 20 + 3 = 23 bytes (Regla 110)

AZZ
>}/a
`)\'E~Zte*f

+3 para bandera -z

Pruébalo en línea!

Esta presentación no es perfecta, ya que Chip (todavía) no tiene ninguna capacidad de bucle, por lo que la salida debe pasarse como entrada para simular varias generaciones, con algo como esto (por supuesto, podría ejecutar ese bucle indefinidamente, y Chip puede manejar entradas arbitrariamente largas, por lo que esta combinación es Turing completa).

Esta implementación toma entrada y salida dada en forma de ASCII 0sy 1s. La lógica aquí es la siguiente:

p := value of left neighbor cell    AZZ
q := value of current cell          AZ
r := value of right neighbor cell   A

q' := ((r xor q) and p) or          >}/a
      ((r or q) and ~p)             `)\'

El resto de los elementos son para la limpieza: e*fgenera una salida numérica ASCII y E~Ztfinaliza la ejecución dos bytes después de que se agota la entrada (ya que el ancho aumenta en 2 cada generación).

Clojure, 75 bytes (sistema de etiquetas cíclicas)

Actualización 1: reemplazado some?por nil?.

Actualización 2: Se corrigió una falta Sen la rama else de if s.

#(loop[[p & P](cycle %)[s & S]%2](if(nil? s)S(recur P(if s(concat S p)S))))

Implementa el sistema de etiquetas cíclicas , devuelve nilsi el programa se detiene, se repite para siempre. Clojure realmente brilla aquí con infinitas secuencias perezosas (como el ciclo ) y la desestructuración . Unos y ceros se indican como valores verdaderos y falsos. Cuando se agota la cadena de datos se sconvierte en nil.

Sin golf:

(def f #(loop[[p & P] (cycle %) [s & S] %2 i 5]
          (do
            (pprint [p (concat [s] S)])
            (if (and (some? s) (pos? i))
              (recur P (if s (concat S p) S) (dec i))))))

Resultados de ejemplo:

(f [[false]] [true true])
[[false] (true true)]
[[false] (true false)]
[[false] (false false)]
[[false] (false)]
[[false] (nil)]

(f [[false true true] [true false] [true false true]] [true])
[[false true true] (true)]
[[true false]      (false true true)]
[[true false true] (true true)]
[[false true true] (true true false true)]
[[true false]      (true false true false true true)]
[[true false true] (false true false true true true false)]

JavaScript que interpreta la Regla 110 , 131 bytes (99 bytes ?, 28 bytes?)

a=(p,q,r)=>q+r+q*r+p*q*r
b=l=>{r="";for(i=0;i<l.length-2;i++)r+=a(l[i],+l[i+1],+l[i+2])%2;return r}
c=(l,n)=>!n?l:c(b(0+l+0),n-1)

Como puede ver, el código define 3 funciones a, by c. Quizás sea posible guardar bytes combinándolos en 1 función (no veo cómo), pero es bueno que se separen porque cada uno de ellos ya cumple este desafío en algún sentido.

La función atoma 3 números como entrada y calcula algunos polinomios extraños de ellos. Cuando estos 3 números son 0o 1pueden verse como celdas de la Regla 110. La paridad de la salida de apuede verse como el valor de la celda intermedia en la próxima generación. Entonces, en cierto sentido, esta función simple ya es un 'intérprete' de la Regla 110 (28 bytes):

a=(p,q,r)=>(q+r+q*r+p*q*r)%2

Luego podemos crear una nueva función bque evalúa acada carácter de una cadena de unos y ceros. Esto bes, entonces, mejor que aun intérprete de la Regla 110. Tomando el mod 2 después de la evaluación de los corchetes guardados (99 bytes):

a=(p,q,r)=>q+r+q*r+p*q*r
b=l=>{r="";for(i=0;i<l.length-2;i++)r+=a(l[i],+l[i+1],+l[i+2])%2;return r}

Para calcular realmente una función con la Regla 110, el usuario debe especificar el estado inicial y el número de generaciones después de las cuales "aparecerá" la salida. Podemos hacer una tercera función cque tome una cadena de unos y ceros, y un entero positivo n, que luego se evalúa ben la cadena, nveces. Así podemos ver realmente la Regla 110 como un lenguaje de programación, donde un programa es un estado inicial y un número n, y la salida es el estado después de ngeneraciones. La función cahora es un intérprete real para ese lenguaje de programación, por lo que el código final para este desafío es lo que presenté anteriormente.

JS -> Nueva línea 854 bytes

(function(d){var b=0;var n=!0;var c=[];var h=[];var e=0;var l=[];var m=0;var f=2;var a=0;var g=!1;var k=function(a){if(a===1)return!1;if(a%2===0&&a!==2)return!1;if(a%3===0&&a!==3)return!1;if(a%5===0&&a!==5)return!1;if(a%7===0&&a!==7)return!1;for(var b=7;b<d.round(d.sqrt(a))+1;b++)if(a%b===0)return!1;return f=a,!0;};var j=0;var i=0;var o=function(q){var o=d.__split(q,'\n');d.println(o);for(var n=0;n<o.length;n++)if(n>=f^2&&n<=f+1^2&&k(n)){f=n;for(var p=0;p<o[n].length;p++){if(o[n]==='+'&&(a+=c[b],b++),o[n]==='-')if(g===!0&&a<=0)break;else a-=c[b],b++;if(o[n]==='*'&&(a*=c[b],b++),o[n]==='/'&&(a/=c[b],b++),o[n]==='s'&&(a=d.sqrt(a)),o[n]==='%'&&(a%=c[b],b++),o[n]==='a'&&l.push(a),o[n]==='g'&&(a=c[b],b++),o[n]==='q'&&c.push(a),o[n]==='i'&&a++,o[n]==='d')if(g===!0&&a<=0)break;else a--;o[n]==='r'&&(g=!0),o[n]==='w'&&(g=!1),o[n]==='['&&(j=n),o[n]===']'&&a>0&&(n=j,h[e]--),o[n]==='{'&&(i=n),o[n]==='}'&&h[e]>0&&(n=i,h[e]--),m=a,o[n]==='k'&&e++;}}};});

Súper golf gracias a google.

Clojure, 87 bytes (Regla 110)

¡El crédito por el código de paridad es para Jens Renders! Realmente estaba luchando sobre cómo expresar esto e iba a convertir [p q r]de binario a entero y usar una tabla de búsqueda.

#(iterate(fn[S](for[[p q r](partition 3 1(concat[0]S[0]))](mod(+ q(* q(+ 1 p)r)r)2)))%)

Aquí partitiony la desestructuración de Clojure hace que la aplicación lógica sea bastante simple. Esta función devuelve una secuencia infinita de estados, por lo que la persona que llama es responsable de taketodos los que necesita o simplemente nthpara saltar a un estado específico. Si los rellenos con cero fueran dos elementos en lugar de uno solo, la cinta crecería constantemente, evitando problemas de límites. Ahora se mantiene el ancho original.

Ejemplo:

(def f #(iterate(fn[S](for[[p q r](partition 3 1(concat[0]S[0]))](mod(+ q(* q(+ 1 p)r)r)2)))%))

(pprint (take 5 (f '(0 0 0 0 0 1 1 1 0 0 1 0 0))))
((0 0 0 0 0 1 1 1 0 0 1 0 0)
 (0 0 0 0 1 1 0 1 0 1 1 0 0)
 (0 0 0 1 1 1 1 1 1 1 1 0 0)
 (0 0 1 1 0 0 0 0 0 0 1 0 0)
 (0 1 1 1 0 0 0 0 0 1 1 0 0))

APL (Dyalog) → Variante de Fractran , 15 bytes

(⊃0~⍨××0=1|×)⍣≡

Pruébalo en línea!

La función toma los racionales como una lista de números en lugar de dos listas que contienen el numerador y el denominador, y genera el resultado si el programa finaliza. Esto implementa una variante de Fractran que tiene el 1/1 racional (= 1) al final del programa. El 1 no tiene ningún efecto sobre la integridad de Turing (hasta donde yo entiendo) porque la entrada al programa solo aterriza en el 1 cuando ninguno de los otros racionales funciona, y cuando lo hace, la entrada no cambia. Esto solo se usa para que la función sepa cuándo finalizar.

El enlace TIO ejecuta la función durante 2 iteraciones (para que pueda ver la salida ya que el programa no termina) en la primera entrada, y ejecuta la segunda entrada hasta su finalización, después de lo cual devuelve la salida.

(⊃0~⍨××0=1|×)⍣≡ toma la lista de racionales como argumento izquierdo, para referirse como ⊣, y la entrada como argumento derecho, para referirse como ⊢

(⊃0~⍨××0=1|×) tren de funciones

• 1|×obtener la parte después del punto decimal (módulo 1) del producto ×de ⊣ y ⊢

• 0= ¿es igual a 0?

• ×× multiplique este resultado con ⊣ × ⊢, siempre que el racional × ⊢ no sea un entero, se reemplaza por 0

• 0~⍨ eliminar todos los 0s

• ⊃ obtener el primer elemento

⍣bucle hasta que la ≡entrada no cambie, tenga en cuenta que el resultado de (⊃0~⍨××0=1|×)se reutiliza como entrada, por lo que si deja de cambiar (como resultado del 1 al final) el programa se detiene

JavaScript: cálculo Lambda ( 123114 )

Representado usando Debruijn Indicies en Duples.

V=function b(c,d){if(!isNaN(c)){for(;--c;)d=d[1];return d[0]}return 0==c[0]?e=>b(c[1],[e,d]):b(c[0],d)(b(c[1],d))}

El combinador S es [0, [0, [0, [[3, 1], [2, 1]]]]]

K es [0, [0, 2]]

Yo es [0, 1]

Editar: Afeitado 9 bytes reemplazando "number"==typeof ccon!isNaN(c)

APL (Dyalog Unicode) , ^{SBCS de} 15 bytes

Programa completo que implementa un ejecutor de autómata celular unidimensional generalizado. Esto incluye la Regla 110 que se completa con Turing. Solicita stdin para el estado inicial, el número de iteraciones (o ≡para continuar hasta que sea estable o {⍵≡⎕←⍺}para mostrar todos los valores intermedios hasta que sea estable) y el conjunto de reglas.

⎕∊⍨∘(⊢∘⊂⌺3)⍣⎕⊢⎕

Pruébalo en línea! (4 iteraciones de la Regla 110)

⎕ solicitud de estado inicial y

⊢ producir eso (separa el estado del número de iteraciones)

⍣⎕ solicite el número de iteraciones y aplique la siguiente función muchas veces:

 (... ) aplique la siguiente función tácita:

  ⌺3 obtenga todos los vecindarios de longitud 3 (con información sobre si están en el borde) y aplique la siguiente función tácita a cada par:

   ⊂ encerrar el barrio

   ∘ y

   ⊢ producir eso (descartando la información sobre estar al borde)

 ∘ luego

 ∊⍨ comprobar si son miembros de

 ⎕ solicitar una lista de vecindarios que conducen a estar en la próxima iteración