Le but de ce défi est de produire (éventuellement) tous les programmes d'arrêt possibles dans la langue de votre choix. Au début, cela peut sembler impossible, mais vous pouvez le faire avec un choix très attentif de l'ordre d'exécution.

Voici un diagramme ASCII pour illustrer cela. Laissez les colonnes représenter une numérotation de chaque programme possible (chaque programme est un nombre fini de symboles d'un alphabet fini). Que chaque ligne représente une étape singulière dans l'exécution de ce programme. An Xreprésente l'exécution effectuée par ce programme à ce pas de temps.

 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

Comme vous pouvez le constater, les programmes 2 et 4 ne s'arrêtent pas. Si vous les exécutiez un par un, votre contrôleur resterait coincé dans la boucle infinie qu'est le programme 2 et ne sortirait jamais les programmes 3 et au-delà.

Au lieu de cela, vous utilisez une approche en queue d'aronde . Les lettres représentent un ordre d'exécution possible pour les 26 premières étapes. Les *s sont des endroits où ce programme s'est arrêté et est sorti. Les .s sont des étapes qui n'ont pas encore été exécutées.

 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     .     .
     ∞     .     .

Exigences pour la langue cible

La langue cible (celle qui est interprétée en parallèle) doit être Turing-complete. À part cela, il peut s'agir de langue Turing-complete, y compris des sous-ensembles Turing-complete de langues beaucoup plus grandes. Vous êtes également libre d'interpréter des choses comme les règles du système d'étiquettes cycliques. Vous êtes également autorisé à créer un langage à tester, tant que vous pouvez montrer pourquoi il est Turing-complet.

Par exemple, si vous choisissez de tester le brainfuck, il est préférable de tester uniquement []-+<> sous ensemble, car l'entrée n'est pas prise en charge et la sortie est simplement jetée (voir ci-dessous).

En ce qui concerne le programme "contrôleur" (auquel vous jouez), il n'y a pas d'exigences particulières. Des restrictions linguistiques normales s'appliquent.

Comment créer une liste infinie de programmes

La majorité des langages de programmation peuvent être représentés comme une série de symboles d'un alphabet fini. Dans ce cas, il est relativement facile d'énumérer une liste de tous les programmes possibles par ordre de longueur croissante. L'alphabet que vous utilisez doit être représentatif des exigences de la langue cible. Dans la plupart des cas, il s'agit d'un fichier ASCII imprimable. Si votre langue prend en charge Unicode en tant que fonctionnalité supplémentaire, vous ne devez pas tester toutes les combinaisons possibles de caractères Unicode, uniquement ASCII. Si votre langue utilise uniquement, []-+<>ne testez pas les différentes combinaisons de caractères ASCII "commentaire". Des langues comme APL auraient leurs propres alphabets spéciaux.

Si votre langue est mieux décrite d'une manière non alphabétique, comme Fractran ou Turing Machines, il existe d'autres méthodes également valables pour générer une liste de tous les programmes valides possibles.

Interpréter une liste sans cesse croissante de programmes

L'élément clé de ce défi est d'écrire un interprète parallèle pour une liste croissante de programmes. Il y a quelques étapes de base pour cela:

• Ajouter un nombre fini de programmes à la liste
• Interprétez chaque programme de la liste individuellement pour une durée limitée. Cela peut être accompli en effectuant une étape d'instruction pour chacune. Enregistrez tous les états.
• Supprimer tous les programmes se terminant / générant des erreurs de la liste
• Sortie des programmes * correctement arrêtés
• Ajoutez d'autres programmes à la liste
• Simulez chaque programme à tour de rôle, reprenant l'exécution des anciens programmes là où ils s'étaient arrêtés
• Supprimer tous les programmes se terminant / générant des erreurs de la liste
• Sortie des programmes * correctement arrêtés
• répéter

* Vous ne devez sortir que les programmes qui s'arrêtent proprement. Cela signifie qu'aucune erreur de syntaxe ni exception non interceptée n'a été levée lors de l'exécution. Les programmes qui demandent une entrée doivent également être interrompus sans les sortir. Si un programme produit une sortie, vous ne devriez pas y mettre fin, jetez simplement la sortie.

Plus de règles

• Vous ne devez pas générer de nouveaux threads pour contenir les programmes testés, car cela décharge le travail de parallélisation sur le système d'exploitation hôte / autre logiciel.
• Modifier: pour fermer les futures failles potentielles, vous n'êtes pas autorisé à eval(ou toute fonction connexe) une partie du code du programme testé . Vous pouvez eval un bloc de code à partir du code de l'interpréteur. (La réponse BF-in-Python est toujours valide selon ces règles.)
• C'est du code-golf
• La langue dans laquelle vous écrivez votre soumission n'a pas besoin d'être la même que la langue que vous testez / produisez.
• Vous devez supposer que votre mémoire disponible est illimitée.
• Lorsque vous prouvez l'intégralité de Turing, vous pouvez supposer que l'entrée est codée en dur dans le programme et que la sortie peut être lue dans l'état interne du programme.
• Si votre programme sort lui-même, c'est probablement faux ou un polyglotte.

subleq OISC en Python, 317 269 ​​octets

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 programme subleq est une liste extensible d'entiers (p) et un pointeur d'instruction (i). Cette variante de subleq utilise l'adressage relatif, ce que la page de discussion wiki suggère est requis pour garantir l'exhaustivité avec des valeurs bornées. A chaque tick, l'opération p[i+p[i+1]]-=p[i+p[i]]est effectuée, puis i+=p[i+2]si le résultat de l'opération était <= 0, sinon i+=3. Si i est négatif, le programme s'arrête.

Cette implémentation teste chaque programme dont l'état initial est composé d'entiers non négatifs à un chiffre (0-9) avec un pointeur d'instruction initial 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 sortie est inversée, pour des raisons de golf. La spécification ci-dessus pourrait être reformulée à l'envers, mais ne correspondrait pas au code utilisé dans l'implémentation, donc je ne l'ai pas décrit de cette façon.

EDIT: Le premier programme qui présente une croissance simple et non bornée est 14283, ce qui diminue la valeur à l'emplacement de mémoire 6 et écrit un 0 explicite (par opposition au 0 implicite dans chaque cellule) dans la cellule négative suivante, tous les trois ticks.

Balise cyclique au niveau du bit dans CJam, 98 87 84 77 octets

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

Comme il s'agit d'une boucle infinie, vous ne pouvez pas directement tester cela dans l'interpréteur en ligne. Cependant, voici une version alternative qui lit le nombre d'itérations de STDIN pour que vous puissiez jouer avec. Pour tester le programme complet, vous aurez besoin de l'interpréteur Java .

BCT est une variante minimaliste des systèmes d'étiquettes cycliques . Un programme est défini par deux chaînes binaires: une liste (cyclique) d'instructions et un état initial. Pour me faciliter la vie lors de l'impression des programmes, j'ai défini ma propre notation: chacune des chaînes est donnée sous la forme d'un tableau d'entiers de type CJam, et le programme entier est entouré [[...]], par exemple

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

Je n'autorise pas non plus les états initiaux vides ou les listes d'instructions vides.

Les instructions dans BCT sont interprétées comme suit:

• Si l'instruction est 0, supprimez le bit de tête de l'état actuel.
• Si l'instruction est 1, lisez un autre bit de la liste d'instructions, appelez cela X. Si le bit de tête de l'état actuel est 1, ajoutez-le Xà l'état actuel, sinon ne faites rien.

Si l'état actuel devient vide, le programme s'arrête.

Les premiers programmes d'arrêt sont

[[[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 vous voulez en voir plus, consultez la version dans l'interpréteur en ligne que j'ai lié ci-dessus.

Explication

Voici comment fonctionne le code. Pour garder une trace de la queue d'aronde, nous aurons toujours un tableau sur la pile qui contient tous les programmes. Chaque programme est une paire d'une représentation interne du code de programme (similaire [[0 1 0] [1 0]]) ainsi que de l'état actuel du programme. Nous n'utiliserons que ce dernier pour effectuer le calcul, mais nous devrons nous souvenir du premier pour imprimer le programme une fois qu'il s'arrête. Cette liste de programmes est simplement initialisée dans un tableau vide avec L.

Le reste du code est une boucle infinie {...1}gqui ajoute d'abord un ou plusieurs programmes à cette liste et calcule une étape sur chaque programme. Les programmes qui s'arrêtent sont imprimés et supprimés de la liste.

J'énumère les programmes en comptant un nombre binaire. Le chiffre de tête est supprimé pour garantir que nous pouvons également obtenir tous les programmes avec des 0 de tête. Pour chacune de ces représentations binaires tronquées, je pousse un programme pour chaque division possible entre les instructions et l'état initial. Par exemple, si le compteur est actuellement à 42, sa représentation binaire est 101010. Nous nous débarrassons de l'amorce 1et poussons toutes les séparations non vides:

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

Puisque nous ne voulons pas d'instructions ou d'états vides, nous commençons le compteur à 4, ce qui donne [[[0] [0]]]. Cette énumération est effectuée par le code suivant:

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.

Le reste du code mappe un bloc sur la liste des programmes, qui effectue une étape du calcul BCT sur la seconde moitié de ces paires et supprime le programme s'il s'arrête:

)~     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 octets

Une solution relativement simple, car Brainfuck n'est pas la langue la plus difficile à écrire pour un interprète.

Cette implémentation de Brainfuck a le pointeur de données commençant à 0, autorisé uniquement à prendre une valeur positive (considéré comme une erreur s'il essaie d'aller à gauche de 0). Les cellules de données peuvent prendre des valeurs de 0 à 255 et se terminer. Les 5 instructions valides sont ><+[](- est inutile en raison de l'emballage).

Je pense que la sortie est tout à fait correcte maintenant, mais il est difficile d'être sûr qu'elle imprime toutes les solutions possibles, donc je peux en manquer.

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

Les premières sorties:

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

Et une liste des premiers 2000: http://pastebin.com/KQG8PVJn

Et enfin une liste des 2000 premières sorties avec []en elles: http://pastebin.com/iHWwJprs
(tout le reste est trivial tant qu'ils sont valides)

Notez que la sortie n'est pas dans un ordre trié, bien qu'elle puisse apparaître de cette façon pour beaucoup d'entre eux, car les programmes qui prennent plus de temps seront imprimés plus tard.

barres obliques en Python, 640 498 octets

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 programme slash est une chaîne, dans cet interpréteur limité aux caractères '/' et '\'. Dans cette implémentation, / est '1' et \ est '0' pour permettre une partie de golf avec l'utilisation de bin (x) de python. Lorsque l'interpréteur rencontre un \, le caractère suivant est sorti et les deux caractères sont supprimés. Lorsqu'il rencontre un /, il recherche les modèles de recherche et de remplacement comme / search / replace / y compris les caractères d'échappement dans les modèles (\\ représente \ et \ / représente /). Cette opération de remplacement est ensuite effectuée sur la chaîne de façon répétée jusqu'à ce que la chaîne de recherche ne soit plus présente, puis l'interprétation continue à nouveau depuis le début. Le programme s'arrête lorsqu'il est vide. Un programme sera tué s'il y a un ensemble non fermé de / motifs ou un \ sans caractère après.

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 à Java, 1,299 1,257 1,251 1,207 1,203 1,201 1,193 1,189 octets

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 → Problème de correspondance post , 10 octets

≜;?{~c}ᵐ\d

Essayez-le en ligne!

Fonction qui est un générateur qui génère tous les problèmes de correspondance possible pour lesquels les solutions de forçage brutal s'arrêtent finalement. (Les solutions de forçage brutal au problème de post-correspondance sont connues pour être une opération Turing-complete.) Le lien TIO contient un en-tête qui convertit un générateur en un programme complet et imprime chaque sortie immédiatement lors de sa génération (ainsi, lorsque TIO tue le programme en raison de la consommation de plus de 60 secondes de temps d'exécution, la sortie produite jusqu'à présent est visible).

Cela utilise une formulation du problème dans laquelle les chaînes sont données sous forme de chaînes de chiffres, les zéros non significatifs ne sont autorisés que pour 0lui-même, les solutions au problème impliquant les zéros non significatifs ne sont pas acceptées et une chaîne de chiffres peut être représentée soit par le nombre ou moins le nombre. De toute évidence, rien de tout cela n'a un impact sur l'intégralité de Turing de la langue (car il n'y a aucun besoin d'un problème de correspondance de poste pour utiliser le chiffre zéro).

Ce programme fonctionne en générant toutes les solutions possibles aux problèmes, puis en reculant pour trouver les programmes originaux qui sont résolus par eux. En tant que tel, un programme individuel peut être émis plusieurs fois. Il n'est pas clair si cela invalide la réponse ou non; notez que tous les programmes d'arrêt seront éventuellement sortis au moins une fois (en fait, infiniment de fois, comme tout programme qui a des solutions a une infinité de solutions), et les programmes sans arrêt ne seront jamais sortis.

Explication

≜;?{~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}

"Violet sans E / S" à Ceylan, 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));}}}}

