Jako kontynuacja najkrótszego programu kończącego, którego wielkość wyjściowa przekracza liczbę Grahama i Golfa większą niż TREE (3) , przedstawiam nowe wyzwanie.

Liczba ładujących jest bardzo dużą liczbą, która jest dość trudna do wyjaśnienia (ponieważ sama była wynikiem ćwiczenia w golfa kodowego z elastycznym celem). Jest to definicja i wyjaśnienie tutaj , ale dla celów samodzielnego magazynowania, postaram się to wyjaśnić w dalszej części tego postu, jak również.

Zastosowany algorytm Ralph Loader tworzy jedną z największych liczby (obliczalnych) algorytmów, jakie kiedykolwiek napisano! Rzeczywiście, liczba Loadera jest największą liczbą „obliczalną” na Wiki Googology. (Przez liczbę „obliczalną” oznaczają liczbę zdefiniowaną w oparciu o obliczenia.) Oznacza to, że jeśli odpowiedź daje liczbę większą niż liczba modułu ładującego w interesujący sposób (tj. Nie tylko liczbę modułu ładującego + 1), można zejść Historia googologii! To powiedziawszy, programy, które produkują coś w rodzaju numeru Loadera + 1, są zdecydowanie poprawnymi odpowiedziami i rywalizują z tym pytaniem; po prostu nie oczekuj żadnej sławy.

Twoim zadaniem jest stworzenie programu kończącego, który wygeneruje liczbę większą niż liczba modułu ładującego. To jest golf golfowy , więc wygrywa najkrótszy program!

• Nie możesz przyjmować danych wejściowych.
• Twój program musi ostatecznie zakończyć się deterministycznie, ale możesz założyć, że maszyna ma nieskończoną pamięć.
• Możesz założyć, że typ liczbowy Twojego języka może zawierać dowolną skończoną wartość, ale musisz wyjaśnić, jak to dokładnie działa w twoim języku (np. Czy liczba zmiennoprzecinkowa ma nieskończoną precyzję?)
  • Nieskończoności nie są dozwolone jako wynik.
  • Niedomiar typu liczbowego powoduje wyjątek. Nie zawija się.
• Musisz podać wyjaśnienie, dlaczego Twój numer jest tak duży, oraz wersję kodu bez kodu, aby sprawdzić, czy twoje rozwiązanie jest prawidłowe (ponieważ nie ma komputera z wystarczającą ilością pamięci do przechowywania numeru modułu ładującego).

Oto wyjaśnienie numeru modułu ładującego. Zobacz http://googology.wikia.com/wiki/Loader%27s_number i linki w nim, aby uzyskać bardziej szczegółowe informacje. W szczególności zawiera program, który dokładnie wytwarza numer modułu ładującego (z definicji).

Rachunek konstrukcji jest w zasadzie językiem programowania o bardzo szczególnych właściwościach.

Po pierwsze, każdy poprawny składniowo program kończy się. Nie ma nieskończonych pętli. Będzie to bardzo przydatne, ponieważ oznacza, że ​​jeśli uruchomimy dowolny rachunek programu konstrukcyjnego, nasz program nie utknie. Problem polega na tym, że oznacza to, że rachunek strukturalny nie jest kompletny w Turingu.

Po drugie, wśród niekompletnych języków jest jednym z najpotężniejszych. Zasadniczo, jeśli możesz udowodnić, że maszyna Turinga zatrzyma się na każdym wejściu, możesz zaprogramować funkcję w rachunku konstrukcji, która będzie ją symulować. (To nie oznacza, że ​​turing jest zakończony, ponieważ istnieją maszyny do zatrzymywania, których nie można udowodnić, że się zatrzymują.)

Liczba modułu ładującego jest w zasadzie zajętym numerem bobra dla rachunku konstrukcji, który można obliczyć, ponieważ wszystkie programy coc zostają zakończone.

