Napisz możliwie najkrótszy program (długość mierzony w bajtach) spełniający następujące wymagania:

• brak wejścia
• wyjście jest na standardowe wyjście
• wykonanie ostatecznie kończy się
• całkowita liczba bajtów wyjściowych przekracza liczbę Grahama

Załóżmy, że programy działają aż do „normalnego” zakończenia na idealnym komputerze ^{1, który} może uzyskać dostęp do nieograniczonych zasobów, oraz że wspólne języki programowania są modyfikowane, jeśli to konieczne (bez zmiany składni), aby to umożliwić. Z powodu tych założeń możemy nazwać to rodzajem eksperymentu Gedanken.

Na początek oto 73-bajtowy program Ruby, który oblicza f _{ω + 1} (99) w szybko rosnącej hierarchii :

f=proc{|k,n|k>0?n.times{n=f[k-1,n]}:n+=1;n};n=99;n.times{n=f[n,n]};puts n

¹ EDYCJA: Dokładniej, załóżmy, że bierzemy istniejący system i modyfikujemy go tylko po to, aby nie mieć górnego limitu wielkości pamięci (ale zawsze jest skończony). Czasy wykonania instrukcji nie powinny być modyfikowane, ale zakłada się, że maszyna jest idealna, ponieważ nie będzie miała górnego limitu czasu pracy.

GolfScript ( 49 47 znaków)

