Celem tego wyzwania jest (ostatecznie) wygenerowanie każdego możliwego programu zatrzymania w wybranym języku. Na początku może się to wydawać niemożliwe, ale możesz to zrobić, bardzo ostrożnie wybierając kolejność wykonywania.

Poniżej znajduje się schemat ASCII ilustrujący to. Niech kolumny reprezentują numerację każdego możliwego programu (każdy program jest skończoną liczbą symboli ze skończonego alfabetu). Niech każdy wiersz reprezentuje pojedynczy krok w wykonaniu tego programu. XStanowią wykonanie wykonaniu tego programu w tym czasie kroku.

 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

Jak widać, programy 2 i 4 się nie zatrzymują. Jeśli miałbyś je wykonać pojedynczo, twój kontroler utknąłby w nieskończonej pętli, którą jest program 2 i nigdy nie wyprowadzałby programów 3 i późniejszych.

Zamiast tego stosujesz podejście typu „ jaskółczy ogon” . Litery przedstawiają możliwą kolejność wykonania dla pierwszych 26 kroków. Są *to miejsca, w których program został zatrzymany i jest generowany. Są .to kroki, które nie zostały jeszcze wykonane.

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

Wymagania dotyczące języka docelowego

Język docelowy (ten interpretowany równolegle) musi być kompletny w Turingu. Poza tym może to być dowolny język, który jest kompletny z Turinga, w tym kompletne podzbiory Turinga dla znacznie większych języków. Możesz także dowolnie interpretować takie zasady, jak reguły systemu tagów cyklicznych. Możesz także utworzyć język do testowania, o ile możesz pokazać, dlaczego jest on kompletny w Turingu.

Na przykład, jeśli zdecydujesz się na test pieprzenia mózgu, najlepiej przetestować tylko []-+<>podzbiór, ponieważ dane wejściowe nie są obsługiwane, a dane wyjściowe są po prostu wyrzucane (patrz poniżej).

Jeśli chodzi o program „kontrolera” (w który grasz), nie ma specjalnych wymagań. Obowiązują normalne ograniczenia językowe.

Jak stworzyć nieskończoną listę programów

Większość języków programowania może być reprezentowana jako seria symboli ze skończonego alfabetu. W takim przypadku stosunkowo łatwo jest wymienić listę każdego możliwego programu w kolejności rosnącej długości. Używany alfabet powinien być reprezentatywny dla wymagań języka docelowego. W większości przypadków jest to drukowany kod ASCII. Jeśli twój język obsługuje Unicode jako dodatkową funkcję, nie powinieneś testować każdej możliwej kombinacji znaków Unicode, tylko ASCII. Jeśli używasz tylko Twojego języka []-+<>, nie testuj różnych kombinacji „komentujących” znaków ASCII. Języki takie jak APL miałyby własne specjalne alfabety.

Jeśli Twój język najlepiej jest opisać w jakiś sposób niealfabetyczny, np. Fractran lub Turing Machines, istnieją inne równie poprawne metody generowania listy wszystkich możliwych prawidłowych programów.

Interpretacja stale rosnącej listy programów

Kluczową częścią tego wyzwania jest napisanie równoległego interpretera dla rosnącej listy programów. Oto kilka podstawowych kroków:

• Dodaj skończoną liczbę programów do listy
• Interpretuj każdy program na liście indywidualnie przez określony czas. Można to osiągnąć, wykonując jeden krok instrukcji dla każdego. Zapisz wszystkie stany.
• Usuń wszystkie programy kończące / zgłaszające błędy z listy
• Wyjście czysto zatrzymanych * programów
• Dodaj więcej programów do listy
• Symuluj kolejno każdy program, pobierając wykonanie starszych programów tam, gdzie je przerwał
• Usuń wszystkie programy kończące / zgłaszające błędy z listy
• Wyjście czysto zatrzymanych * programów
• powtarzać

* Powinieneś wypisywać tylko programy, które zatrzymują się w sposób czysty. Oznacza to, że podczas wykonywania nie zgłoszono żadnych błędów składniowych ani nieprzechwyconych wyjątków. Programy, które proszą o wejście, również powinny zostać zakończone bez ich wysyłania. Jeśli program produkuje dane wyjściowe, nie powinieneś ich kończyć, po prostu wyrzuć dane wyjściowe.

Więcej zasad

