Golf angka lebih besar dari TREE (3)

47

Fungsi TREE (k) memberikan panjang urutan pohon terpanjang T 1 , T 2 , ... 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 = (1).

TREE (2) = 3: misal T 1 = (1); T 2 = (2)--(2); T 3 = (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 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?

PyRulez
sumber
9
@ LANGKAH tidak sepele. Getting to Tree (3) membutuhkan paradigma yang sama sekali baru.
PyRulez
11
TREE(3)+1di sana saya menang
HyperNeutrino
1
@KSmarts Anda menyadari tidak ada jawaban di sana yang mendekati TREE (3)?
Simply Beautiful Art
2
@ MDXF Aku akan mengatakan tidak, karena menggunakan INT_MAX agak curang (jika tidak, cetak INT_MAX akan menang). Secara umum, output Anda harus sama untuk sistem yang cukup besar.
PyRulez

Jawaban:

38

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:

masukkan deskripsi gambar di sini

Dan (secara kasar) fungsi phi Veblen:

masukkan deskripsi gambar di sini

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


Ruby Lama, 309 byte, H ψ ' 09 ) (9) (lihat riwayat revisi , selain yang baru jauh lebih baik)

Seni Cukup Indah
sumber
1
Saya hanya bisa menguji program saya untuk nilai yang sangat sedikit, jadi permisi jika saya membuat kesalahan di suatu tempat.
Simply Beautiful Art
1
Bleh, perlahan tapi pasti mencoba memikirkan jalan dan memperbaiki apa pun yang saya lihat salah. :-( Sangat membosankan.
Simply Beautiful Art
1
Hmm ... jadi $ f_ {ψ_0 (ψ9 (9))} (9) $ berarti kita membutuhkan setidaknya $ ψ_9 (9) $ th tingkat kardinal lemah yang tidak dapat diakses dari hierarki yang tumbuh cepat dengan basis 9 untuk menjadi lebih besar dari $ TREE (3) $
Secret
1
@Secret Tidak, saya hanya ingin melakukan overshoot sedikit, ditambah bekerja lebih dekat dengan nilai TREE (3) akan dikenakan biaya lebih banyak byte untuk menulis. Dan tidak ada kardinal yang tidak bisa diakses yang digunakan di sini.
Simply Beautiful Art
1
Golf nitpicks: Anda pasti bisa bermain golf a.class!=Array, sebagian besar idiomatis adalah yang !a.is_a? Arrayterpendek yang bisa saya pikirkan a!=[*a]. Dan metode dapat dikonversi menjadi lambda: f=->a,n=0,b=a{...}...f[x,y]untuk menyimpan beberapa karakter dan mungkin membuka kemungkinan refactoring menggunakannya sebagai objek kelas satu.
histokrat
23

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.

PyRulez
sumber
16

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

Deedlit
sumber
Tidak begitu golf teman saya :-)
Simply Beautiful Art
Aku tahu. Saya tidak tahu cara menguranginya lebih jauh, setidaknya tidak dengan Python. Mungkin saya bisa mencoba mempelajari Ruby.
Deedlit
Apakah mungkin untuk menempatkan R (T) semua dalam satu baris?
Simply Beautiful Art
@SimplyBeautifulArt Kemungkinan besar ya ( tautan TIO ), meskipun belum diuji.
Jonathan Frech
@JonathanFrech Terima kasih atas bantuan Anda! Sayangnya, ketika saya mencoba kode Anda itu memberikan pesan kesalahan "global B tidak didefinisikan". Saya tidak tahu mengapa ini memberikan kesalahan sementara kode asli tidak, jadi saya tidak tahu bagaimana cara memperbaikinya.
Deedlit
6

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

Deedlit
sumber
Sial, Anda dan 149 byte Anda.
Simply Beautiful Art
Tapi Ruby untuk kemenangan: P
Simply Beautiful Art
Golf nitpick: Daripada menulis u==0?v:u==[]?vAnda bisa menulis u==0?||u[0]?v, yang menghemat dua byte.
Simply Beautiful Art
@SimplyBeautifulArt Terima kasih atas bantuannya! Balls kembali di pengadilan Anda. : D
Deedlit
2
D: <perbedaan 1 byte di antara kami adalah hal yang paling membuat frustrasi.
Simply Beautiful Art
6

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.

eaglgenes101
sumber
1
Oh sayang. 1 tambahan lagi untuk kegilaan tempat ini.
Simply Beautiful Art
1
Juga, sementara saya tidak punya bukti tentang ini, saya berpikir bahwa D (D (D (D (D (99)))))) cukup besar. : | Mungkin D (D (D (99))) cukup besar.
Simply Beautiful Art
1
Jika ada yang ingin membantu saya di sini, rencana logis serangan berikutnya adalah membuat makro untuk dipadatkan "(x = ¬x)% 2! = 0" menjadi makro huruf tunggal. Tidak dapat menemukan makro Julia sendiri, sehingga orang lain bisa berguna di sini.
eaglgenes101
4

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
Naruyoko
sumber