W szczególności loader.c definiuje funkcję o nazwie D. W przybliżeniu D(x)iteruje wszystkie ciągi bitowe mniej niż x, interpretuje je jako programy coc, uruchamia te poprawne składniowo i konkatenuje wyniki (które również będą ciągami bitowymi ). Zwraca tę konkatenację.

Numer ładowarki to D(D(D(D(D(99))))).

Bardziej czytelna kopia kodu z wiki googolologii

int r, a;

P(y,x){return y- ~y<<x;}

Z(x){return r = x % 2 ? 0 : 1 + Z (x / 2 );}

L(x){return x/2 >> Z(x);}

S(v,y,c,t){
   int f = L(t);         
   int x = r;
   return f-2 ? f>2 ? f-v ? t-(f>v)*c : y : P(f,P(S(v,y,c,L(x)), S(v+2,t=S(4,13,-4,y),c,Z(x)))) : A(S(v,y,c,L(x)),S(v,y,c,Z(x)));
}

A(y,x){return L(y)-1 ? 5<<P(y,x) : S(4,x,4,Z(r));}

D(x) 
{
   int f;
   int d;
   int c=0;
   int t=7;
   int u=14;
   while(x&&D(x-1),(x/=2)%2&&(1)){
      d = L(L(D(x))),
      f = L(r),
      x = L(r),
      c - r||(L(u)||L(r)-f||(x/=2)%2&&(u=S(4,d,4, r),t=A(t,d)),f/2&(x/=2)%2&&(c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u))),
      c&&(x/=2)%2&&(t=P(~u&2|(x/=2)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r)
      u/2&(x/=2)%2&&(c=P(t,c),u=S(4,13,-4,t),t=9);
    }
    return a = P( P( t, P( u, P( x, c)) ),a);
}

main(){return D(D(D(D(D(99)))));}

JavaScript, D ^ 6 (9) ( _{508 501 495 492 487 485} 481 bajtów)

_='r=a=0,PN,yEx-~x<<y,ZNEr=x%2?0:1+ZC>>1@LNEx/2>>ZC@S=Bt,f=Ht@x=rEf-2?f>2?f-v?t-(f>v)*c:y:Ff,FSO(v+2,t8y@c,ZCMM:A(AOBZC)GAN,yELC)-1?5<<PC,y):Iy,4,Z(rGDN,f,dQ=0,t=7,u=14Eeval("whileC&&DC-1@61Md=HHDC)Gf=Hr@x=Hr@c-r||(Hu)||Hr)-f||6u=Id,4,r@t=A(t,dGfJdQ@t8t@u8u)Gc&&6t=F~u&2|6u=1<<FHc@uGFHc@tGc=r@uJtQ@u8t@t=9);a=FFt,Fu,PCQ)Ga)"@KKK9MMM6C>>=1)%2&&(8=I13,-4,G)@@),B(v,yQ,N=COBLCGSC(xE)=>J/2&6c=FFP(HL(IS(4,KD(D(M))Q,c';for(Y of $='QMKIHFJECONB@G86')with(_.split(Y))_=join(pop());eval(_)

To jest zakodowany kod.

_='r=a=0,PN,yEx-~x<<y,ZNEr=x%2?0:1+ZC>>1@LNEx/2>>ZC@S=Bt,f=Ht@x=rEf-2?f>2?f-v?t-(f>v)*c:y:Ff,FSO(v+2,t8y@c,ZCMM:A(AOBZC)GAN,yELC)-1?5<<PC,y):Iy,4,Z(rGDN,f,dQ=0,t=7,u=14Eeval("whileC&&DC-1@61Md=HHDC)Gf=Hr@x=Hr@c-r||(Hu)||Hr)-f||6u=Id,4,r@t=A(t,dGfJdQ@t8t@u8u)Gc&&6t=F~u&2|6u=1<<FHc@uGFHc@tGc=r@uJtQ@u8t@t=9);a=FFt,Fu,PCQ)Ga)"@KKK9MMM6C>>=1)%2&&(8=I13,-4,G)@@),B(v,yQ,N=COBLCGSC(xE)=>J/2&6c=FFP(HL(IS(4,KD(D(M))Q,c'; //encoded code
for(Y of $='QMKIHFJECONB@G86')with(_.split(Y))_=join(pop()); //decoding algorithm
eval(_) //Evaluation of the string

