El objetivo de este desafío es (eventualmente) generar todos los posibles programas de detención en el idioma que elija. Al principio esto puede sonar imposible, pero puede lograr esto con una elección muy cuidadosa de la orden de ejecución.

A continuación se muestra un diagrama ASCII para ilustrar esto. Deje que las columnas representen una numeración de cada programa posible (cada programa es un número finito de símbolos de un alfabeto finito). Deje que cada fila represente un paso singular en la ejecución de ese programa. An Xrepresenta la ejecución realizada por ese programa en ese paso de tiempo.

 step#  p1 p2 p3 p4 p5 p6
     1  X  X  X  X  X  X
     2  X  X  X  X  X  
     3  X  X     X  X
     4  X  X     X  X
     5  X  X     X
     6     X     X
     7     X     X
     8     X     X
     9     X     X
     ∞     X     X

Como puede ver, los programas 2 y 4 no se detienen. Si los ejecutara uno a la vez, su controlador se quedaría atascado en el bucle infinito que es el programa 2 y nunca generaría los programas 3 y posteriores.

En su lugar, utiliza un enfoque de cola de milano . Las letras representan un posible orden de ejecución para los primeros 26 pasos. Los *s son lugares donde ese programa se ha detenido y se emite. Los .s son pasos que aún no se han ejecutado.

 step#  p1 p2 p3 p4 p5 p6
     1  A  C  F  J  N  R  V
     2  B  E  I  M  Q  *  Z
     3  D  H  *  P  U
     4  G  L     T  Y
     5  K  O     X
     6  *  S     .
     7     W     .
     8     .     .
     9     .     .
     ∞     .     .

Requisitos para el idioma de destino

El idioma de destino (el que se interpreta en paralelo) debe ser Turing completo. Aparte de eso, puede ser cualquier idioma que sea Turing completo, incluidos los subconjuntos Turing completos de idiomas mucho más grandes. También es libre de interpretar cosas como las reglas del sistema de etiquetas cíclicas. También puede crear un idioma para probar, siempre y cuando pueda mostrar por qué es Turing completo.

Como ejemplo, si elige probar brainfuck, lo mejor es probar solo el []-+<>subconjunto, ya que la entrada no es compatible y la salida simplemente se descarta (ver más abajo).

Cuando se trata del programa "controlador" (que está jugando al golf), no hay requisitos especiales. Se aplican restricciones de idioma normales.

Cómo crear una lista infinita de programas

La mayoría de los lenguajes de programación se pueden representar como una serie de símbolos de un alfabeto finito. En este caso, es relativamente fácil enumerar una lista de todos los programas posibles en orden creciente. El alfabeto que use debe ser representativo de los requisitos del idioma de destino. En la mayoría de los casos, esto es ASCII imprimible. Si su idioma admite Unicode como una característica adicional, no debe probar todas las combinaciones posibles de caracteres Unicode, solo ASCII. Si su idioma solo usa []-+<>, no pruebe las diversas combinaciones de caracteres ASCII de "comentario". Idiomas como APL tendrían sus propios alfabetos especiales.

Si su idioma se describe mejor de alguna manera no alfabética, como Fractran o Turing Machines, existen otros métodos igualmente válidos para generar una lista de todos los posibles programas válidos.

Interpretar una lista cada vez mayor de programas

La parte clave de este desafío es escribir un intérprete paralelo para una lista creciente de programas. Hay algunos pasos básicos para esto:

• Agregue un número finito de programas a la lista
• Interprete cada programa en la lista individualmente por un período de tiempo finito. Esto se puede lograr realizando un paso de instrucción para cada uno. Salva a todos los estados.
• Eliminar todos los programas de terminación / lanzamiento de errores de la lista
• Salida de los programas limpiamente detenidos *
• Agregue algunos programas más a la lista
• Simule cada programa a su vez, retomando la ejecución de programas antiguos donde se dejó
• Eliminar todos los programas de terminación / lanzamiento de errores de la lista
• Salida de los programas limpiamente detenidos *
• repetir

* Solo debe generar programas que se detengan limpiamente. Esto significa que no hubo errores de sintaxis o excepciones no detectadas lanzadas durante la ejecución. Los programas que solicitan información también deben finalizar sin generarlos. Si un programa produce resultados, no debe terminarlos, solo bótelos.