• Nie wolno odradzać nowych wątków zawierających testowane programy, ponieważ odciąża to pracę równoległą do systemu operacyjnego hosta / innego oprogramowania.
• Edycja: Aby zamknąć potencjalne przyszłe luki, nie możesz eval(ani żadnej pokrewnej funkcji) części kodu testowanego programu. Państwo może eval bloku kodu z kodem tłumacza. (Odpowiedź BF-in-Python jest nadal ważna zgodnie z tymi zasadami).
• To jest golf golfowy
• Język, w którym piszesz zgłoszenie , nie musi być taki sam, jak język, w którym testujesz / publikujesz.
• Należy założyć, że dostępna pamięć jest nieograniczona.
• Udowadniając kompletność Turinga, możesz założyć, że dane wejściowe są zakodowane na stałe w programie, a dane wyjściowe można odczytać ze stanu wewnętrznego programu.
• Jeśli twój program sam się wypisuje, prawdopodobnie jest to błąd lub poliglota.

subleq OISC w Pythonie, 317 269 ​​bajtów

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

Program podrzędny jest rozszerzalną listą liczb całkowitych (p) i wskaźnika instrukcji (i). Ten wariant subleq wykorzystuje adresowanie względne, które według strony dyskusji wiki jest wymagane do uzyskania kompletności z ograniczonymi wartościami. W każdym tiku operacja p[i+p[i+1]]-=p[i+p[i]]jest wykonywana, a i+=p[i+2]jeśli wynik operacji był <= 0, w przeciwnym razie i+=3. Jeśli i jest kiedykolwiek ujemne, program zatrzymuje się.

Ta implementacja testuje każdy program, którego stan początkowy składa się z jednocyfrowych liczb całkowitych nieujemnych (0–9) ze wskaźnikiem instrukcji początkowej równym 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

Wyjście jest odwrócone z powodów golfowych. Powyższa specyfikacja może być przekształcona w odwrotnej kolejności, ale wtedy nie będzie pasować do kodu użytego w implementacji, więc nie opisałem tego w ten sposób.

EDYCJA: Pierwszym programem, który wykazuje prosty nieograniczony wzrost, jest 14283, który zmniejsza wartość w miejscu pamięci 6 i zapisuje wyraźne 0 (w przeciwieństwie do niejawnego 0 w każdej komórce) do następnej ujemnej komórki, co trzy tiki.

Bitowy cykliczny znacznik w CJam, 98 87 84 77 bajtów

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

Ponieważ jest to nieskończona pętla, nie można tego bezpośrednio przetestować w tłumaczu online. Jednak tutaj jest alternatywna wersja, która odczytuje liczbę iteracji ze STDIN, z którymi możesz się bawić. Aby przetestować pełny program, potrzebujesz interpretera Java .

BCT to minimalistyczna odmiana cyklicznych systemów tagów . Program jest zdefiniowany przez dwa ciągi binarne: (cykliczną) listę instrukcji i stan początkowy. Aby ułatwić sobie życie podczas drukowania programów, zdefiniowałem własną notację: każdy ciąg jest podany jako tablica liczb całkowitych w stylu CJam, a cały program jest otoczony [[...]], np.

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

Nie zezwalam również na puste stany początkowe lub puste listy instrukcji.

Instrukcje w BCT są interpretowane w następujący sposób:

• Jeśli instrukcja jest 0, usuń bit wiodący z bieżącego stanu.
• Jeśli instrukcja jest 1, przeczytaj kolejny bit z listy instrukcji, wywołaj to X. Jeśli bitem wiodącym z bieżącego stanu jest 1, dołącz Xdo bieżącego stanu, w przeciwnym razie nic nie rób.

Jeśli aktualny stan zostanie kiedykolwiek pusty, program się zatrzyma.

Pierwsze kilka programów zatrzymujących to

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

Jeśli chcesz zobaczyć więcej, sprawdź wersję w internetowym tłumaczu, który zamieściłem powyżej.

Wyjaśnienie

Oto jak działa kod. Aby śledzić dovetailing, zawsze będziemy mieć stos na tablicy zawierającej wszystkie programy. Każdy program jest parą wewnętrznej reprezentacji kodu programu (podobnego [[0 1 0] [1 0]]), a także bieżącego stanu programu. Tego drugiego użyjemy tylko do obliczeń, ale musimy pamiętać o tym pierwszym, aby wydrukować program, gdy się zatrzyma. Ta lista programów jest po prostu inicjowana do pustej tablicy przy pomocy L.

Reszta kodu to nieskończona pętla, {...1}gktóra najpierw dodaje jeden lub więcej programów do tej listy i oblicza jeden krok dla każdego programu. Zatrzymane programy są drukowane i usuwane z listy.

Wyliczam programy, licząc liczbę binarną. Cyfra wiodąca jest usuwana, abyśmy mogli uzyskać wszystkie programy z wiodącymi zerami. Dla każdej takiej obciętej reprezentacji binarnej pcham jeden program dla każdego możliwego podziału między instrukcjami i stanem początkowym. Np. Jeśli licznik jest obecnie w 42, jego reprezentacja binarna to 101010. Pozbywamy się wiodących 1i wypychamy wszystkie niepuste podziały:

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

