Ziel dieser Herausforderung ist es, (eventuell) jedes mögliche Stopp-Programm in einer Sprache Ihrer Wahl auszugeben . Das mag zunächst unmöglich klingen, aber Sie können dies mit einer sehr sorgfältigen Auswahl der Ausführungsreihenfolge erreichen.

Unten sehen Sie ein ASCII-Diagramm, um dies zu veranschaulichen. Lassen Sie die Spalten eine Nummerierung jedes möglichen Programms darstellen (jedes Programm ist eine endliche Anzahl von Symbolen aus einem endlichen Alphabet). Es sei jede Zeile ein einzelner Schritt bei der Ausführung dieses Programms. Eine XDarstellung der Ausführung, die von diesem Programm zu diesem Zeitpunkt ausgeführt wurde.

 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

Wie Sie sehen, halten die Programme 2 und 4 nicht an. Wenn Sie sie einzeln ausführen, bleibt Ihr Controller in der Endlosschleife von Programm 2 stecken und gibt niemals Programme ab 3 aus.

Stattdessen verwenden Sie einen Verzahnungsansatz . Die Buchstaben stellen eine mögliche Ausführungsreihenfolge für die ersten 26 Schritte dar. Die *s sind Stellen, an denen das Programm angehalten und ausgegeben wurde. Die .s sind Schritte, die noch nicht ausgeführt wurden.

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

Anforderungen an die Zielsprache

Die Zielsprache (die parallel gedolmetscht wird) muss Turing-vollständig sein. Ansonsten kann es sich um jede Sprache handeln, die Turing-vollständig ist, einschließlich Turing-vollständiger Untergruppen von viel größeren Sprachen. Sie können auch zyklische Tag-Systemregeln interpretieren. Sie können auch eine zu testende Sprache erstellen, sofern Sie nachweisen können, warum Turing vollständig ist.

Wenn Sie beispielsweise Brainfuck testen möchten, ist es am besten, nur die []-+<>Teilmenge zu testen , da die Eingabe nicht unterstützt wird und die Ausgabe einfach weggeworfen wird (siehe unten).

Wenn es um das "Controller" -Programm (auf dem Sie Golf spielen) geht, gibt es keine besonderen Anforderungen. Es gelten die normalen Sprachbeschränkungen.

So erstellen Sie eine unendliche Liste von Programmen

Die Mehrheit der Programmiersprachen kann als eine Reihe von Symbolen aus einem endlichen Alphabet dargestellt werden. In diesem Fall ist es relativ einfach, eine Liste aller möglichen Programme in aufsteigender Reihenfolge aufzulisten. Das von Ihnen verwendete Alphabet sollte für die Anforderungen der Zielsprache repräsentativ sein . In den meisten Fällen ist dies druckbares ASCII. Wenn Ihre Sprache zusätzlich Unicode unterstützt, sollten Sie nicht jede mögliche Kombination von Unicode-Zeichen testen, sondern nur ASCII. Wenn Ihre Sprache nur verwendet []-+<>, testen Sie die verschiedenen Kombinationen von "Kommentar" -ASCII-Zeichen nicht. Sprachen wie APL hätten ihre eigenen speziellen Alphabete.

Wenn Ihre Sprache nicht alphabetisch beschrieben werden kann, wie z. B. Fractran oder Turing Machines, gibt es andere gleichermaßen gültige Methoden, um eine Liste aller möglichen gültigen Programme zu erstellen.

Interpretation einer ständig wachsenden Liste von Programmen

Der Schlüssel zu dieser Herausforderung besteht darin, einen parallelen Interpreter für eine wachsende Liste von Programmen zu schreiben. Hierfür gibt es einige grundlegende Schritte:

• Fügen Sie der Liste eine endliche Anzahl von Programmen hinzu
• Interpretieren Sie jedes Programm auf der Liste für einen begrenzten Zeitraum einzeln. Dies kann erreicht werden, indem für jeden Befehl ein Schritt ausgeführt wird. Speichern Sie alle Zustände.
• Entfernen Sie alle terminierenden / fehlerauslösenden Programme aus der Liste
• Die sauber gestoppten * Programme ausgeben
• Fügen Sie der Liste weitere Programme hinzu
• Simulieren Sie nacheinander jedes Programm und nehmen Sie die Ausführung älterer Programme dort auf, wo sie aufgehört haben
• Entfernen Sie alle terminierenden / fehlerauslösenden Programme aus der Liste
• Die sauber gestoppten * Programme ausgeben
• wiederholen