4.,{\):i\.0={.0+.({<}+??\((\+.@<i*\+}{(;}if.}do

Aby uzyskać wiele wyjaśnień, zobacz Żywotność robaka . W skrócie, wypisuje liczbę większą niż f _{ω ^ω} (2).

Haskell, _{59 57 55} 63

(f%s)1=s;(f%s)n=f.(f%s)$n-1
main=print$((flip((%3)%(3^))3)%4)66

Jak to działa: %po prostu bierze funkcję i komponuje ją n-1razy s; tzn. %3przyjmuje funkcję fi zwraca funkcję nrówną zastosowaniu jej fdo 3 n-1razy z rzędu. Jeśli iterujemy stosowanie tej funkcji wyższego rzędu, otrzymujemy szybko rosnącą sekwencję funkcji - zaczynając od potęgowania, jest to dokładnie sekwencja rozmiarów Knutha-strzałki-lasu:
((%3)%(3^))1 n = (3^)n     = 3ⁿ = 3↑n
((%3)%(3^))2 n = ((3^)%3)n = (3↑)ⁿ⁻¹ $ 3 = 3↑↑n
((%3)%(3^))3 n = (((3^)%3)%3)n = (3↑↑)ⁿ⁻¹ $ 3  = 3↑↑↑n
i tak dalej. ((%3)%(3^))n 3jest 3 ↑ⁿ 3, co pojawia się w obliczeniach do liczby Grahama. Pozostaje tylko skomponować funkcję(\n -> 3 ↑ⁿ 3) ≡ flip((%3)%(3^))3ponad 64 razy, oprócz 4 (liczby strzałek, od których rozpoczyna się obliczenie), aby uzyskać liczbę większą niż liczba Grahama. Oczywiste jest, że logarytm (co to za powolna wolna funkcja!) g₆₅Jest wciąż większy niż g₆₄=G, więc jeśli wydrukujemy tę liczbę, długość wyjściowa przekroczy G.

⬛

Pyth , 29 28 bajtów

M?*GHgtGtgGtH^ThH=ZTV99=gZTZ

Definiuje lambda dla hiperoperacji i rekurencyjnie ją wywołuje. Podobnie jak definicja liczby Grahama, ale z większymi wartościami.

To:

M?*GHgtGtgGtH^3hH

Definiuje lambda, mniej więcej równe pytonowi

g = lambda G, H:
  g(G-1, g(G, H-1)-1) if G*H else 3^(H+1)

Daje to funkcję hiperoperacji, g (G, H) = 3 ↑ ^{G + 1} (H + 1).
Na przykład g (1,2) = 3 ↑ ² 3 = 7,625,597,484,987, co możesz przetestować tutaj .

V<x><y>uruchamia pętlę, która wykonuje ciało y, xrazy.
=gZTjest tu ciałem pętli, co jest równoważne zZ=g(Z,10)

Kod:

M?*GHgtGtgGtH^3hH=Z3V64=gZ2)Z

Powinien rekurencyjnie wywoływać hiperoperację ponad 64 razy, podając liczbę Grahama.

W mojej odpowiedzi zastąpiłem jednak pojedyncze cyfry T, które są inicjowane do 10, i zwiększyłem głębokość rekurencji do 99. Za pomocą Notacji tablicy Grahama, liczba Grahama wynosi [3,3,4,64], a moja program wypisuje większy [10,11,11,99]. Usunąłem również tę, )która zamyka pętlę, aby zapisać jeden bajt, więc wypisuje każdą kolejną wartość w 99 iteracjach.

Python (111 + n), n = długość (x)

Chociaż ten nie jest tak krótki jak program Ruby odpowiadającego, i tak opublikuję go, aby wykluczyć tę możliwość.

Wykorzystuje funkcję Ackermann i wywołuje funkcję Ackermann, gdzie m i n są wartościami z innego wywołania funkcji Ackermann, i powtarza się 1000 razy.

Prawdopodobnie jest to liczba większa niż liczba Grahama, ale nie jestem pewien, ponieważ nikt nie zna jej dokładnej długości. Można go łatwo rozszerzyć, jeśli nie jest większy.

x=999
b='A('*x+'5,5'+')'*x
def A(m,n):n+1 if m==0 else A(m-1,A(m,n-1)if n>0 else 1)
exec('print A('%s,%s')'%(b,b))

Rubin, 54 52 50 bajtów

f=->b{a*=a;eval"f[b-1];"*b*a};eval"f[a];"*a=99;p a

Rubinowy, 85 81 76 71 68 64 63 59 57 bajtów

f=->a,b=-a{eval"a*=b<0?f[a,a]:b<1?a:f[a,b-1];"*a};p f[99]

Dość szybko rosnąca hierarchia zf (a + 1)> f _{ω + 1} (a).

Ruby, 61 bajtów

f=->a,b=-a{a<0?9:b==0?a*a:f[f[a-1,b],b>0?b-1:f[a,b+1]]};f[99]

Zasadniczo funkcja Ackermanna z niespodzianką.

Rubin, 63 59 bajtów

n=99;(H=->a{b,*c=a;n.times{b ?H[[b-1]*n*b+c]:n+=n}})[n];p n

Another Ruby, 74 71 bajtów

def f(a,b=a)a<0?b:b<0?f(a-1):f(a-1,f(a,b-1))end;n=99;n.times{n=f n};p n

Zasadniczo funkcja Ackermanna do siebie 99 razy.

Python: 85

f=lambda a,a:a*a
exec'f=lambda a,b,f=f:reduce(f,[a]*b,1)'*99
exec'f('*64+'3'+',3)'*64

Który może być skrócony do 74+length(X) :

f=lambda a,a:a*a
exec'f=lambda a,b,f=f:reduce(f,[a]*b,1)'*int('9'*X)
f(3,3)

Gdzie Xjest odpowiednia duża liczba, taka że wynikowa hiperoperacja 3, 3jest większa niż liczba Grahama (jeśli ta liczba jest mniejsza niż, 99999999999wówczas zapisywany jest jakiś bajt).

Uwaga: Zakładam, że kod Pythona jest wykonywany na interaktywnym interpretatorze, dlatego wynik jest wypisywany na standardowe wyjście, w przeciwnym razie dodaj 9bajty do każdego rozwiązania dla wywołania print.

JavaScript, 83 bajty

Kolejne rozwiązanie funkcji Ackermanna.

(function a(m,n,x){return x?a(a(m,n,x-1),n,0):(m?a(m-1,n?a(m,n-1):1):n+1)})(9,9,99)

JavaScript, 68 bajtów, jednak nie konkuruje o użycie ES6

a=(x,y)=>y?x?a(a(x-1,y)*9,y-1):a(9,y-1):x;b=x=>x?a(9,b(x-1)):9;b(99)

a funkcja jest podobna do notacji strzałki w górę z bazą 9.

       /a(a(x-1,y)*9,y-1)  x>0, y>0
a(x,y)=|a(9,y-1)           x=0, y>0
       \x                  y=0

bfunkcja to: b (x) = b ^x (9).

b(99)to ~ f _{ω + 1} (99), w porównaniu do liczby Grahama <f _{ω + 1} (64).