Ponieważ nie chcemy pustych instrukcji ani stanów, licznik rozpoczynamy od 4, co daje [[[0] [0]]]. To wyliczenie odbywa się za pomocą następującego kodu:

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.

Reszta kodu odwzorowuje blok na listę programów, która wykonuje jeden krok obliczeń BCT na drugiej połowie tych par i usuwa program, jeśli się zatrzyma:

)~     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 bajtów

Stosunkowo proste rozwiązanie, ponieważ Brainfuck nie jest najtrudniejszym językiem do napisania tłumacza.

Ta implementacja Brainfuck ma wskaźnik danych zaczynający się od 0, może przyjmować tylko wartość dodatnią (uważany za błąd, jeśli próbuje przejść na lewo od 0). Komórki danych mogą przyjmować wartości od 0 do 255 i zawijać. 5 prawidłowych instrukcji jest ><+[]( -jest niepotrzebnych ze względu na opakowanie).

Myślę, że dane wyjściowe są teraz poprawne, jednak trudno jest mieć pewność, że wypisuje wszystkie możliwe rozwiązania, więc może mi brakować niektórych.

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

Pierwsze kilka wyjść:

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

I lista pierwszych 2000: http://pastebin.com/KQG8PVJn

I wreszcie lista pierwszych 2000 wyników z []nimi: http://pastebin.com/iHWwJprs
(cała reszta jest banalna, o ile są ważne)

Zauważ, że dane wyjściowe nie są posortowane, chociaż może się tak wydawać dla wielu z nich, ponieważ programy, które trwają dłużej, zostaną wydrukowane później.

ukośniki w Pythonie, 640 498 bajtów

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////

Program ukośnik jest ciągiem znaków, w tym tłumaczu ograniczony do znaków „/” i „\”. W tej implementacji / to „1”, a \ to „0”, aby pozwolić na grę w golfa przy użyciu bin (x) pythona. Gdy interpreter napotka znak \, wyprowadzany jest następny znak i oba znaki są usuwane. Gdy napotka znak /, szuka wzorców wyszukiwania i zamienia je jako / search / replace / włączając w to znaki specjalne (\\ reprezentuje \ i \ / reprezentuje /). Ta operacja zamiany jest następnie wykonywana wielokrotnie na łańcuchu, aż łańcuch wyszukiwania nie będzie już obecny, a następnie interpretacja będzie kontynuowana od początku. Program zatrzymuje się, gdy jest pusty. Program zostanie zabity, jeśli istnieje niezamknięty zestaw / wzorców lub \ bez znaku po nim.

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 w Javie, 1299 1257 1251 1207 1203 1201 1193 1189 bajtów

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 → Problem z korespondencją pocztową , 10 bajtów

≜;?{~c}ᵐ\d

Wypróbuj online!

Funkcja, która jest generatorem, który generuje wszystkie możliwe problemy z korespondencją pocztową, dla których rozwiązania wymuszania brutalnego w końcu przestają działać. (Brutalne wymuszanie rozwiązań problemu korespondencji Post jest znane jako operacja kompletna Turinga). Łącze TIO zawiera nagłówek, który konwertuje generator do pełnego programu i drukuje każde wyjście natychmiast po wygenerowaniu (a zatem, gdy TIO zabija program z uwagi na to, że zużywa ponad 60 sekund czasu wykonania, dotychczasowy wynik jest widoczny).

Wykorzystuje się w tym sformułowanie problemu, w którym ciągi są podawane jako ciągi cyfr, zera wiodące są niedozwolone, z wyjątkiem 0samego siebie, rozwiązania problemu dotyczącego zer wiodących nie są akceptowane, a ciąg cyfr może być reprezentowany jako liczba lub minus liczba. Oczywiście nie ma to żadnego wpływu na kompletność języka Turinga (ponieważ nie ma potrzeby, aby problem z korespondencją w Post wykorzystywał cyfrę zero).

Ten program działa poprzez generowanie wszystkich możliwych rozwiązań problemów, a następnie pracę wstecz, aby znaleźć oryginalne programy, które są przez nich rozwiązywane. Jako taki, pojedynczy program może być wyprowadzany wiele razy. Nie jest jasne, czy to unieważnia odpowiedź, czy nie; zwróć uwagę, że wszystkie programy zatrzymujące zostaną ostatecznie wydane co najmniej raz (w rzeczywistości nieskończenie wiele razy, ponieważ każdy program, który ma rozwiązania, ma nieskończenie wiele rozwiązań), a programy nie zatrzymujące nigdy nie zostaną wyświetlone.

Wyjaśnienie

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

„Fioletowy bez I / O” na Cejlonie, 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));}}}}

