Fungsi TREE (k) memberikan panjang urutan pohon terpanjang T ₁ , T ₂ , ... di mana setiap simpul diberi label dengan salah satu warna k, pohon T _i memiliki paling banyak i simpul, dan tidak ada pohon yang merupakan minor dari sembarang pohon yang mengikutinya dalam urutan.

TREE (1) = 1, dengan misalnya T ₁ = (1).

TREE (2) = 3: misal T ₁ = (1); T ₂ = (2)--(2); T ₃ = (2).

TREE (3) adalah angka yang sangat besar . Bahkan lebih besar dari angka Graham. Tugas Anda adalah menghasilkan angka yang bahkan lebih besar dari itu!

Ini adalah kode-golf sehingga tujuannya adalah untuk menulis program terpendek dalam bahasa apa pun yang secara pasti menghasilkan angka yang lebih besar atau sama dengan TREE (3) (ke stdout).

• Anda tidak diizinkan mengambil input.
• Program Anda akhirnya harus dihentikan tetapi Anda dapat menganggap mesin memiliki memori tak terbatas.
• Anda mungkin berasumsi tipe nomor bahasa Anda dapat memiliki nilai terbatas, tetapi perlu menjelaskan bagaimana ini sebenarnya bekerja dalam bahasa Anda (mis: apakah float memiliki ketelitian tak terbatas?)
  • Infinities tidak diizinkan sebagai output.
  • Underflow dari tipe angka melempar pengecualian. Itu tidak membungkus.
• Karena TREE (3) adalah angka yang sangat kompleks, Anda dapat menggunakan pendekatan hierarki yang tumbuh cepat f _{ϑ (Ω ^ω ω) +1} (3) sebagai angka untuk dikalahkan.
• Anda perlu memberikan penjelasan mengapa nomor Anda begitu besar dan versi kode Anda yang tidak diklik untuk memeriksa apakah solusi Anda valid (karena tidak ada komputer dengan memori yang cukup untuk menyimpan TREE (3) )

Catatan: Tidak ada jawaban yang saat ini ditemukan di sini berfungsi.

Mengapa TREE (3) begitu besar?

Ruby Baru, 135 byte, >> H _{ψ (φ 3 (Ω + 1))} (9)

di mana H adalah hierarki Hardy, ψ adalah versi diperpanjang dari OCF Madore (akan dijelaskan di bawah) dan φ adalah fungsi Veblen.

Cobalah 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

Tidak digabungkan: (menggunakan fungsi, bukan lambdas)

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

OCF Madore yang diperluas:

Dan (secara kasar) fungsi phi Veblen:

Penjelasan tanpa tata cara:

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]

Program saya dimulai k = 9, h = [[],9,9]. Ini kemudian berlaku k = k*kdan h = f(h,k)sampai h == 0dan keluar k.

Penjelasan dengan tata cara:

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]

ψ '(ω ∙ α) ≈ ψ (α), fungsi runtuh ordinal yang dijelaskan pada gambar di atas.

Program saya kurang lebih memulai k = 9dan h = Ω(↑9)9, kemudian menerapkan k ← k²dan h ← h[k,h]sampai h = 1dan kembali k.

Jadi jika saya melakukan ini dengan benar, [[],9,9]jauh lebih besar dari ordinal Bachmann-Howard ψ (Ω ^{Ω Ω ...} ), yang jauh lebih besar dari ϑ (Ω ^ω ω) +1.

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

Dan jika analisis saya benar, maka kita harus memiliki ψ '(Ω ^Ω ∙ x) ~ = ψ * (Ω ^Ω ∙ x), di mana ψ * adalah fungsi psi normal Madore. Jika ini berlaku, maka ordinal saya kira-kira ψ * (φ ₃ (Ω + ω)).