Dekodowany kod:

r=a=0,P=(x,y)=>x-~x<<y,Z=(x)=>r=x%2?0:1+Z(x>>1),L=(x)=>x/2>>Z(x),S=(v,y,c,t,f=L(t),x=r)=>f-2?f>2?f-v?t-(f>v)*c:y:P(f,P(S(v,y,c,L(x)),S(v+2,t=S(4,13,-4,y),c,Z(x)))):A(A(v,y,c,L(x)),S(v,y,c,Z(x))),A=(x,y)=>L(x)-1?5<<P(x,y):S(4,y,4,Z(r)),D=(x,f,d,c=0,t=7,u=14)=>eval("while(x&&D(x-1),(x>>=1)%2&&(1))d=L(L(D(x))),f=L(r),x=L(r),c-r||(L(u)||L(r)-f||(x>>=1)%2&&(u=S(4,d,4,r),t=A(t,d)),f/2&(x>>=1)%2&&(c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u))),c&&(x>>=1)%2&&(t=P(~u&2|(x>>=1)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r),u/2&(x>>=1)%2&&(c=P(t,c),u=S(4,13,-4,t),t=9);a=P(P(t,P(u,P(x,c))),a)"),D(D(D(D(D(D(9))))))

Zdekodowany, nieoznakowany kod (warunki i inne rzeczy są przechowywane przed loader.c):

var r=a=0;
function P(y,x){
  return y-~y<<x;
}
function Z(x){
  return r=x%2?0:1+Z(x>>1);
}
function L(x){
  return x/2>>Z(x);
}
function S(v,y,c,t){
  var f=L(t),x=r;
  return f-2?
           f>2?
             f-v?
               t-(f>v)*c
               :y
             :P(f,P(S(v,y,c,L(x)),S(v+2,t=S(4,13,-4,y),c,Z(x))))
           :A(S(v,y,c,L(x)),S(v,y,c,Z(x)))
}
function A(y,x){
  return L(y)-1?
         5<<P(y,x):
         S(4,x,4,Z(r));
}
function D(x){
  var f,
      d,
      c=0,
      t=7,
      u=14;
  while(x&&D(x-1),(x>>=1)%2&&(1))
    d=L(L(D(x))),
    f=L(r),
    x=L(r),
    c-r||(
      L(u)||L(r)-f||
      (x>>=1)%2&&(
        u=S(4,d,4,r),t=A(t,d)
      ),
      f/2&(x>>=1)%2&&(
        c=P(d,c),
        t=S(4,13,-4,t),
        u=S(4,13,-4,u)
      )
    ),
    c&&(x>>=1)%2&&(
      t=P(
        ~u&2|(x>>=1)%2&&(
          u=1<<P(L(c),u)
        ),
        P(L(c),t)
      ),
      c=r
    ),
    u/2&(x>>=1)%2&&(
      c=P(t,c),
      u=S(4,13,-4,t),
      t=9
    );
  return a=P(P(t,P(u,P(x,c))),a)
};
D(D(D(D(D(D(9))))))

Zakłada się, że:

• Nieskończony stos wywołań
• Nieskończona pamięć
• Nieskończona precyzja Number
• Nieskończona wielkość Number
• Operatory Bitshift i bitowe działają na nieskończonych liczbach całkowitych zamiast 53 bitów. Negacja bitowa nadal neguje bit znaku.

Algorytm kodowania / dekodowania:

Kodowanie odbywa się w następujący sposób:

