Sebagai tindak lanjut dari program terminasi terpendek yang ukuran outputnya melebihi jumlah Graham dan Golf lebih besar dari TREE (3) , saya menyajikan tantangan baru.
Angka loader adalah angka yang sangat besar, yang agak sulit dijelaskan (karena itu sendiri merupakan hasil dari latihan kode golf dengan tujuan yang fleksibel). Ada definisi dan penjelasan di sini , tetapi untuk tujuan pengendalian diri, saya akan mencoba menjelaskannya nanti dalam posting ini juga.
Algoritma Ralph Loader yang digunakan menghasilkan salah satu angka terbesar dari semua algoritma (yang dapat dihitung) yang pernah ditulis! Memang, nomor Loader adalah angka "yang dapat dihitung" terbesar di Wiki Googology. (Dengan angka "yang dapat dihitung", itu berarti angka yang ditentukan dalam perhitungan.) Itu berarti bahwa jika jawaban menghasilkan angka yang lebih besar dari angka Loader dengan cara yang menarik (yaitu bukan hanya angka Loader +1), Anda bisa turun di Sejarah googologi! Yang sedang berkata, program yang menghasilkan sesuatu seperti nomor Loader +1 adalah jawaban yang benar-benar valid dan pesaing untuk pertanyaan ini; tapi jangan berharap ketenaran.
Tugas Anda adalah membuat program terminating yang menghasilkan angka lebih besar dari angka Loader. Ini kode-golf , jadi program tersingkat menang!
- Anda tidak diizinkan mengambil input.
- Program Anda akhirnya harus berakhir secara deterministik, tetapi Anda dapat menganggap mesin memiliki memori tak terbatas.
- Anda dapat menganggap jenis nomor bahasa Anda dapat menampung nilai terbatas apa pun, 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.
- 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 nomor Loader).
Jadi, inilah penjelasan nomor Loader. Lihat http://googology.wikia.com/wiki/Loader%27s_number dan tautan di dalamnya untuk detail yang lebih tepat. Secara khusus, ini berisi program yang menghasilkan angka Loader persis (menurut definisi).
The kalkulus konstruksi pada dasarnya adalah sebuah bahasa pemrograman dengan sifat yang sangat khusus.
Pertama-tama, setiap program yang valid secara sintaksis berakhir. Tidak ada loop tanpa batas. Ini akan sangat berguna, karena itu berarti bahwa jika kita menjalankan program kalkulus konstruksi yang sewenang-wenang, program kita tidak akan macet. Masalahnya adalah bahwa ini menyiratkan bahwa kalkulus konstruksi belum selesai.
Kedua, di antara bahasa lengkap non-Turing, itu adalah salah satu yang paling kuat. Pada dasarnya, jika Anda dapat membuktikan bahwa mesin Turing akan berhenti pada setiap input, Anda dapat memprogram fungsi dalam kalkulus konstruksi yang akan mensimulasikannya. (Ini tidak membuatnya turing lengkap, karena ada menghentikan mesin turing yang Anda tidak dapat membuktikan sedang berhenti.)
Nomor loader pada dasarnya adalah nomor berang-berang yang sibuk untuk kalkulus konstruksi, yang dimungkinkan untuk dihitung karena semua program coc berakhir.
Secara khusus, loader.c mendefinisikan fungsi yang disebut D. Kira-kira, D(x)iterasi semua bit-string kurang dari x, menafsirkannya sebagai program coc, menjalankan yang valid secara sintaksis, dan menggabungkan hasilnya (yang juga akan menjadi bitstring). Ini mengembalikan rangkaian ini.
Nomor pemuat adalah D(D(D(D(D(99))))).
Salinan kode yang lebih mudah dibaca dari wiki googolology
int r, a;
P(y,x){return y- ~y<<x;}
Z(x){return r = x % 2 ? 0 : 1 + Z (x / 2 );}
L(x){return x/2 >> Z(x);}
S(v,y,c,t){
int f = L(t);
int x = r;
return f-2 ? f>2 ? f-v ? t-(f>v)*c : y : P(f,P(S(v,y,c,L(x)), S(v+2,t=S(4,13,-4,y),c,Z(x)))) : A(S(v,y,c,L(x)),S(v,y,c,Z(x)));
}
A(y,x){return L(y)-1 ? 5<<P(y,x) : S(4,x,4,Z(r));}
D(x)
{
int f;
int d;
int c=0;
int t=7;
int u=14;
while(x&&D(x-1),(x/=2)%2&&(1)){
d = L(L(D(x))),
f = L(r),
x = L(r),
c - r||(L(u)||L(r)-f||(x/=2)%2&&(u=S(4,d,4, r),t=A(t,d)),f/2&(x/=2)%2&&(c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u))),
c&&(x/=2)%2&&(t=P(~u&2|(x/=2)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r)
u/2&(x/=2)%2&&(c=P(t,c),u=S(4,13,-4,t),t=9);
}
return a = P( P( t, P( u, P( x, c)) ),a);
}
main(){return D(D(D(D(D(99)))));}
sumber
Jawaban:
JavaScript, D ^ 6 (9) (
508501495492487485481 bytes)Ini adalah kode yang disandikan.
Kode yang didekodekan:
Kode yang diterjemahkan dan tidak ditandai (kondisi dan barang disimpan dari loader.c):
Dalam hal ini, diasumsikan:
NumberNumberAlgoritma pengodean / Penguraian:
Pengkodean dilakukan sebagai berikut:
Algoritma decoding:
Kompresi dilakukan dengan kode ini , centang hanya kotak terakhir. Karena ini akan mengkodekan save terbesar terlebih dahulu, ini bukan kompresi yang paling efisien, tapi saya juga tidak tahu bagaimana membuatnya lebih kecil jadi meh.
JavaScript, (339 karakter )
Kode ini akan mengambil string 16bit sebagai, mengubahnya menjadi string 8bit dengan biner (BE) yang sama, dan
evalitu.Kode yang didekodekan adalah kode yang disandikan di atas.
Bukti bahwa D ^ 6 (9)> D ^ 5 (99)
Untuk ini, kita akan membandingkan D (9) dan 99.
Dengan menjalankan kode secara manual, D (9) ditemukan sama dengan
(15*2^14849+1)*2^((15*2^14849+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^929+1)*2^((15*2^929+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^(15*2^59+1)))))))))))))))))))))))))))))))), dan bahkan D (0) sama dengan8646911284551352321.Jadi, D (9) >>> 99, dan karena D benar-benar meningkat, D ^ 6 (9)> D ^ 5 (99).
D(D(D(D(D(99)))))menjadiD(D(D(D(D(D(9)))))). Juga yang mengocok surat-surat itu.&&(1)untukD(x)kondisi loop./2ke>>1karenaNumberfor...inmenjadifor...of.evaluntukD, menghapusreturn.sumber
Python 3, D ^ 6 (9) (
608600599 bytes)Ini adalah kode yang disandikan. Diekstraksi:
Dalam hal ini, diasumsikan:
Ini pada dasarnya adalah port dari jawaban JavaScript saya . Untuk detail lebih lanjut, periksa yang itu.
Kompresi dilakukan dengan ini .
Saya tidak tahu banyak tentang Python, jadi pasti ada tempat untuk menyimpan byte.
Saya pikir sub-600 mungkin.sub-600 telah terbukti.Suntuk mengurangi tanda kurungu/2baris terakhir ketiga definisiDtou>>1, menyimpan byte dari mengompresnya ke karakter dengan karakter lain>>1.sumber
Ruby, D ^ 6 (9) (553 bytes)
Ini adalah kode yang disandikan. Diekstraksi:
Kode ini adalah Nomor Loader dengan D 6 (9) sebagai gantinya.
Dalam hal ini, diasumsikan:
Ini pada dasarnya adalah port dari jawaban JavaScript dan Python 3 saya . Untuk lebih jelasnya, periksa itu.
Kompresi dilakukan dengan ini (mungkin muncul karena tidak ada).
Saya seorang pemula di Ruby, jadi mungkin di bawah 512 adalah mungkin, tapi saya ragu.
sumber