Ruby Lama, 309 byte, H _{ψ ' 0 (Ω 9 )} (9) (lihat riwayat revisi , selain yang baru jauh lebih baik)

Haskell, 252 Bytes, TREE (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

Terima kasih atas bantuan dari H.PWiz, Laikoni dan Ørjan Johansen untuk bantuan golf kode!

Seperti yang disarankan oleh HyperNeutrino , program saya menghasilkan TREE (3) +1, tepatnya (TREE dapat dihitung karena ternyata).

T n cadalah pohon dengan label cdan node n. charus 1, 2atau 3.

l tadalah jumlah node dalam pohon t.

t1 # t2benar jika t1ditanamkan secara homomorfis t2(berdasarkan Definisi 4.4 di sini ), dan salah sebaliknya.

a nmenghasilkan daftar besar pohon. Daftar pastinya tidak penting. Properti penting adalah bahwa a nmengandung setiap pohon sampai nnode, dengan node dicap dengan 1, 2atau 3, dan mungkin beberapa pohon yang lebih juga (tapi pohon-pohon lain juga akan diberi label dengan 1, 2atau 3). Juga dijamin untuk menghasilkan daftar yang terbatas.

s ndaftar semua urutan panjang npohon, sehingga kebalikannya (karena kita membangunnya mundur) dari urutan itu valid. Sebuah urutan valid jika elemen ke-n (di mana kita mulai menghitung pada 1) memiliki paling banyak n node, dan tidak ada pohon yang di-embed secara homeomorfik menjadi yang berikutnya.

mainmencetak terkecil nsehingga tidak ada urutan panjang yang valid n.

Karena TREE(3)didefinisikan sebagai panjang urutan valid terpanjang, TREE(3)+1adalah yang terkecil nsehingga tidak ada urutan panjang yang valid n, yang merupakan hasil keluaran program saya.

Python 2, 194 byte, ~ H _{ψ (Ω ^{Ω Ω} )} (9)

di mana H adalah hierarki Hardy, dan ψ adalah fungsi runtuh ordinal di bawah ordinal Bachmann-Howard yang didefinisikan oleh Pohlers.

Terima kasih kepada Jonathan Frech untuk -3 byte.

def S (T): return 0jika T ==1sels [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 if U == 1else [R (U)] * c + V jika U else V
A = [[[1,1], 1], 0]
c = 9
sedangkan A: A = R (A); c * = c
cetak c

Cobalah online!

Versi spasi lebih baik:

def S (T):
  kembalikan 0 jika T == 1 lainnya [S (T [0])] + T [1:]

def R (T):
  U = T [0]
  V = T [1:]
  global B
  jika T [-1] == 0:
    B = T
  jika U == 1: 
    return [S (B)] + V
  return [R (U)] * c + V jika U else V

A = [[[1,1], 1], 0]
c = 9
sementara A:
  A = R (A)
  c * = c
cetak c

Penjelasan:

Program ini mengimplementasikan varian dari Buchholz hydra , hanya menggunakan label 0 dan 1. Pada dasarnya, pada setiap langkah, kita melihat simpul daun pertama dari pohon, dan melihat apakah ada label dengan 0 atau 1.

-Jika simpul daun diberi label dengan 0, maka kami menghapus simpul daun, dan kemudian menyalin pohon mulai dari induk dari simpul daun c kali, semua salinan terhubung ke kakek-nenek dari simpul daun.

-Jika simpul daun diberi label dengan 1, maka kita mencari kembali ke akar sampai kita mencapai simpul leluhur yang berlabel 0. Mari S menjadi pohon mulai dari simpul leluhur itu. Misalkan S 'menjadi S dengan simpul daun yang dilabel ulang dengan 0. Ganti simpul daun dengan S'.

Kami kemudian ulangi proses itu sampai tidak ada yang tersisa selain simpul root.

Program ini berbeda dari prosedur hydra Buchholz normal dalam dua cara: Pertama, setelah kita melakukan prosedur di atas, kita melakukan rekur balik atas pohon, dan melakukan prosedur penyalinan label 0 yang dijelaskan di atas untuk setiap simpul leluhur dari simpul daun asli. Ini meningkatkan ukuran pohon, sehingga prosedur kami akan memakan waktu lebih lama dari pada Buchholz hydra yang normal, dan karenanya menghasilkan jumlah yang lebih besar pada akhirnya; Namun, itu masih akan berakhir karena ordinal yang terkait dengan pohon baru masih akan kurang dari pohon yang lama. Perbedaan lainnya adalah, daripada mulai dengan c = 1 dan bertambah 1 setiap kali, kita mulai dengan c = 9 dan kuadratkan setiap kali, karena mengapa tidak.

Pohon [[[1,1], 1], 0] sesuai dengan ordinal ψ (Ω ^{Ω Ω} ), yang jauh lebih besar dari ordinal ϑ (Ω ^ω ω), dan dengan demikian jumlah akhir kami yang dihasilkan sekitar H _{ψ (Ω ^{Ω Ω} )} (9) pasti akan melebihi TREE (3).

Ruby, 140 byte, ~ H _{ψ (Ω ^{Ω Ω} )} (81)

di mana H adalah hierarki Hardy , dan ψ adalah fungsi runtuh ordinal standar di bawah ordinal Bachmann-Howard, sebagaimana didefinisikan di sini .

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

Cobalah online!

Versi tidak disatukan:

def S (a)
  * v, u = a
  jika a == 1 
    kembali []
  lain
    return v + [S (u)]
  akhir
akhir  

def R (t)
  * v, u = t
  jika t [0] == []
    $ b = t
  akhir
  if u == 1
    return v + [S ($ b)]
  elsif u == []
    kembali v
  lain
    return v + [R (u)] * $ c
  akhir
akhir

$ c = 9

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

sementara a! = [] lakukan
  $ c * = 9
  a = R (a)
akhir

cetak $ c

Program ini mengimplementasikan hydra Buchholz dengan node yang berlabel [] dan 1, seperti yang dijelaskan dalam entri Python 2 saya.

Pohon [[], [1, [1,1]]] sesuai dengan ordinal ψ (Ω ^{Ω Ω} ), yang jauh lebih besar dari ordinal ϑ (Ω ^ω ω) = ψ (Ω ^{Ω ω ω} ), dan sehingga jumlah akhir kami yang dihasilkan sekitar H _{ψ (Ω ^{Ω Ω} )} (81) akan melebihi TREE (3).

Julia, 569 byte, Nomor Pemuat

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

Untuk menghemat sedikit kerja keras, saya memutuskan untuk memindahkan Loader.c ke Julia hampir satu untuk satu dan memadatkannya ke dalam blok kode di atas. Bagi mereka yang ingin melakukan perbandingan sendiri (baik untuk memverifikasi skor saya atau untuk membantu saya menemukan kesalahan atau meningkatkan kode saya), versi yang tidak diklik di bawah ini:

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

Tidak ada penghitungan sebelumnya karena saya membuat byte terlalu banyak kesalahan dalam golf agresif yang saya lakukan.

JavaScript, 190B, H _{ψ (ε Ω + 1 )} (9) _{Berdasarkan analisis ini}

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

Program ini adalah versi modifikasi dari terjemahan nomor urutan 225B ini dalam JavaScript . Untuk nomor urutan pasangan dan kode aslinya, lihat di sini .

Modifikasi dilakukan:

• Ini dalam JavaScript, bukan BASIC.
• Tidak ada iterasi (f _{ψ (Ω ω +1)} -> f _{ψ (Ω ω )} )
• Urutannya adalah (0,0) (1,1) (2,2), yang sesuai dengan inal (ε _{Ω + 1} ). _{Ini dalam ordinal Hardy-hierarki}