• Weź powtarzający się ciąg, nazwij to S.
• Zamień wszystkie S w kodzie na klucz K.
• Na końcu umieść K i S.
• Zrób listę kluczy, a także umieść algorytm dekodujący, aby kod faktycznie działał.

Algorytm dekodowania:

• Weź listę kluczy.
• Weź najwcześniejszy klucz K.
• Podziel ciąg dla każdego K.
• Ponieważ ostatnią z tablicy jest to, co ma zastąpić KS, wstaw ją i zamień wszystkie K, łącząc tablicę z wyskakującą wartością S.

Kompresja została wykonana przy użyciu tego kodu , zaznacz tylko ostatnie pole. Ponieważ najpierw zakoduje to największy zapis, nie jest to najbardziej wydajna kompresja, ale nie wiem, jak ją zmniejszyć, więc meh.

JavaScript, (339 znaków )

eval("_㴧爽愽〬偍ⱹ䕸⵾砼㱹ⱚ䵅爽砥㈿〺ㄫ婃㸾ㅀ䱍䕸⼲㸾婃䁓㵂琬昽䡴䁸㵲䕦ⴲ㽦㸲㽦⵶㽴⴨显瘩⩣㩹㩆昬䙓丨瘫㈬琸祀挬婃䭋㩁⡁乂婃⥇䅍ⱹ䕌䌩ⴱ㼵㰼偃ⱹ⤺匨㐬礬㐬娨片䑍ⱦⱤⱣ㴰ⱴ㴷Ⱶ㴱㑅敶慬⠢睨楬敃☦䑃ⴱ䀶ㅋ搽䡈䑃⥇昽䡲䁸㵈牀挭牼簨䡵⥼籈爩ⵦ籼㙵㵓⠴ⱤⰴⱲ䁴㵁⡴Ɽ䝦䥤Ᵽ䁴㡴䁵㡵⥇挦☶琽䙾甦㉼㙵㴱㰼䙈捀畇䙈捀瑇挽牀畉琬捀甸瑀琽㤩㭡㵆䙴ⱆ甬偃Ᵽ⥇愩≀䩊䨹䭋䬶䌾㸽ㄩ┲☦⠸㵓⠴ⰱ㌬ⴴⱇ⥀䀩ⱂ⡶ⱹⱣⱍ㵃乂䱃䝓䌨硅⤽㹉⼲☶挽䙆倨䡌⡊䐨䐨䬩⤧㭦潲⡙映␽❋䩈䙉䕃乍䉀䜸㘧⥷楴栨弮獰汩琨天⥟㵪潩渨灯瀨⤩㭥癡氨弩".split``.map(a=>(d=String.fromCharCode)((c=a.charCodeAt())>>8)+d(c&255)).join``.slice(1))

Ten kod weźmie 16-bitowy ciąg jako a, konwertuje go na 8-bitowy ciąg z tym samym plikiem binarnym (BE) i evalto.

Dekodowany kod to kod zakodowany powyżej.

Dowód, że D ^ 6 (9)> D ^ 5 (99)

W tym celu porównalibyśmy D (9) i 99.

Po ręcznym uruchomieniu kodu D (9) jest równe (15*2^14849+1)*2^((15*2^14849+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^929+1)*2^((15*2^929+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^(15*2^59+1)))))))))))))))))))))))))))))))), a nawet D (0) jest równe 8646911284551352321.

Tak więc, D (9) >>> 99, a ponieważ D ściśle rośnie, D ^ 6 (9)> D ^ 5 (99).

• 508B-> 501B, -7B
  • -1B dla ... Nie wiem dlaczego. Zmieniłem się D(D(D(D(D(99)))))na D(D(D(D(D(D(9)))))). Także to przetasowało litery.
  • -6B do ponownego dodania &&(1)do D(x)jego sytuacji pętli.