* Sie sollten nur Programme ausgeben, die sauber anhalten. Dies bedeutet, dass während der Ausführung keine Syntaxfehler oder nicht erfassten Ausnahmen aufgetreten sind. Programme, die zur Eingabe auffordern, sollten ebenfalls beendet werden, ohne sie auszugeben. Wenn ein Programm eine Ausgabe erzeugt, sollten Sie es nicht beenden, sondern einfach die Ausgabe wegwerfen.

Weitere Regeln

• Sie dürfen keine neuen Threads erzeugen, um die getesteten Programme zu enthalten, da dies die Parallelisierungsarbeit auf das Host-Betriebssystem / andere Software verlagert.
• Bearbeiten: Um potenzielle zukünftige Lücken zu schließen, dürfen Sie keinen evalTeil des Codes des getesteten Programms (oder einer verwandten Funktion) . Sie können eval einen Codeblock aus dem Interpretercode erstellen. (Die BF-in-Python-Antwort ist nach diesen Regeln weiterhin gültig.)
• Das ist Code-Golf
• Die Sprache, in der Sie Ihren Beitrag verfassen, muss nicht mit der Sprache übereinstimmen, die Sie testen / ausgeben.
• Sie sollten davon ausgehen, dass Ihr verfügbarer Speicher unbegrenzt ist.
• Wenn Sie die Turing-Vollständigkeit nachweisen, können Sie davon ausgehen, dass die Eingabe fest im Programm codiert ist und die Ausgabe aus dem internen Status des Programms gelesen werden kann.
• Wenn Ihr Programm sich selbst ausgibt, ist es wahrscheinlich falsch oder polyglott.

subleq OISC in 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

Ein subleq-Programm ist eine erweiterbare Liste von ganzen Zahlen (p) und ein Befehlszeiger (i). Diese Subleq-Variante verwendet eine relative Adressierung, die laut Wiki-Diskussionsseite erforderlich ist, um die Vollständigkeit mit begrenzten Werten zu gewährleisten. Bei jedem Häkchen wird die Operation p[i+p[i+1]]-=p[i+p[i]]ausgeführt i+=p[i+2], andernfalls, wenn das Operationsergebnis <= 0 war i+=3. Wenn ich jemals negativ ist, stoppt das Programm.

Diese Implementierung testet jedes Programm, dessen Anfangszustand aus einstelligen nicht negativen ganzen Zahlen (0-9) mit einem Anfangsanweisungszeiger von 0 besteht.

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

Die Ausgabe ist aus Golfgründen umgekehrt. Die obige Spezifikation könnte in umgekehrter Reihenfolge angepasst werden, würde dann aber nicht mit dem in der Implementierung verwendeten Code übereinstimmen, sodass ich sie nicht so beschrieben habe.

BEARBEITEN: Das erste Programm, das ein einfaches, unbegrenztes Wachstum aufweist, ist 14283, das den Wert an Speicherstelle 6 dekrementiert und alle drei Ticks eine explizite 0 (im Gegensatz zur impliziten 0 in jeder Zelle) in die nächste negative Zelle schreibt.

Bitweises zyklisches Tag in CJam, 98 87 84 77 Byte

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

Da dies eine Endlosschleife ist, können Sie dies nicht direkt im Online-Interpreter testen. Allerdings ist hier eine alternative Version , die die Anzahl der Iterationen von STDIN liest für Dich zu spielen , um. Zum Testen des vollständigen Programms benötigen Sie den Java-Interpreter .

BCT ist eine minimalistische Variante von Cyclic Tag Systems . Ein Programm wird durch zwei binäre Zeichenfolgen definiert: eine (zyklische) Anweisungsliste und einen Anfangszustand. Um das Drucken der Programme zu vereinfachen, habe ich meine eigene Notation definiert: Jede der Zeichenfolgen wird als ein Array von Ganzzahlen im CJam-Stil angegeben, und das gesamte Programm ist [[...]]z

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

