Golf liczba większa niż DRZEWO (3)

47

Funkcja DRZEWO (k) podaje długość najdłuższej sekwencji drzew T 1 , T 2 , ... gdzie każdy wierzchołek jest oznaczony jednym z k kolorów, drzewo T i ma co najwyżej i wierzchołki, a żadne drzewo nie jest drobne z dowolnego drzewa następującego po nim w sekwencji.

DRZEWO (1) = 1, np. T 1 = (1).

DRZEWO (2) = 3: np. T 1 = (1); T 2 = (2)--(2); T 3 = (2).

DRZEWO (3) to duża, duża liczba. Nawet większa niż liczba Grahama. Twoim zadaniem jest wyprowadzenie jeszcze większej liczby !

Jest to więc celem jest napisanie najkrótszego programu w dowolnym języku, który deterministycznie wyprowadza liczbę większą lub równą TREE (3) (na standardowe wyjście).

  • Nie możesz przyjmować danych wejściowych.
  • Twój program musi ostatecznie zakończyć się, 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ę.
  • Ponieważ DRZEWO (3) jest tak złożoną liczbą, możesz użyć szybko rosnącej aproksymacji hierarchii f ϑ (Ω ω ω) +1 (3) jako liczby do pokonania.
  • Musisz podać wyjaśnienie, dlaczego Twój numer jest tak duży, oraz nieokreśloną wersję kodu, aby sprawdzić, czy Twoje rozwiązanie jest prawidłowe (ponieważ nie ma komputera z wystarczającą ilością pamięci, aby przechowywać TREE (3) )

Uwaga: Żaden z odpowiedziami obecnie znaleźć tu pracę.

Dlaczego TREE (3) jest taki duży?

PyRulez
źródło
9
@StepHen nie trywialnie. Dotarcie do drzewa (3) wymaga zupełnie nowego paradygmatu.
PyRulez
11
TREE(3)+1tam wygrywam
HyperNeutrino
1
@KSmarts Nie zdajesz sobie sprawy, że żadna z odpowiedzi nie jest bliska TREE (3)?
Simply Beautiful Art,
2
@MDXF Powiem „nie”, ponieważ użycie INT_MAX jest trochę oszustwem (w przeciwnym razie wydrukowanie INT_MAX spowoduje wygraną). Ogólnie rzecz biorąc, wydajność musi być taka sama dla każdego wystarczająco dużego systemu.
PyRulez

Odpowiedzi:

38

Nowy Rubin, 135 bajtów, >> H ψ (φ 3 (Ω + 1)) (9)

gdzie H jest hierarchią Hardy'ego, ψ jest rozszerzoną wersją OCF Madore (wyjaśni poniżej), a φ jest funkcją Veblena.

Wypróbuj online!

f=->a,n,b=a{c,d,e=a;a==c ?a-1:e ?a==a-[0]?[[c,d,f[e,n,b]],d-1,c]:c:[n<1||c==0?n:[f[c||b,n-1]],n,n]};h=[],k=9,k;h=f[h,p(k*=k)]while h!=0

Ungolfed: (używanie funkcji, nie lambdów)

def f(a,n,b)
  c,d,e = a
  if a == c
    return a-1
  elsif e
    if a == a-[0]
      return [[c,d,f(e,n,b)],d-1,c]
    else
      return c
    end
  else
    x = c || b
    if n < 1 || c == 0
      return [n,n,n]
    else
      return [f(x,n-1,x),n,n]
    end
  end
end

k = 9
h = [[],k,k]
while (h != 0) do
  k *= k
  p k
  h = f(h,k,h)
end

Rozszerzony OCF Madore:

wprowadź opis zdjęcia tutaj

I (nieuprzejmie) funkcja ph Veblena:

wprowadź opis zdjęcia tutaj

Objaśnienie bez porządków:

f(a,n,b) reduces an array recursively. (if no third argument given, it takes the first argument twice.)
f(k,n,b) = k-1, k is a positive int.
f([c,d,0],n,b) = f([c,0,e],n,b) = c
f([c,d,e],n,b) = [[c,d,f(e,n,b)],d-1,c], d ≠ -1 and c ≠ 0

f([a],0,b) = [0,0,0]
f([0],n,b) = [n,n,n]
f([],n,b) = f([b],n,b)
f([a],n,b) = [f[a,n-1,a],n,n]

Mój program się inicjuje k = 9, h = [[],9,9]. Następnie ma zastosowanie k = k*ki h = f(h,k)do h == 0i wyjścia k.

Objaśnienie z rzędnymi:

Ordinals follow the following representation: n, [], [a], [a,b,c], where n,d is a natural number and a,c are all ordinals.
x = Ord(y) if y is the syntactic version of x.
a[n,b] = Ord(f(a,n))
ω = Ord([0]) = Ord(f([a],-1,b))
n = Ord(n)
Ω = Ord([])
ψ'(a) = Ord([a])
ψ'(a)[n] = Ord(f([a],n))
φ(b,c) ≈ Ord([[0],b,c])
a(↓b)c = Ord([a,b,c]) (down-arrows/backwards associative hyper operators I designed just for ordinals)

We follow the following FS for our ordinals:
k[n,b] = k-1, k < ω
ω[n,b] = n(↓n)n
(a(↓b)0)[n,b] = (a(↓0)c)[n,b] = a
(a(↓b)c)[n,b] = (a(↓b)(c[n,b]))(↓b[n,b])a, b ≥ 0 and c > 0.
ψ'(a)[0,b] = 0(↓0)0
ψ'(a)[n,b] = (ψ'(a[n-1,a]))(↓n)ω, a > 0 and n ≥ 0. (also note that we've changed from [n,b] to [n,a].)
Ω[n,b] = ψ'(b)[n,b]

ψ '(ω ∙ α) ≈ ψ (α), funkcja zwijania porządkowego opisana na powyższym obrazku.

Mój program mniej lub bardziej wtajemniczeni k = 9i h = Ω(↑9)9, a następnie stosuje się k ← k²i h ← h[k,h]do czasu h = 1i wraca k.

I jeśli to zrobiłem dobrze, [[],9,9]jest znacznie większy niż porządek Bachmanna-Howarda ψ (Ω Ω Ω ... ), który jest znacznie większy niż ϑ (Ω ω ω) +1.

ψ (Ω (↓ 9) 9)> ψ (Ω (↓ 4) 3)> ψ (Ω Ω Ω ) +1> ψ (Ω Ω ω ω ) +1> ϑ (Ω ω ω) +1

A jeśli moja analiza jest poprawna, powinniśmy mieć ψ '(Ω Ω ∙ x) ~ = ψ * (Ω Ω ∙ x), gdzie ψ * jest normalną funkcją psi Madore. Jeśli tak się dzieje, mój porządek wynosi w przybliżeniu ψ * (φ 3 (Ω + ω)).


Old Ruby, 309 bajtów, H ψ ' 09 ) (9) (zobacz historię zmian , poza tym nowy jest o wiele lepszy)

Po prostu piękna sztuka
źródło
1
Mogłem przetestować mój program tylko pod kątem bardzo niewielu wartości, więc przepraszam, jeśli gdzieś popełniłem błąd.
Po prostu piękna sztuka
1
Bleh, powoli, ale pewnie, próbuję przemyśleć i naprawić wszystko, co widzę źle. :-( Takie nudne.
Po prostu piękna sztuka
1
Hmm ... więc $ f_ {ψ_0 (ψ9 (9))} (9) $ oznacza, że ​​potrzebujemy co najmniej ψ_9 (9) $ th słabo niedostępny główny poziom szybko rosnącej hierarchii z bazą 9, aby uzyskać więcej niż $ DRZEWO (3) $
Sekret
1
@ Sekret Nie, chciałem tylko trochę przeregulować, a wypracowanie wartości bliższej TREE (3) kosztowałoby mnie więcej bajtów do napisania. I nie ma tu żadnych niedostępnych kardynałów.
Po prostu piękna sztuka
1
Nitki golfowe: zdecydowanie możesz grać w golfa a.class!=Array, najbardziej idiomatyczne jest, !a.is_a? Arrayale najkrótsze, o czym myślę a!=[*a]. I metody można przekształcić w lambdas: f=->a,n=0,b=a{...}...f[x,y]aby uratować niektóre postacie i być może otworzyć możliwości refaktoryzacji, używając ich jako obiektów pierwszej klasy.
histocrat
23

Haskell, 252 bajtów, DRZEWO (3) +1

data T=T[T]Int
l(T n _)=1+sum(l<$>n)
a@(T n c)#T m d=any(a#)m||c==d&&n!m
l@(x:t)!(y:u)=l!u||x#y&&t!u
x!_=null x
a n=do x<-[1..n];T<$>mapM(\_->a$n-1)[2..x]<*>[1..3]
s 0=[[]]
s n=[t:p|p<-s$n-1,t<-a n,(l t<=n)>any(#t)p]
main=print$[x|x<-[0..],null$s x]!!0

Dziękujemy za pomoc H.PWiz, Laikoni i Ørjan Johansen za pomoc w grze w kod!

Jak sugeruje HyperNeutrino , mój program wypisuje TREE (3) +1 dokładnie (TREE jest obliczalny, jak się okazuje).

T n cto drzewo z etykietą ci węzłami n. cpowinny być 1, 2albo 3.

l tto liczba węzłów w drzewie t.

t1 # t2jest prawdą, jeśli t1homeomorficznie osadza się t2(w oparciu o definicję 4.4 tutaj ), a fałsz w przeciwnym razie.

a nwyświetla dużą listę drzew. Dokładna lista nie jest ważna. Ważne jest to, że właściwość a nzawiera każde drzewo do nwęzłów, przy czym węzły oznakowane 1, 2lub 3, a może kilka drzew, jak również (ale te inne drzewa zostaną również oznakowane 1, 2lub 3). Gwarantowane jest również wygenerowanie skończonej listy.

s nwypisuje wszystkie sekwencje długości ndrzew, tak aby odwrotność (ponieważ budujemy ją wstecz) tej sekwencji była poprawna. Sekwencja jest poprawna, jeśli n-ty element (od którego zaczynamy liczenie od 1) ma co najwyżej n węzłów, a żadne drzewo homeomorficznie nie osadzi się w późniejszym.

maindrukuje najmniejsze, ntak że nie ma prawidłowych sekwencji długości n.

Ponieważ TREE(3)jest zdefiniowany jako długość najdłuższej prawidłowej sekwencji, TREE(3)+1jest najmniejszy, ntak że nie ma prawidłowych sekwencji długości n, co wyprowadza mój program.

PyRulez
źródło
16

Python 2, 194 bajtów, ~ H ψ (Ω Ω Ω ) (9)

gdzie H jest hierarchią Hardy'ego, a ψ jest porządkową funkcją zwijania pod porządkiem Bachmanna-Howarda zdefiniowanym przez Pohlersa.

Podziękowania dla Jonathana Frecha za -3 bajty.

def S (T): zwraca 0, jeśli T == 1else [S (T [0])] + T [1:]
def R (T): U = T [0]; V = T [1:]; exec "global B; B = T" * (T [-1] == 0); return [S (B)] + V, jeśli U == 1else [R (U)] * c + V, jeśli U else V
A = [[[1,1], 1], 0]
c = 9
podczas gdy A: A = R (A); c * = c
drukuj c

Wypróbuj online!

Wersja z lepszymi odstępami:

def S (T):
  zwraca 0, jeśli T == 1 jeszcze [S (T [0])] + T [1:]

def R (T):
  U = T [0]
  V = T [1:]
  globalny B
  jeśli T [-1] == 0:
    B = T
  jeśli U == 1: 
    return [S (B)] + V
  zwróć [R (U)] * c + V, jeśli U jeszcze V

A = [[[1,1], 1], 0]
c = 9
podczas:
  A = R (A)
  c * = c
drukuj c

Wyjaśnienie:

Ten program implementuje wariant hydry Buchholza , używając tylko etykiet 0 i 1. Zasadniczo, na każdym kroku, patrzymy na pierwszy węzeł liścia drzewa i sprawdzamy, czy jest on oznaczony 0 lub 1.

-Jeśli węzeł liścia jest oznaczony cyfrą 0, usuwamy węzeł liścia, a następnie kopiujemy drzewo zaczynając od elementu nadrzędnego węzła liścia c razy, wszystkie kopie połączone z dziadkiem węzła liścia.

-Jeśli węzeł liścia jest oznaczony cyfrą 1, wówczas szukamy wstecz w kierunku korzenia, aż dojdziemy do węzła przodka oznaczonego 0. Niech S będzie drzewem zaczynającym się od tego węzła przodka. Niech S 'będzie S z węzłem liścia oznaczonym etykietą 0. Zastąp węzeł liścia literą S'.

Następnie powtarzamy ten proces, dopóki nie zostanie nam nic oprócz węzła głównego.

Ten program różni się od zwykłej procedury hydry Buchholza na dwa sposoby: Po pierwsze, po wykonaniu powyższej procedury, ponownie wykonujemy kopię zapasową drzewa i wykonujemy procedurę kopiowania etykiety 0 opisaną powyżej dla każdego węzła przodka oryginalnego węzła liścia. Zwiększa to rozmiar drzewa, więc nasza procedura potrwa dłużej niż zwykła hydra Buchholza, a zatem doprowadzi do większej liczby; jednak nadal będzie wygasać, ponieważ porządek związany z nowym drzewem nadal będzie mniej starym drzewem. Inna różnica polega na tym, że zamiast zaczynać od c = 1 i zwiększać 1 za każdym razem, zaczynamy od c = 9 i za każdym razem zwiększamy kwadrat, ponieważ dlaczego nie.

Drzewo [[[1,1], 1], 0] odpowiada porządkowej ψ (Ω Ω Ω ), która jest znacznie większa niż porządkowa ϑ (Ω ω ω), a więc nasza wynikowa liczba około H ψ (Ω Ω Ω ) (9) zdecydowanie przekroczy DRZEWO (3).

Deedlit
źródło
Nie tak golfowy przyjacielu :-)
Po prostu piękna sztuka
Wiem. Nie wiem, jak to jeszcze zmniejszyć, przynajmniej nie w Pythonie. Może spróbuję nauczyć się trochę Ruby.
Deedlit
Czy można umieścić R (T) w jednym wierszu?
Po prostu piękna sztuka,
@SimplyBeautifulArt Najprawdopodobniej tak ( link TIO ), choć niesprawdzony.
Jonathan Frech
@JonathanFrech Dzięki za pomoc! Niestety, kiedy próbowałem kodu, wyświetlił komunikat o błędzie „globalny B nie jest zdefiniowany”. Nie mam pojęcia, dlaczego powoduje to błąd, podczas gdy oryginalny kod nie, więc nie wiem, jak to naprawić.
Deedlit
6

Rubinowy, 140 bajtów, ~ H ψ (Ω Ω Ω ) (81)

gdzie H jest hierarchią Hardy'ego , a ψ jest standardową funkcją zwijania porządkowego pod porządkiem Bachmanna-Howarda, jak zdefiniowano tutaj .

s=->t{*v,u=t;t==1?[]:v<<s[u]}
r=->t{*v,u=t;$b=t[0][0]?$b:t;u==1?v<<s[$b]:u[0]?v+[r[u]]*$c:v}
$c=9
a=[],[1,[1,1]]
($c*=9;a=r[a])while a[0]
$c

Wypróbuj online!

Wersja bez golfa:

def S (a)
  * v, u = a
  jeśli a == 1 
    powrót []
  jeszcze
    return v + [S (u)]
  koniec
koniec  

def R (t)
  * v, u = t
  jeśli t [0] == []
    $ b = t
  koniec
  jeśli u == 1
    return v + [S ($ b)]
  elsif u == []
    return v
  jeszcze
    return v + [R (u)] * $ c
  koniec
koniec

$ c = 9

a = [[], [1, [1,1]]]

podczas gdy a! = [] zrobić
  $ c * = 9
  a = R (a)
koniec

wydrukuj $ c

Ten program implementuje hydrę Buchholza z węzłami oznaczonymi [] i 1, jak opisano w moim wpisie w Pythonie 2.

Drzewo [[], [1, [1,1]]] odpowiada porządkowej ψ (Ω Ω Ω ), która jest znacznie większa niż porządkowa ϑ (Ω ω ω) = ψ (Ω Ω ω ω ), i więc nasza końcowa liczba około H ψ (Ω Ω Ω ) (81) przekroczy DRZEWO (3).

Deedlit
źródło
Niech to ty i twoje 149 bajtów.
Po prostu piękna sztuka,
Ale Ruby wygrywa: P
Simply Beautiful Art
Golf nitpick: Zamiast pisać u==0?v:u==[]?vmożna pisać u==0?||u[0]?v, co oszczędza dwa bajty.
Po prostu piękna sztuka,
@SimplyBeautifulArt Dzięki za pomoc! Piłki z powrotem w sądzie. : D
Deedlit
2
D: <różnica 1 bajtów między nami jest najbardziej frustrującą rzeczą w historii.
Po prostu piękna sztuka,
6

Julia, 569 bajtów, numer modułu ładującego

r,/,a=0,div,0;¬x=x/2;r<s=r?s:0;y\x=y-~y<<x;+x=global r=(x%2!=0)<1+(+¬x);!x=¬x>>+x;√x=S(4,13,-4,x);S(v,y,c,t)=(!t;f=x=r;f!=2?f>2?f!=v?t-(f>v)%2*c:y:f\(S(v,y,c,!x)\S(v+2,t=√y,c,+x)):S(v,y,c,!x)$S(v,y,c,+x));y$x=!y!=1?5<<y\x:S(4,x,4,+r);D(x)=(c=0;t=7;u=14;while(x!=0&&D(x-1);(x=¬x)%2!=0)d=!!D(x);f=!r;x=!r;c==r<((!u!=0||!r!=f||(x=¬x)%2!=0)<(u=S(4,d,4,r);t=t$d);¬f&(x=¬x)%2!=0<(c=d\c;t=√t;u=√u));(c!=0&&(x=¬x)%2!=0)<(t=((~u&2|(x=¬x)%2!=0)<(u=1<<(!c\u)))\(!c\t);c=r);¬u&(x=¬x)%2!=0<(c=t\c;u=√t;t=9)end;global a=(t\(u\(x\c)))\a);D(D(D(D(D(BigInt(99))))))

Aby zaoszczędzić trochę miejsca na pracy, postanowiłem przenieść Loader.c do Julii prawie jeden na jednego i umieścić go w powyższym bloku kodu. Dla tych, którzy chcą dokonać porównań (aby zweryfikować moją punktację lub pomóc mi znaleźć błędy lub poprawić kod), poniżej znajduje się wersja bez golfa:

r,/,a=0,div,0;
¬x=x/2;
r<s=r?s:0;
y\x=y-~y<<x;
+x=global r=(x%2!=0)<1+(+¬x);
!x=¬x>>+x;
√x=S(4,13,-4,x);
S(v,y,c,t)=(
    !t;
    f=x=r;
    f!=2?
        f>2?
            f!=v?
                t-(f>v)%2*c
                :y
            :f\(S(v,y,c,!x)\S(v+2,t=√y,c,+x))
        :S(v,y,c,!x)$S(v,y,c,+x)
);
y$x=!y!=1?5<<y\x:S(4,x,4,+r);
D(x)=(
    c=0;
    t=7;
    u=14;
    while(x!=0&&D(x-1);(x=¬x)%2!=0) 
        d=!!D(x);
        f=!r;
        x=!r;
        c==r<(
            (!u!=0||!r!=f||(x=¬x)%2!=0)<(
                u=S(4,d,4,r);
                t=t$d
            );
            ¬f&(x=¬x)%2!=0<(
                c=d\c;
                t=√t;
                u=√u
            )
        );
        (c!=0&&(x=¬x)%2!=0)<(
            t=((~u&2|(x=¬x)%2!=0)<(u=1<<(!c\u)))\(!c\t);
            c=r
        );
        ¬u&(x=¬x)%2!=0<(
            c=t\c;
            u=√t;
            t=9
        )
    end;
    global a=(t\(u\(x\c)))\a
);
D(D(D(D(D(BigInt(99))))))

Nie liczyło się to wcześniej, ponieważ zrobiłem zbyt wiele błędnych rachunków w agresywnym golfie.

eaglgenes101
źródło
1
O jej. Jeszcze jeden dodatek do tego szaleństwa tego miejsca.
Po prostu piękna sztuka,
1
Ponadto, chociaż nie mam na to dowodów, myślę, że D (D (D (D (99)))) jest wystarczająco duży. : | Może D (D (D (99))) jest wystarczająco duży.
Po prostu piękna sztuka,
1
Jeśli ktoś chce mi tutaj pomóc, następnym logicznym planem ataku jest wygenerowanie makra do kompaktowania „(x = ¬x)% 2! = 0” w makro jednoliterowe. Nie mogę sam rozgryźć makr Julii, więc ktoś inny może się tu przydać.
eaglgenes101
4

JavaScript, 190B, H ψ (ε Ω + 1 ) (9) Na podstawie tej analizy

A=[0,1,2];B=[0,1,2];for(F=C=9;F;F--){for(C++,G=0;G<=F;G++)(A[F]||A[F-G]<A[F]-H)&&(B[F]?(I=G,G=F):(H=A[F]-A[F-G],B[F-G]<B[F]&&(I=G,G=F)));for(J=0;J<C*I;J++)A[F]=A[F-I]+H,B[F]=B[F-I],F++;H=0}C

Ten program jest zmodyfikowaną wersją tego tłumaczenia numeru par 225B w JavaScript . Aby zobaczyć numer sekwencji i ich oryginalny kod, patrz tutaj .

Dokonane modyfikacje:

  • Jest w JavaScript zamiast BASIC.
  • Bez iteracji (f ψ (Ω ω +1) -> f ψ (Ω ω ) )
  • Sekwencja wynosi (0,0) (1,1) (2,2), co odpowiada porządkowi ψ (ε Ω + 1 ). Jest to porządek porządkowy w hierarchii Hardy'ego
Naruyoko
źródło