• 501B-> 495B, -6B
  • Naprawiono większość /2s do >>1s, ponieważNumber
  • 6 bajtów oszczędzić skądś
  • Można zobaczyć moją próbę w tej aktualizacji tutaj
• 495 -> 492B, -3B
  • Zmieniając dekoder z for...inna for...of.
• 492 -> 487B, -5B
  • Usuwanie niepotrzebnych zadań
  • Zmiana nazw argumentów
• 487-> 485 B, -2 B
  • 1 bajt z użycia evaldo Dusuwania return.
  • Kompresja 1 bajtowa łącząca nawiasy zamykające z przecinkiem.
• 485-> 481B, -4B
  • Kompresując różne podciągi.

Python 3, D ^ 6 (9) ( _{608 600} 599 bajtów)

_='r=a=0?CM:#y-~y<<x?H6@r=0.EB1+HI)#r?Fx):#xI>>H)?8t6@TtNr#A(U8HG).f==2BCf,CUS(v+2,/yNc,HGG.f<2Bt-(f>v)*c.f-vBy?A(M:#5<<CM.Fy)-1BOx,4,Z(rG?Jx6,a@f=d=c=0@VW7,14@while 1:@.x:Jx-1)X~E:breakKd,TFJxGNFrNFr)@.c-r:K.not(Fu)or(Fr)-fGQ.E:WOd,4,rRA(Vd)K.fIQ.Yd,cR/t);W/u)@.c:@!.EQ q=~u&2|EK .q:W1<<CFuNu)K  Vc=Cq and u,CFcNtG,rXuI&YVc);W/tR9@a=CCVCu,Cx,cGNa)#a\nprint(JJJJJJ9GGG)X\n!if !  x=xIK#@return . if /O13,-4,6):@global r8S(v,y,c,?\ndef Q:K! K@ @\n B else CP(YE:c=CEx%2Tf,x=FFL(U8FxG,G))HZ(xI>>1JD(My,x)N),OS(4,R);t=Vt,Wu='
for Y in 'WVRONMJIHGUFTEYCB@KQ?86/.#!X':_=_.split(Y);_=_.pop().join(_)
exec(_)

To jest zakodowany kod. Wytłoczony:

r=a=0
def P(y,x):
 return y-~y<<x
def Z(x):
 global r
 r=0 if x%2 else 1+Z(x>>1)
 return r
def L(x):
 return x>>1>>Z(x)
def S(v,y,c,t):
 global r
 f,x=L(t),r
 return A(S(v,y,c,L(x)),S(v,y,c,Z(x))) if f==2 else P(f,P(S(v,y,c,L(x)),S(v+2,S(4,13,-4,y),c,Z(x)))) if f<2 else t-(f>v)*c if f-v else y
def A(y,x):
 return 5<<P(y,x) if L(y)-1 else S(4,x,4,Z(r))
def D(x):
 global r,a
 f=d=c=0
 t,u=7,14
 while 1:
  if x:D(x-1)
  x=x>>1
  if ~x%2:break
  d,f,x=L(L(D(x))),L(r),L(r)
  if c-r:
   if not(L(u)or(L(r)-f)):
    x=x>>1
    if x%2:u=S(4,d,4,r);t=A(t,d)
   if f>>1:
    x=x>>1
    if x%2:c=P(d,c);t=S(4,13,-4,t);u=S(4,13,-4,u)
  if c:
   x=x>>1
   if x%2:
    x=x>>1
    q=~u&2|x%2
    if q:u=1<<P(L(u),u)
    t,c=P(q and u,P(L(c),t)),r
  x=x>>1
  if u>>1&x%2:c=P(t,c);u=S(4,13,-4,t);t=9
 a=P(P(t,P(u,P(x,c))),a)
 return a
print(D(D(D(D(D(D(9)))))))

Zakłada się, że:

• Nieskończony stos wywołań
• Nieskończona pamięć

Jest to w zasadzie część mojej odpowiedzi JavaScript . Aby uzyskać więcej informacji, sprawdź ten.