Fioletowy jest samodmodyfikującym się językiem z jedną instrukcją, który został tutaj poproszony o tłumaczenie . Jako wejście i wyjście nie są istotne dla tego zadania, usunąłem oznaczenie symbolu od tłumacza, tak że (potencjalnie) symbole są ważne tylko a, b, A, B, ii 1(ten ostatni tylko do czytania, nie do pisania).

Ale ponieważ Purple sam się modyfikuje (i używa swojego kodu źródłowego jako danych), potencjalnie przydatne mogą być również programy zawierające inne niż te znaki, dlatego zdecydowałem się zezwolić na wszystkie znaki ASCII do drukowania (inne niż białe znaki) w kodzie (inne mogą być przydatne, ale nie są tak łatwe do wydrukowania).

(Możesz zmodyfikować interpreter, aby zamiast tego przyjmował jako ciąg dozwolonych znaków jako argument wiersza poleceń - przełącz zdefiniowaną aponiżej linię z komentarzem . Wtedy długość wynosi 686 bajtów.)

Mój „równoległy” interpreter tworzy zatem wszystkie skończone ciągi znaków z tych znaków (w coraz większej długości i porządku leksykograficznym) i próbuje każdego z nich.

Fioletowy zatrzyma się bezbłędnie za każdym razem, gdy polecenie do odczytania z taśmy do wykonania jest nieprawidłowe - dlatego nie ma niepoprawnych programów i wiele, wiele zatrzymujących. (Większość zatrzymuje się nawet na pierwszym etapie, tylko niektóre programy o długości 3 przechodzą do drugiego etapu (i zatrzymają się wtedy), pierwsze nie zatrzymujące się mają długość 6.

Myślę, że pierwszym nie zatrzymującym się programem w kolejności wypróbowanej przez mojego tłumacza jest aaaiaa, który w pierwszym kroku ustawia arejestr na 0 (który już był), a drugi i każdy następny krok ustawia wskaźnik instrukcji z powrotem na 0, powodując jego iaaponowne uruchomienie .

Ponownie wykorzystałem część kodu napisanego dla mojego interpretera „standardowego” fioletu , ale z powodu usunięcia danych wejściowych i wyjściowych mój równoległy interpreter staje się nawet nieco krótszy, a jednocześnie zawiera dodatkową logikę do wykonywania wielu programów jednocześnie.

Oto skomentowana i sformatowana wersja:

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

Rachunek kombinatoryczny SK w Haskell , 249 bajtów

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)

Wypróbuj online!

Jak to działa

Reguły oceny według wartości wywoławczej dla rachunku kombinatora SK są następujące:

(a) S xyz ↦ xz ( yz ), dla x , y , z w postaci normalnej;
(b) K xy ↦ x , dla x , y w postaci normalnej;
(c) xy ↦ x ′ y , jeśli x ↦ x ′;
(d) xy ↦ xy ′, dla x w normalnej formie, jeśli y ↦ y ′ .

Ponieważ jesteśmy zainteresowani jedynie zatrzymywaniem zachowania, nieznacznie rozszerzamy język, wprowadzając symbol H, który nie jest w normalnej formie, ale do którego „wszystkie” normalne formy „oceniają”:

(a) S xyz ↦ xz ( yz ), dla x , y , z w postaci normalnej;
(b ′) K x H ↦ x , dla x w postaci normalnej;
(c) xy ↦ x ′ y , jeśli x ↦ x ′;
(d) xy ↦ xy ′, dla xw normalnej formie, jeśli y ↦ y ′ ;
(e) S = H;
(f) K = H;
(g) SH ↦ H;
(h) KH ↦ H;
(i) SHH ↦ H.

Uważamy, że każda aplikacja H x jest błędem w czasie wykonywania traktowanym tak, jakby była nieskończoną pętlą, i zlecamy oceny w taki sposób, aby żadne H nie było wytwarzane przez (e) - (i), z wyjątkiem kontekstu, w którym będzie ignorowane (najwyższy poziom, dowolne K x ☐, dowolne zignorowane K any, dowolne zignorowane S x ☐ dla x w normalnej formie, dowolne zignorowane S☐H). W ten sposób nie wpływamy na zatrzymanie zachowania zwykłych terminów bez H.

Korzyści z tych zmodyfikowanych reguł są takie, że każdy znormalizowany termin ma unikalną ścieżkę oceny do H i że każdy termin ma skończoną liczbę możliwych obrazków pod under. Zamiast więc stosować podejście typu „jaskółczy ogon”, możemy przeprowadzić o wiele bardziej wydajne przeszukiwanie wszystkich ścieżek oceny odwrotnej od H.

nsprawdza, czy termin jest w normalnej formie, fznajduje wszystkie możliwe obrazy tego terminu i ljest leniwą, nieskończoną listą normalizowanych terminów utworzoną podczas pierwszego wyszukiwania od H.