Najkrótszy kończący program, którego rozmiar wyjściowy przekracza liczbę Grahama

37

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

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

res
źródło
To przenosi moje pytanie dotyczące tetracji na zupełnie nowy poziom!
MrZander
1
Był kiedyś podobny konkurs programistyczny o nazwie Bignum Bakeoff. Niektóre wpisy są dość interesujące; wyniki są tutaj: djm.cc/bignum-results.txt
Danny Chia

Odpowiedzi:

11

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

Peter Taylor
źródło
f_ (ω ^ ω) (2) jest mniej więcej tak duże jak g_ (f_8 (8)), więc nie jest tak przesadne, jak sugerowałoby to wyrażenie.
Po prostu piękna sztuka,
21

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.

przestał się obracać w lewo
źródło
Kiedy przetestować z print$((flip((%3)%(3*))3)%2)1, tam jest błąd run-time - można powiedzieć, dlaczego? Udaje się, gdy 2zmieniono na 1(wynik wynosi 81).
res
Och ... ideone wydaje się działać w wersji 32-bitowej, więc Intszybko się przepełnia . W systemie 64-bitowym, który zużywa zbyt dużo pamięci do odtworzenia, ale oczywiście nadal nie pozwala na dostęp G. Potrzebuję typu (big-int) Integer, więc nie mogę użyć !!; czekaj ...
przestał się obracać przeciwnie do zegara
Naprawiono to teraz, trzeba było użyć jawnej rekurencji do wdrożenia %.
przestał się obracać w lewo o
Uważam, że w ((%3)%(3*))2 nrzeczywistości rośnie szybciej niż mówisz ( dobra rzecz), ale mój Haskell-fu nie jest w stanie zrozumieć, dlaczego. Bo n = 0, 1, 2, ...zamiast dawać 3, 3^3, 3^(3^3), ..., daje 3, 3^(3+1), 3^((3^(3+1))+1), ....
res
Jak powiedziałem: „ ((%3)%(3*))n 3jest większy niż 3 ↑ⁿ 3”. Czy masz na myśli coś innego? W każdym razie zmieniłem definicję, aby wszystkie były równe (przynajmniej tak myślę, aby leniwie sprawdzić teraz ...), a nie większe. A jeśli zmienisz się 66na 65, to Gsam się produkuje , czy to nie miłe?
przestał obracać przeciwnie do zegara
5

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 ↑ 2 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.

KSmarts
źródło
3

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))
beary605
źródło
wyjście na standardowe wyjście? potrzebujesz także returnoświadczenia lub lambda.
stoisko
7
Również jeśli A (m, n) zwraca pojedynczą wartość, to czy A (A (5,5)) nie ma argumentu? ... Jest to problem związany z takim wyzwaniem: zachęca ludzi, aby nie testowali swojego kodu, ponieważ pełne uruchomienie jest czysto teoretyczne.
breadbox
Jeśli zamienisz swój ostatni wiersz na exec'x=A(x,x);'*x;print x, wówczas program jest w porządku, a wynik jest w przybliżeniu f_ (ω + 1) (x) (zakładając, że kod funkcji Ackermanna jest poprawny), który ma więcej niż G bajtów nawet dla x = 99, powiedzmy . (W moim programie Ruby f[m,n]jest to wersja A(m,n).)
res
@breadbox - Dobra uwaga ... Takie teoretyczne pytania wymagają od nas upewnienia się, że program jest odpowiedni dla przypadków testowych o małych parametrach (tj. nie-teoretycznych), które wyraźnie uogólniają, aby dać poprawną odpowiedź.
res
1
Jest dłuższy, ale jeśli chcesz użyć evalzamiast exec, twoja ostatnia linia może być f=lambda x:A(x,x);print eval('f('*x+'x'+')'*x). Ponadto twoja def A (m, n) musi zostać skorygowana według komentarza boothby.
res
2

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.

Po prostu piękna sztuka
źródło
0

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.

Bakuriu
źródło
2
Twoje 74-bajtowe rozwiązanie nie zapewnia wystarczająco dużej wydajności.
lirtosiast,
0

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)
SuperJedi224
źródło
0

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

Naruyoko
źródło
Jeśli zaznaczyłeś ten niekonkurencyjny ze względu na to, że język jest nowszy niż pytanie, nie musisz już tego robić
Jo King