Ich lasse auch leere Anfangszustände oder leere Anweisungslisten nicht zu.

Anweisungen in BCT werden wie folgt interpretiert:

• Wenn der Befehl lautet 0, entfernen Sie das führende Bit aus dem aktuellen Status.
• Wenn die Anweisung lautet 1, lesen Sie ein weiteres Bit aus der Anweisungsliste und nennen Sie esX . Wenn das führende Bit des aktuellen Status ist 1, hängen Sie es Xan den aktuellen Status an, andernfalls tun Sie nichts.

Wenn der aktuelle Status jemals leer wird, wird das Programm angehalten.

Die ersten Stoppprogramme sind

[[[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]]]

Wenn Sie mehr sehen möchten, lesen Sie die Version in dem Online-Interpreter, den ich oben verlinkt habe.

Erläuterung

So funktioniert der Code. Um den Überblick über die Verzahnung zu behalten, haben wir immer ein Array auf dem Stapel, das alle Programme enthält. Jedes Programm ist ein Paar einer internen Darstellung des Programmcodes (ähnlich [[0 1 0] [1 0]]) sowie des aktuellen Status des Programms. Wir werden nur die letztere verwenden, um die Berechnung durchzuführen, aber wir müssen uns die erstere merken, um das Programm zu drucken, sobald es anhält. Diese Programmliste wird einfach mit einem leeren Array initialisiertL .

Der Rest des Codes ist eine Endlosschleife, {...1}gdie dieser Liste zunächst ein oder mehrere Programme hinzufügt und für jedes Programm einen Schritt berechnet. Programme, die anhalten, werden gedruckt und aus der Liste entfernt.

Ich zähle die Programme durch Aufzählen einer Binärzahl auf. Die führende Ziffer wird entfernt, um sicherzustellen, dass wir auch alle Programme mit führenden Nullen erhalten können. Für jede solche verkürzte Binärdarstellung schiebe ich ein Programm für jede mögliche Aufteilung zwischen Anweisungen und Anfangszustand. Befindet sich der Zähler aktuell auf 42, ist seine Binärdarstellung 101010. Wir werden das Führen los 1und schieben alle nicht leeren Teilungen:

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

Da wir keine leeren Anweisungen oder Zustände wollen, starten wir den Zähler bei 4, was ergibt [[[0] [0]]]. Diese Aufzählung erfolgt mit folgendem Code:

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.

Der Rest des Codes ordnet der Programmliste einen Block zu, der einen Schritt der BCT-Berechnung für die zweite Hälfte dieser Paare ausführt und das Programm entfernt, wenn es anhält:

)~     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 in Python, 567 Bytes

Eine relativ einfache Lösung, da Brainfuck kaum die schwierigste Sprache ist, für die ein Dolmetscher geschrieben werden kann.

Bei dieser Implementierung von Brainfuck darf der Datenzeiger ab 0 nur einen positiven Wert annehmen (wird als Fehler gewertet, wenn versucht wird, nach links von 0 zu springen). Die Datenzellen können Werte von 0 bis 255 annehmen und umbrechen. Die 5 gültigen Anweisungen sind ><+[]( -ist aufgrund der Verpackung nicht erforderlich).

Ich denke, die Ausgabe ist jetzt in Ordnung, es ist jedoch schwierig, sicherzugehen, dass alle möglichen Lösungen gedruckt werden, sodass mir möglicherweise einige fehlen.

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

Die ersten paar Ergebnisse:

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

Und eine Liste der ersten 2000: http://pastebin.com/KQG8PVJn

Und zum Schluss eine Liste der ersten 2000 Ausgaben mit []darin: http://pastebin.com/iHWwJprs
(alle anderen sind trivial, solange sie gültig sind)

Beachten Sie, dass die Ausgabe nicht in einer sortierten Reihenfolge erfolgt, obwohl dies bei vielen von ihnen der Fall sein kann, da die länger dauernden Programme später gedruckt werden.