Le violet est un langage à instruction unique auto-modifiable qui a été demandé d'interpréter ici . Étant donné que l'entrée et la sortie ne sont pas pertinentes pour cette tâche, j'ai supprimé leo le sens du symbole de l'interprète, de sorte que les (potentiellement) symboles valides sont juste a, b, A, B, iet 1(le dernier seulement pour la lecture, et non pour l' écriture).

Mais comme Purple se modifie automatiquement (et utilise son code source comme données), potentiellement aussi des programmes contenant d'autres que ces caractères sont utiles, j'ai donc choisi d'autoriser tous les caractères ASCII imprimables (non blancs) dans le code (d'autres pourraient être également utiles, mais ne sont pas aussi faciles à imprimer).

(Vous pouvez modifier l'interpréteur pour prendre à la place une chaîne de caractères autorisés comme argument de ligne de commande - changez la ligne commentée définissant aci-dessous. La longueur devient alors 686 octets.)

Mon interprète "parallèle" crée ainsi toutes les chaînes finies à partir de ces caractères (en longueur et en ordre lexicographique croissants) et essaie chacun d'eux.

Purple s'arrêtera sans erreur chaque fois que la commande à lire sur la bande pour exécution n'est pas valide - il n'y a donc pas de programmes invalides et beaucoup, beaucoup de programmes d'arrêt. (La plupart s'arrêtent même à la première étape, seuls certains des programmes de longueur 3 arrivent à la deuxième étape (et s'arrêteront alors), les premiers non-arrêtants ont la longueur 6.

Je pense que le tout premier programme sans interruption dans l'ordre essayé par mon interprète est aaaiaa, qui dans la première étape définit le aregistre à 0 (ce qu'il était déjà), et la deuxième et chaque étape suivante remet le pointeur d'instruction à 0, l'amenant à exécuteriaa nouveau.