Más reglas

• No debe generar nuevos subprocesos para contener los programas probados, ya que esto descarga el trabajo de paralelización en el sistema operativo host / otro software.
• Editar: para cerrar posibles lagunas futuras, no se le permite eval(ni ninguna función relacionada) una parte del código del programa probado . Usted puede eval un bloque de código a partir del código del intérprete. (La respuesta BF-in-Python sigue siendo válida según estas reglas).
• Esto es código golf
• El idioma en el que escribe su envío no necesita ser el mismo que el idioma que está probando / enviando.
• Debe suponer que su memoria disponible no tiene límites.
• Al probar la integridad de Turing, puede suponer que la entrada está codificada en el programa y que la salida se puede leer en el estado interno del programa.
• Si su programa se genera solo, probablemente sea incorrecto o políglota.

subleq OISC en Python, 317 269 ​​bytes

import collections
g=0
P={}
while 1:
    P[g]=[[0],collections.defaultdict(int,enumerate(list(int(x)for x in reversed(str(g)))))]
    g+=1
    for o,[a,p]in P.items():
        i=a[0]
        p[i+p[i+1]]-=p[i+p[i]]
        if p[i+p[i+1]]<=0:a[0]+=p[i+2]
        else:a[0]+=3
        if a[0]<0:print o;del P[o]

https://esolangs.org/wiki/Subleq

Un programa subleq es una lista extensible de enteros (p) y un puntero de instrucción (i). Esta variante subleq utiliza el direccionamiento relativo, que la página de discusión wiki sugiere que se requiere para asegurar la integridad con valores acotados. Cada tic, p[i+p[i+1]]-=p[i+p[i]]se realiza la operación , y i+=p[i+2]si el resultado de la operación fue <= 0, de lo contrario i+=3. Si alguna vez es negativo, el programa se detiene.

Esta implementación prueba cada programa cuyo estado inicial se compone de enteros no negativos de un dígito (0-9) con un puntero de instrucción inicial de 0.