Schrägstriche in 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////

Ein Schrägstrich-Programm ist eine Zeichenfolge, die in diesem Interpreter auf die Zeichen '/' und '\' beschränkt ist. In dieser Implementierung ist / '1' und \ '0', um unter Verwendung von Pythons bin (x) etwas Golf zu spielen. Wenn der Interpreter auf ein \ stößt, wird das nächste Zeichen ausgegeben und beide Zeichen werden entfernt. Wenn es auf ein / stößt, sucht es nach Such- und Ersetzungsmustern als / search / replace /, wobei es maskierte Zeichen in die Muster einschließt (\\ steht für \ und \ / steht für /). Diese Ersetzungsoperation wird dann wiederholt an der Zeichenfolge ausgeführt, bis die Suchzeichenfolge nicht mehr vorhanden ist, und dann wird die Interpretation von vorne fortgesetzt. Das Programm wird angehalten, wenn es leer ist. Ein Programm wird abgebrochen, wenn eine nicht geschlossene Menge von / Mustern oder ein \ ohne Zeichen dahinter steht.

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 in 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 → Korrespondenzproblem posten , 10 Bytes

≜;?{~c}ᵐ\d

Probieren Sie es online!

Funktion, die als Generator alle möglichen Post-Korrespondenz-Probleme generiert, für die brachiale Lösungen möglicherweise nicht mehr funktionieren. (Brute-Forcing-Lösungen für das Post-Korrespondenz-Problem sind bekanntermaßen eine Turing-Complete-Operation.) Die TIO-Verknüpfung enthält einen Header, der einen Generator in ein vollständiges Programm umwandelt und jede Ausgabe sofort druckt, wenn sie generiert wird (also wenn TIO beendet wird) Da das Programm mehr als 60 Sekunden Ausführungszeit in Anspruch nimmt, ist die bisher erzeugte Ausgabe sichtbar.

Hierbei wird eine Formulierung des Problems verwendet, bei der die Zeichenfolgen als Ziffernfolgen angegeben werden, führende Nullen nur für sich 0selbst zulässig sind , Lösungen für das Problem mit führenden Nullen nicht akzeptiert werden und eine Ziffernfolge als Zahl dargestellt werden kann oder minus der Zahl. Dies hat natürlich keine Auswirkung auf die Vollständigkeit der Sprache (da für die Verwendung der Ziffer Null überhaupt kein Post-Korrespondenz-Problem erforderlich ist).

Dieses Programm generiert alle möglichen Lösungen für Probleme und arbeitet dann rückwärts, um die ursprünglichen Programme zu finden, die von ihnen gelöst wurden. Als solches kann ein einzelnes Programm viele Male ausgegeben werden. Es ist unklar, ob dies die Antwort ungültig macht oder nicht. Beachten Sie, dass alle angehaltenen Programme mindestens einmal ausgegeben werden (in der Tat unendlich oft, da jedes Programm, das Lösungen enthält, unendlich viele Lösungen hat), und dass nicht angehaltene Programme niemals ausgegeben werden.

Erläuterung

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

"Lila ohne E / A" in Ceylon, 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));}}}}

Lila ist eine sich selbst modifizierende Ein-Instruktions-Sprache, die hier interpretiert werden sollte . Als Ein- und Ausgabe für diese Aufgabe nicht relevant ist, entfernte ich die oBedeutung des Symbols aus dem Dolmetscher, so dass die (potentiell) gültigen Symbole sind nur a, b, A, B, iund 1(der letzte nur zum Lesen, nicht zum Schreiben).

Da Purple sich jedoch selbst modifiziert (und seinen Quellcode als Daten verwendet), sind möglicherweise auch Programme nützlich, die andere Zeichen als diese enthalten. Daher habe ich mich dafür entschieden, alle druckbaren ASCII-Zeichen (ohne Leerzeichen) im Code zuzulassen (möglicherweise auch andere) nützlich, aber nicht so einfach zu drucken).

(Sie können den Interpreter so ändern, dass er stattdessen eine Zeichenfolge zulässiger Zeichen als Befehlszeilenargument verwendet - wechseln Sie die aunten definierte Kommentarzeile . Die Länge wird dann zu 686 Byte.)

