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)))));}
źródło
Odpowiedzi:
JavaScript, D ^ 6 (9) (
508501495492487485481 bajtów)To jest zakodowany kod.
Dekodowany kod:
Zdekodowany, nieoznakowany kod (warunki i inne rzeczy są przechowywane przed loader.c):
Zakłada się, że:
NumberNumberAlgorytm kodowania / dekodowania:
Kodowanie odbywa się w następujący sposób:
Algorytm dekodowania:
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 )
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ówne8646911284551352321.Tak więc, D (9) >>> 99, a ponieważ D ściśle rośnie, D ^ 6 (9)> D ^ 5 (99).
D(D(D(D(D(99)))))naD(D(D(D(D(D(9)))))). Także to przetasowało litery.&&(1)doD(x)jego sytuacji pętli./2s do>>1s, ponieważNumberfor...innafor...of.evaldoDusuwaniareturn.źródło
Python 3, D ^ 6 (9) (
608600599 bajtów)To jest zakodowany kod. Wytłoczony:
Zakłada się, że:
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.Sograniczenia nawiasówu/2trzeciego ostatniego wiersza definicjiDnau>>1, oszczędzając bajt od kompresji go do znaku z innymi>>1s.źródło
Rubinowy, D ^ 6 (9) (553 bajtów)
To jest zakodowany kod. Wytłoczony:
Ten kod jest zamiast tego numerem ładowarki z D 6 (9).
Zakłada się, że:
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ę.
źródło