J'ai réutilisé une partie du code écrit pour mon interprète de "standard" Purple , mais en raison de la suppression des entrées et des sorties, mon interprète parallèle devient même légèrement plus court que cela, tout en incluant la logique supplémentaire pour exécuter plusieurs programmes à la fois.

Voici une version commentée et formatée:

// 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);
    }
}

Calculateur combinatoire SK à Haskell , 249 octets

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)

Essayez-le en ligne!

Comment ça marche

Les règles d'évaluation de l'appel par valeur pour le calcul du combinateur SK sont les suivantes:

(a) S xyz ↦ xz ( yz ), pour x , y , z sous forme normale;
(b) K xy ↦ x , pour x , y sous forme normale;
(c) xy ↦ x ′ y , si x ↦ x ′;
(d) xy ↦ xy ′, pour x sous forme normale, si y ↦ y ′ .

Comme nous ne souhaitons que stopper le comportement, nous développons légèrement le langage en introduisant un symbole H qui n'est pas sous forme normale, mais auquel toutes les formes normales «évaluent»:

(a) S xyz ↦ xz ( yz ), pour x , y , z sous forme normale;
(b ′) K x H ↦ x , pour x sous forme normale;
(c) xy ↦ x ′ y , si x ↦ x ′;
(d) xy ↦ xy ′, pour x sous forme normale, si y ↦ y ′ ;
(e) S ↦ H;
(f) K ↦ H;
(g) SH ↦ H;
(h) KH ↦ H;
(i) SHH ↦ H.

Nous considérons toute application H x comme une erreur d'exécution à traiter comme si elle était une boucle infinie, et nous ordonnons des évaluations telles qu'aucun H ne soit produit par (e) - (i) sauf dans un contexte où il sera ignoré (niveau supérieur, tout K x ☐, tout K☐ ignoré, tout S x ☐ ignoré pour x sous forme normale, tout S☐H ignoré). De cette façon, nous n'affectons pas le comportement d'arrêt des termes habituels dépourvus de H.

Les avantages de ces règles modifiées sont que chaque terme normalisable a un chemin d'évaluation unique vers H, et que chaque terme a un nombre fini de préimages possibles sous ↦. Ainsi, au lieu d'utiliser l'approche en queue d'aronde, nous pouvons faire une recherche en largeur beaucoup plus efficace en premier de tous les chemins d'évaluation inverse de H.

nvérifie si un terme est sous forme normale, ftrouve toutes les pré-images possibles d'un terme et lest une liste infinie paresseuse de termes normalisables produite par une recherche en largeur de H.