Funkcja DRZEWO (k) podaje długość najdłuższej sekwencji drzew T ₁ , T ₂ , ... 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).

DRZEWO (2) = 3: np. T ₁ = (1); T ₂ = (2)--(2); T ₃ = (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 golf kodowy, 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?

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:

I (nieuprzejmie) funkcja ph Veblena:

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 ψ * (φ ₃ (Ω + ω)).

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

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.

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

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

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.

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}