Kompresja została z tym wykonana .

Nie mam zbyt dużej wiedzy na temat języka Python, więc z pewnością są miejsca do zapisywania bajtów. Myślę, że sub-600 jest możliwe. Sub-600 został sprawdzony.

• 608-> 600B, -8B
  • Zgrupowane niektóre zadania
  • Odwrócone warunki Sograniczenia nawiasów
• 600-> 599B, ​​-1B
  • Zmiana u/2trzeciego ostatniego wiersza definicji Dna u>>1, oszczędzając bajt od kompresji go do znaku z innymi >>1s.

Rubinowy, D ^ 6 (9) (553 bajtów)

_='F=$a=0TEK#y-~yUx.Z@#F=x%2G1?0R1+Z(x/2).L@#x/2>>Z@.8t)VHt);x=F#fG2?A(8L@C8Z@IRf>2?fGv ?yRt-(f>v ?1R0)*cREf,E8L@CS(v+2,t6yCc,Z@I).A(K#Hy)G1?Mx,4,Z(FIR5UEK.D@;$>UxVd=c=0;t=7;u=14;while[xNOx-1CB>0][1];d=HHD@IVW;x=W;cGF&&[Hu)G0&&WGf&&![u=Md,4,FCt=A(t,d)],fJd,cCt6tCu6u)]];cNB&&[t=E~u&2|!(u=1UEHcCu)CEHcCt)Cc=F];uJt,cCu6tCt=9]Q#$a=EEt,Eu,Ex,cIC$a)Q;$>UOOOOOO9III!BN#;return .QT6=M13,-4,8S(v,y,c,@(x)B(x/=2)%2C),J/2&![c=EEP(F$rNG0||G==WHF)HL(I))Ky,x)MS(4,OD(Q;endR: T;def U<<V;f=VUTRQOMKIHWGNFEJCB@86.#!'.each_char{|Y|_=_.split(Y);_=_.join(_.pop())};eval(_)

To jest zakodowany kod. Wytłoczony:

$r=$a=0;def P(y,x);return y-~y<<x;end;def Z(x);return $r=x%2==1?0: 1+Z(x/2);end;def L(x);return x/2>>Z(x);end;def S(v,y,c,t);f=L(t);x=$r;return f==2?A(S(v,y,c,L(x)),S(v,y,c,Z(x))): f>2?f==v ?y: t-(f>v ?1: 0)*c: P(f,P(S(v,y,c,L(x)),S(v+2,t=S(4,13,-4,y),c,Z(x))));end;def A(y,x);return L(y)==1?S(4,x,4,Z($r)): 5<<P(y,x);end;def D(x);$><<x;f=d=c=0;t=7;u=14;while[x==0||D(x-1),(x/=2)%2>0][1];d=L(L(D(x)));f=L($r);x=L($r);c==$r&&[L(u)==0&&L($r)==f&&(x/=2)%2==0||[u=S(4,d,4,$r),t=A(t,d)],f/2&(x/=2)%2==0||[c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u)]];c==0||(x/=2)%2&&[t=P(~u&2|(x/=2)%2==0||(u=1<<P(L(c),u)),P(L(c),t)),c=$r];u/2&(x/=2)%2==0||[c=P(t,c),u=S(4,13,-4,t),t=9];end;return $a=P(P(t,P(u,P(x,c))),$a);end;$><<D(D(D(D(D(D(9))))))

Ten kod jest zamiast tego numerem ładowarki z D ⁶ (9).

Zakłada się, że:

• Nieskończony stos wywołań
• Nieskończona pamięć

Jest to w zasadzie część mojej odpowiedzi JavaScript i Python 3 . Aby uzyskać więcej informacji, sprawdź je.

Kompresja została wykonana z tym (może się pojawić, ponieważ nie istnieje).

Jestem początkującym w Ruby, więc może poniżej 512 jest możliwe, ale wątpię.