Mein "paralleler" Interpreter erzeugt daher alle endlichen Zeichenfolgen aus diesen Zeichen (in zunehmender Länge und lexikografischer Reihenfolge) und probiert jede einzelne aus.

Purple stoppt immer dann fehlerfrei, wenn der Befehl, der zur Ausführung vom Band gelesen werden soll, ungültig ist - daher gibt es keine ungültigen und viele, viele haltende Programme. (Die meisten halten bereits im ersten Schritt an, nur einige der Programme mit der Länge 3 kommen zum zweiten Schritt (und halten dann an), die ersten, die nicht anhalten, haben die Länge 6.

Ich denke, das allererste Non-Stop-Programm in der Reihenfolge, die mein Interpreter ausprobiert, ist das aaaiaa, das im ersten Schritt das setzta Register auf 0 setzt (was es bereits war), und der zweite und jeder folgende Schritt setzt den Befehlszeiger zurück auf 0. veranlassen, dass es iaaerneut ausgeführt wird.

Ich habe einen Teil des Codes, der für meinen Interpreter von "Standard" Purple geschrieben wurde, wieder verwendet , , aber aufgrund des Wegfalls von Eingabe und Ausgabe wird mein paralleler Interpreter sogar etwas kürzer, während die zusätzliche Logik zum gleichzeitigen Ausführen mehrerer Programme enthalten ist.

Hier ist eine kommentierte und formatierte Version:

// Find (enumerate) all halting programs in (a non-I/O subset of) Purple.
//
// Question:  https://codegolf.stackexchange.com/q/51273/2338
// My answer: https://codegolf.stackexchange.com/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);
    }
}

SK-Kombinator-Kalkül in 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)

Probieren Sie es online!

Wie es funktioniert

Die Call-by-Value-Bewertungsregeln für die SK-Kombinatorrechnung lauten wie folgt:

(a) S xyz ≤ xz ( yz ) für x , y , z in normaler Form;
(b) K xy ↦ x für x , y in normaler Form;
(c) xy ≤ x ' y , wenn x ≤ x ' ist;
(d) xy ↦ xy 'für x in normaler Form, wenn y ↦ y' .

Da wir nur daran interessiert sind, das Verhalten zu stoppen, erweitern wir die Sprache geringfügig, indem wir ein Symbol H einfügen, das nicht in normaler Form vorliegt, für das jedoch alle normalen Formen „auswerten“:

(a) S xyz ≤ xz ( yz ), z x , y , z in normaler Form;
(b ′) K x H ≤ x für x in normaler Form;
(c) xy ≤ x ' y , wenn x ≤ x ' ist;
(d) xy ≤ xy 'für x in normaler Form, wenn y ≤ y' ist ;
(e) SH;
(f) K ≤ H;
(g) SH ≤ H;
(h) KH ≤ H;
(i) SHH ↦ H.

Wir betrachten jede Anwendung H x als Laufzeitfehler und behandeln sie als Endlosschleife. Wir ordnen Auswertungen so an, dass durch (e) - (i) kein H erzeugt wird, außer in einem Kontext, in dem es auftreten wird ignoriert (oberste Ebene, beliebiges K x ☐, beliebiges ignoriertes K☐, beliebiges ignoriertes S x x für x in normaler Form, beliebiges ignoriertes S☐H). Auf diese Weise beeinflussen wir nicht das Stoppverhalten der üblichen Begriffe, denen H fehlt.

Die Vorteile dieser modifizierten Regeln sind, dass jeder normalisierbare Term einen eindeutigen Bewertungspfad zu H hat und dass jeder Term eine endliche Anzahl möglicher Vorbilder unter ↦ hat. Anstatt also den Schwalbenschwanz-Ansatz zu verwenden, können wir alle umgekehrten Auswertungspfade von H weitaus effizienter als bisher durchsuchen.

nprüft, ob ein Begriff in normaler Form vorliegt, ffindet alle möglichen Vorbilder eines Begriffs undl ist eine träge unendliche Liste normalisierbarer Begriffe, die bei der Breitensuche von H erstellt wurden.