Output:
21 (which represents the program [1 2 0 0 0 0 0...]
121
161
221
271
351
352
461
462
571
572
681
682
791
792

La salida se invierte, por razones de golf. La especificación anterior podría reexpresarse a la inversa, pero no coincidiría con el código utilizado en la implementación, por lo que no lo he descrito de esa manera.

EDITAR: El primer programa que exhibe un crecimiento ilimitado simple es 14283, que disminuye el valor en la ubicación de memoria 6 y escribe un 0 explícito (en oposición al 0 implícito en cada celda) en la siguiente celda negativa, cada tres tics.

Etiqueta cíclica bit a bit en CJam, 98 87 84 77 bytes

L{Z):Z2b1>_,,1>\f{/([\:~]a2*}+{)~[\({1+(:X+\_0=Xa*+}{0+\1>}?_{]a+}{];p}?}%1}g

Como se trata de un bucle infinito, no puede probarlo directamente en el intérprete en línea. Sin embargo, aquí hay una versión alternativa que lee el número de iteraciones de STDIN para que juegues. Para probar el programa completo, necesitará el intérprete de Java .

BCT es una variante minimalista de Cyclic Tag Systems . Un programa está definido por dos cadenas binarias: una lista (cíclica) de instrucciones y un estado inicial. Para facilitarme la vida al imprimir los programas, he definido mi propia notación: cada una de las cadenas se da como una matriz de enteros estilo CJam, y todo el programa está rodeado [[...]], por ejemplo

[[[0 0 1 1] [0 1 1 1 0]]]

También estoy rechazando estados iniciales vacíos o listas de instrucciones vacías.

Las instrucciones en BCT se interpretan de la siguiente manera:

• Si la instrucción es 0, elimine el bit inicial del estado actual.
• Si la instrucción es 1, lea otro bit de la lista de instrucciones, llame a eso X. Si el bit inicial del estado actual es 1, agregue Xal estado actual, de lo contrario no haga nada.

Si el estado actual alguna vez se vacía, el programa se detiene.

Los primeros pocos programas de detención son

[[[0] [0]]]
[[[0] [1]]]
[[[0 0] [0]]]
[[[0] [0 0]]]
[[[0 0] [1]]]
[[[0] [0 1]]]
[[[0 1] [0]]]
[[[0] [1 0]]]
[[[0 1] [1]]]
[[[0] [1 1]]]

Si desea ver más, consulte la versión en el intérprete en línea que he vinculado anteriormente.

Explicación

Así es como funciona el código. Para realizar un seguimiento de la combinación, siempre tendremos una matriz en la pila que contiene todos los programas. Cada programa es un par de una representación interna del código del programa (como [[0 1 0] [1 0]]), así como el estado actual del programa. Solo usaremos el último para hacer el cálculo, pero necesitaremos recordar el primero para imprimir el programa una vez que se detenga. Esta lista de programas simplemente se inicializa en una matriz vacía con L.

El resto del código es un bucle infinito {...1}gque primero agrega uno o más programas a esta lista y calcula un paso en cada programa. Los programas que se detienen se imprimen y eliminan de la lista.

Estoy enumerando los programas contando un número binario. El primer dígito se elimina para garantizar que también podamos obtener todos los programas con ceros a la izquierda. Para cada representación binaria truncada, presiono un programa por cada posible división entre instrucciones y estado inicial. Por ejemplo, si el contador está actualmente en 42, su representación binaria es 101010. Nos deshacemos del liderazgo 1y empujamos todas las divisiones no vacías:

[[[0] [1 0 1 0]]]
[[[0 1] [0 1 0]]]
[[[0 1 0] [1 0]]]
[[[0 1 0 1] [0]]]

Como no queremos instrucciones o estados vacíos, comenzamos el contador en 4, lo que da [[[0] [0]]]. Esta enumeración se realiza mediante el siguiente código:

Z):Z    e# Push Z (initially 3), increment, and store in Z.
2b1>    e# Convert to base 2, remove initial digit.
_,      e# Duplicate and get the number of bits N.
,1>     e# Turn into a range [1 .. N-1].
\       e# Swap the range and the bit list.
f{      e# Map this block onto the range, copying in the bit list on each iteration.
  /     e#   Split the bit list by the current value of the range.
  (     e#   Slice off the first segment from the split.
  [     
    \:~ e#   Swap with the other segments and flatten those.
  ]     e#   Collect both parts in an array.
  a2*   e#   Make an array that contains the program twice, as the initial state is the
        e#   same as the program itself.
}
+       e# Add all of these new programs to our list on the stack.

El resto del código asigna un bloque a la lista de programas, que realiza un paso del cálculo de BCT en la segunda mitad de estos pares y elimina el programa si se detiene:

)~     e# Remove the second half of the pair and unwrap it.
[      e# We need this to wrap the instructions and current state back in an array
       e# again later.
\(     e# Bring the instruction list to the top and remove the leading bit.
{      e# If it's a 1...
  1+   e#   Append a 1 again (the instructions are cyclic).
  (:X+ e#   Remove the next bit, store it in X and also append it again.
  \_0= e#   Bring the current state to the top, get its first bit.
  Xa*+ e#   Append X if that bit was 1 or nothing otherwise.
}{     e# Else (if it's a 0...)
  0+   e#   Append a 0 again (the instructions are cyclic).
  \1>  e#   Discard the leading bit from the current state.
}?
_      e# Duplicate the current state.
{      e# If it's non-empty...
  ]a+  e#   Wrap instructions and state in an array and add them to the program
       e#   pair again.
}{     e# Else (if it's empty)...
  ];p  e# Discard the instructions and the current state and print the program.
}?

Brainfuck en Python, 567 bytes

Una solución relativamente simple, ya que Brainfuck no es el idioma más difícil para el que escribir un intérprete.

Esta implementación de Brainfuck tiene el puntero de datos que comienza en 0, solo se le permite tomar un valor positivo (se considera un error si intenta ir a la izquierda de 0). Las celdas de datos pueden tomar valores de 0 a 255 y ajustarse. Las 5 instrucciones válidas son ><+[]( -es innecesario debido al ajuste).

Creo que la salida es correcta ahora, sin embargo, es difícil estar seguro de que está imprimiendo todas las soluciones posibles, por lo que es posible que me falte alguna.

o="><+]["
A="[]if b%s1<0else[(p,a+1,b%s1,t+[0],h)]"
C="[(p,h[a]+1,b,t,h)if t[b]%s0else(p,a+1,b,t,h)]"
I=lambda s,i:i*">"if""==s else o[o.find(s[0])+i-5]+I(s[1:],i*o.find(s[0])>3)
s="";l=[]
while 1:
 s=I(s,1)
 r=[];h={}
 for i in range(len(s)):
    if s[i]=="[":r+=[i]
    if s[i]=="]":
     if r==[]:break
     h[r[-1]]=i;h[i]=r[-1];r=r[:-1]
 else:
    if r==[]:
     l+=[(s,0,0,[0],h)];i=0
     while i<len(l):
        p,a,b,t,h=l[i]
        if a>=len(p):print p;l[i:i+1]=[]
        else:l[i:i+1]=eval([A%("+","+"),A%("-","-"),"[(p,a+1,b,t[:b]+[(t[b]+1)%256]+t[b+1:],h)]",C%">",C%"=="][o.find(p[a])]);i+=1

Las primeras salidas:

>
+
>>
+>
><
>+
++
[]
>>>
+>>

Y una lista de los primeros 2000: http://pastebin.com/KQG8PVJn

Y, por último, una lista de los primeros resultados de 2000 con []ellos: http://pastebin.com/iHWwJprs
(todos los demás son triviales siempre que sean válidos)

Tenga en cuenta que la salida no está en un orden ordenado, aunque puede parecer así para muchos de ellos, ya que los programas que tardan más se imprimirán más adelante.

barras en Python, 640 498 bytes

g=2
P={}
while 1:
    b=bin(g)[3:]
    P[b]=[[0],['',''],[b]]
    g+=1
    for d,[a,b,c]in P.items():
        s=c[0]
        if a[0]:
            if s.count(b[0]):s=s.replace(b[0],b[1],1)
            else:a[0]=0
        else:
            if s[0]=='0':
                if len(s)==1:del P[d];continue
                s=s[2:]
            else:
                b[0]=b[1]=''
                a[0]=1
                t=p=0
                while t<2:
                    p+=1
                    if p>=len(s):break
                    if s[p]=='0':
                        if p+1>=len(s):break
                        b[t]+=s[p+1]
                        p+=1
                    else:t+=1
                if t<2:del P[d];continue
        c[0]=s
        if len(s)==0:print d;del P[d]

https://esolangs.org/wiki////

Un programa de barras es una cadena, en este intérprete limitado a los caracteres '/' y '\'. En esta implementación, / es '1' y \ es '0' para permitir jugar al golf con el uso de bin (x) de python. Cuando el intérprete encuentra un \, se emite el siguiente carácter y se eliminan ambos caracteres. Cuando encuentra un /, busca patrones de búsqueda y reemplazo como / search / replace / incluyendo caracteres escapados dentro de los patrones (\\ representa \ y \ / representa /). Esa operación de reemplazo se realiza en la cadena repetidamente hasta que la cadena de búsqueda ya no esté presente, luego la interpretación continúa desde el principio nuevamente. El programa se detiene cuando está vacío. Se eliminará un programa si hay un conjunto no cerrado de / patrones o un \ sin ningún carácter después de él.

Example output and explanations:
01 outputs '1' and halts
00 outputs '0' and halts
0101 outputs '11' and halts
0100 ...
0001
0000
010101
010100
010001
010000 ...
101110 replaces '1' with '', leaving '00', which outputs '0' and halts

Treehugger en Java, 1,299 1,257 1,251 1,207 1,203 1,201 1,193 1,189 bytes

import java.util.*;class I{static class N{N l,r;byte v;}static class T extends Stack<N>{{push(new N());}void p(){pop();if(size()==0)p();}int i,h;char[]s;}static void s(T t){if(t.i>=t.s.length){t.h=1;return ;}char c=t.s[t.i];if(c=='<'){if(t.peek().l==null)t.peek().l=new N();t.push(t.peek().l);}if(c=='>'){if(t.peek().r==null)t.peek().r=new N();t.push(t.peek().r);}if(c=='^')t.p();if(c=='+')t.peek().v++;if(c=='-')t.peek().v--;if(c=='['&&t.peek().v==0){int i=1;while(i>0){t.i++;if(t.s[t.i]==']')i--;if(t.s[t.i]=='[')i++;}return;}if(c==']'&&t.peek().v!=0){int i=1;while(i>0){t.i--;if(t.s[t.i]==']')i++;if(t.s[t.i]=='[')i--;}return;}t.i++;}static char[]n(char[]a){String b="<^>[+-]";int q=a.length;for(int i=q-1;i>=0;i--){int j=b.indexOf(a[i]);if(j<6){a[i]=b.charAt(j+1);return a;}a[i]='<';}a=Arrays.copyOf(a,q+1);a[q]='<';return a;}public static void main(String[]a){List<T>z=new ArrayList<T>();char[]c={};while(true){T t=new T();t.s=c;if(b(c))z.add(t);c=n(c.clone());for(T u:z)try{s(u);if(u.h>0){z.remove(u);System.out.println(u.s);break;}}catch(Exception e){z.remove(u);break ;}}}static boolean b(char[]c){int i=0;for(char d:c){if(d=='[')i++;if(d==']')i--;if(i<0)return 0>0;}return i==0;}}

Brachylog → Problema de correspondencia posterior , 10 bytes

≜;?{~c}ᵐ\d

Pruébalo en línea!

Función que es un generador que genera todos los posibles problemas de correspondencia posterior para los cuales las soluciones de fuerza bruta finalmente se detienen. (Se sabe que las soluciones de fuerza bruta al problema de correspondencia posterior son una operación completa de Turing.) El enlace TIO contiene un encabezado que convierte un generador en un programa completo e imprime cada salida inmediatamente a medida que se genera (por lo tanto, cuando TIO mata el programa debido a que consume más de 60 segundos de tiempo de ejecución, la salida producida hasta ahora es visible).

Esto utiliza una formulación del problema en el que las cadenas se dan como cadenas de dígitos, no se permiten ceros a la izquierda excepto por 0sí mismo, no se aceptan soluciones al problema que involucra ceros a la izquierda, y una cadena de dígitos puede representarse como el número , o menos el número. Claramente, nada de esto tiene ningún impacto en la integridad del lenguaje de Turing (porque no hay necesidad de un problema de correspondencia posterior para usar el dígito cero).

Este programa funciona mediante la generación de todas las soluciones posibles a los problemas, y luego funciona hacia atrás para encontrar los programas originales que resuelven. Como tal, un programa individual puede salir muchas veces. No está claro si esto invalida la respuesta o no; tenga en cuenta que todos los programas de detención eventualmente saldrán al menos una vez (de hecho, infinitamente muchas veces, ya que cualquier programa que tenga soluciones tiene infinitas soluciones), y los programas que no se detengan nunca saldrán.

Explicación

≜;?{~c}ᵐ\d
≜           Brute-force all numbers:
 ;?           Pair {the number} with {itself}
   {  }ᵐ      For each pair element:
    ~c          Brute-force a partition of that element into substrings
        \     such that the two elements each have the same number of substrings
        \     and group together corresponding substrings
         d    and remove duplicated pairs {to produce a possible output}

"Púrpura sin E / S" en Ceilán, 662

import ceylon.language{l=variable,I=Integer,m=map,S=String}class M(S d){l value t=m{*d*.hash.indexed};l I a=0;l I b=0;l I i=0;I g(I j)=>t[j]else 0;value f=m{97->{a},98->{b},65->{g(a)},66->{g(b)},105->{i},49->{1}};value s=m{97->((I v)=>a=v),98->((I v)=>b=v),65->((I v)=>t=m{a->v,*t}),66->((I v)=>t=m{b->v,*t}),105->((I v)=>i=v)};I&I(I)x{throw Exception(d);}I h(I v)=>f[v]?.first else x;shared void p(){(s[g(i)]else x)(h(g(i+1))-h(g(i+2)));i+=3;}}shared void run(){value a='!'..'~';{S*}s=expand(loop<{S*}>{""}((g)=>{for(c in a)for(p in g)p+"``c``"}));l{M*}r={};for(p in s){r=[M(p),*r];for(e in r){try{e.p();}catch(x){print(x.message);r=r.filter(not(e.equals));}}}}

El púrpura es un lenguaje de una sola instrucción que se modifica a sí mismo y se le pidió que lo interpretara aquí . Como entrada y salida no son relevantes para esta tarea, me quita el osignificado del símbolo del intérprete, de tal manera que los símbolos (potencialmente) son sólo válidos a, b, A, B, iy 1(la última sólo para leer, no por escrito).

Pero como Purple se modifica a sí mismo (y usa su código fuente como datos), potencialmente también son útiles los programas que contienen otros caracteres, por lo que opté por permitir todos los caracteres ASCII imprimibles (sin espacios en blanco) en el código (otros podrían ser útil también, pero no se imprimen tan fácilmente).

(Puede modificar el intérprete para que, en su lugar, tome como una cadena de caracteres permitidos como argumento de la línea de comandos; cambie la línea comentada que se define a acontinuación. Luego, la longitud se convierte en 686 bytes).

Mi intérprete "paralelo" crea así todas las cadenas finitas de esos caracteres (en longitud creciente y orden lexicográfico) y prueba cada uno de ellos.

Purple se detendrá sin error cuando el comando que se leerá desde la cinta para su ejecución no sea válido, por lo tanto, no hay programas inválidos y muchos, muchos detenidos. (La mayoría se detiene incluso en el primer paso, solo algunos de los programas con duración 3 llegan al segundo paso (y se detendrán en ese momento), los primeros que no se detienen tienen longitud 6.

Creo que el primer programa que no se detiene en el orden probado por mi intérprete es aaaiaa, que en el primer paso establece el aregistro en 0 (que ya era), y el segundo y cada paso siguiente establece el puntero de instrucción nuevamente en 0, haciendo que se ejecute iaanuevamente.

Reutilicé parte del código escrito para mi intérprete de Purple "estándar" , pero debido a la eliminación de entrada y salida, mi intérprete paralelo se vuelve aún más corto que eso, al tiempo que incluye la lógica adicional para ejecutar múltiples programas a la vez.

Aquí hay una versión comentada y formateada:

// Find (enumerate) all halting programs in (a non-I/O subset of) Purple.
//
// Question:  /codegolf//q/51273/2338
// My answer: /codegolf//a/65820/2338

// We use a turing-complete subset of the Purple language,
// with input and output (i.e. the `o` command) removed.

import ceylon.language {
    l=variable,
    I=Integer,
    m=map,
    S=String
}

// an interpreting machine.
class M(S d) {
    // The memory tape, as a Map<Integer, Integer>.
    // We can't modify the map itself, but we
    // can replace it by a new map when update is needed.
    l value t = m {
        // It is initialized with the code converted to Integers.
        // We use `.hash` instead of `.integer` because it is shorter.
        *d*.hash.indexed
    };

    // three registers
    l I a = 0;
    l I b = 0;
    l I i = 0;

    // get value from memory
    I g(I j) =>
            t[j] else 0;

    // Map of "functions" for fetching values.
    // We wrap the values in iterable constructors for lazy evaluation
    //  – this is shorter than using (() => ...).
    // The keys are the (Unicode/ASCII) code points of the mapped
    // source code characters.
    value f = m {
        // a
        97 -> { a },
        // b
        98 -> { b },
        // A
        65 -> { g(a) },
        // B
        66 -> { g(b) },
        // i
        105 -> { i },
        // 1
        49 -> { 1 }
    };

    // Map of functions for "storing" results.
    // The values are void functions taking an Integer,
    // the keys are the ASCII/Unicode code points of the corresponding
    // source code characters.
    value s = m {
        // a
        97 -> ((I v) => a = v),
        // b
        98 -> ((I v) => b = v),
        // Modification of the memory works by replacing the map with
        // a new one.
        // This is certainly not runtime-efficient, but shorter than
        // importing ceylon.collections.HashMap.
        // A
        65 -> ((I v) => t = m { a->v, *t }),
        // B
        66 -> ((I v) => t = m { b->v, *t }),
        // i
        105 -> ((I v) => i = v)
    };


    // Exit the interpretation, throwing an exception with the machine's
    // source code as the message.  The return type is effectively `Nothing`,
    // but shorter (and fits the usages).
    I&I(I) x {
        throw Exception(d);
    }

    // accessor function for the f map
    I h(I v) =>
            f[v]?.first else x;

    // a single step
    shared void p() {
        (s[g(i)] else x)(h(g(i + 1)) - h(g(i + 2)));
        i += 3;
    }
}

// the main entry point
shared void run() {
    // the alphabet of "Purple without I/O".
    value a = '!'..'~';
    //// possible alternative to use a command line argument:
    // value a = process.arguments[0] else '!'..'~';

    // an iterable consisting of all programs in length + lexicographic order
    {S*} s =
            // `expand` creates a single iterable (of strings, in this case)
            // from an iterable of iterables (of strings).
             expand(
        // `loop` creates an iterable by applying the given function
        // on the previous item, repeatedly.
        // So here we start with the iterable of length-zero strings,
        // and in each iteration create an iterable of length `n+1` strings
        // by concatenating the length `n` strings with the alphabet members.
        loop<{S*}>{ "" }((g) =>
                {
                    for (c in a)
                        for (p in g)
                            p + "``c``"
                }));

    // This is a (variable) iterable of currently running machines.
    // Initially empty.
    l {M*} r = {};

    // iterate over all programs ...
    for(p in s) {
        // Create a machine with program `p`, include it
        //  in the list of running machines.
        //
        // We use a sequence constructor here instead of
        //  an iterable one (i.e. `r = {M(p, *r)}` to prevent
        // a stack overflow when accessing the deeply nested
        // lazy iterable.
        r = [M(p), *r];
        // iterate over all running machines ...
        for(e in r) {
            try {
                // run a step in machine e.
                e.p();
            } catch(x) {
                // exception means the machine halted.
                // print the program
                print(x.message);
                // remove the machine from the list for further execution
                r = r.filter(not(e.equals));
            }
        }
        // print(r.last);
    }
}

Cálculo combinador SK en Haskell , 249 bytes

data C=H|S|K|C:$C deriving(Eq,Show)
n(a:$b)=m a*n b
n a=m a
m S=1
m K=1
m(S:$a)=n a
m _=0
f H=[S,K,S:$H,K:$H,S:$H:$H]
f a=[S:$b:$c:$d|b:$d:$(c:$e)<-[a],d==e,n b*n c*n d>0]++[K:$a:$H|n a>0]++do b:$c<-[a];[d:$c|d<-f b]++[b:$d|n b>0,d<-f c]
l=H:(f=<<l)

Pruébalo en línea!

Cómo funciona

Las reglas de evaluación de llamada por valor para el cálculo del combinador SK son las siguientes:

(a) S xyz ↦ xz ( yz ), para x , y , z en forma normal;
(b) K xy ↦ x , para x , y en forma normal;
(c) xy ↦ x ′ y , si x ↦ x ′;
(d) xy ↦ xy ′, para x en forma normal, si y ↦ y ′ .

Como solo estamos interesados ​​en detener el comportamiento, ampliamos el lenguaje ligeramente al introducir un símbolo H que no está en forma normal, pero al que todas las formas normales "evalúan":

(a) S xyz ↦ xz ( yz ), para x , y , z en forma normal;
(b ') K x H ↦ x , para x en forma normal;
(c) xy ↦ x ′ y , si x ↦ x ′;
(d) xy ↦ xy ′, para x en forma normal, si y ↦ y ′ ;
(e) S ↦ H;
(f) K = H;
(g) SH ↦ H;
(h) KH ↦ H;
(i) SHH ↦ H.

Consideramos que cualquier aplicación H x es un error de tiempo de ejecución que debe tratarse como si fuera un bucle infinito, y ordenamos evaluaciones de modo que no se produzca H por (e) - (i) excepto en un contexto donde será ignorado (nivel superior, cualquier K x ☐, cualquier ignorado K☐, cualquier ignorado S x ☐ para x en forma normal, cualquier ignorado S☐H). De esta manera no afectamos el comportamiento de detención de los términos habituales que carecen de H.

Los beneficios de estas reglas modificadas son que cada término normalizable tiene una ruta de evaluación única a H, y que cada término tiene un número finito de posibles imágenes previas en ↦. Entonces, en lugar de utilizar el enfoque de cola de milano, podemos hacer una búsqueda mucho más eficiente de todas las rutas de evaluación inversa desde H.

ncomprueba si un término está en forma normal, fencuentra todas las preimágenes posibles de un término y les una lista infinita perezosa de términos normalizables producidos por la búsqueda de amplitud de H.