The Laver tabel memberikan contoh program yang belum ditampilkan untuk mengakhiri dalam sistem aksiomatik standar matematika ZFC tetapi yang berakhir pada saat kita menganggap aksioma kardinal yang sangat besar.
pengantar
Tabel Laver klasik adalah aljabar terbatas yang unik dengan himpunan yang mendasari dan operasi yang memenuhi identitas dan di mana untuk dan di mana .An
{1,...,2n}
*
x * (y * z)=(x * y) * (x * z)
x*1=x+1
x<2n
2n*1=1
Informasi lebih lanjut tentang tabel Laver klasik dapat ditemukan dalam buku Braids and Self-Distributivity oleh Patrick Dehornoy.
Tantangan
Apa kode terpendek (dalam byte) yang menghitung 1*32
dalam tabel Laver klasik dan berakhir tepat ketika ia menemukan sebuah n
dengan ? Dengan kata lain, program berakhir jika dan hanya jika ia menemukan dengan tetapi jika tidak berjalan selamanya.1*32<2n
n
1*32<2n
Motivasi
Sebuah peringkat-ke-rank cardinal (juga disebut I3-kardinal) adalah sangat besar tingkat infinity dan jika kita menganggap keberadaan seorang kardinal peringkat-ke-rank, maka seseorang dapat membuktikan lebih teorema daripada jika salah satu tidak mengasumsikan keberadaan kardinal pangkat-ke-pangkat. Jika ada kardinal peringkat ke peringkat, maka ada beberapa tabel Laver klasik di mana . Namun, tidak ada bukti yang diketahui di ZFC. Selain itu, diketahui bahwa paling sedikit di mana lebih besar dari (yang merupakan jumlah yang sangat besar karena fungsi Ackermann adalah fungsi yang tumbuh cepat). Oleh karena itu, program semacam itu akan bertahan untuk waktu yang sangat lama.An
1*32<2n
1*32<2n
n
1*32<2n
Ack(9,Ack(8,Ack(8,254)))
Ack
Saya ingin melihat seberapa pendek suatu program dapat ditulis sehingga kita tidak tahu apakah program berakhir menggunakan sistem aksiomatik standar ZFC tetapi di mana kita tahu bahwa program akhirnya berakhir dalam sistem aksiomatik yang jauh lebih kuat, yaitu ZFC + I3. Pertanyaan ini diinspirasi oleh pos Scott Aaronson baru-baru ini di mana Aaronson dan Adam Yedidia telah membangun mesin Turing dengan di bawah 8000 negara sehingga ZFC tidak dapat membuktikan bahwa mesin Turing tidak berakhir tetapi diketahui tidak akan berhenti ketika seseorang mengasumsikan hipotesis kardinal besar.
Bagaimana tabel Laver klasik dihitung
Ketika komputasi tabel Laver biasanya mudah untuk menggunakan fakta bahwa dalam aljabar yang , kita memiliki semua di .An
2n * x=x
x
An
Kode berikut menghitung tabel Laver klasik An
# table (n, x, y) mengembalikan x * y dalam A n tabel: = fungsi (n, x, y) jika x = 2 ^ n maka kembalikan y; elif y = 1 lalu kembalikan x + 1; selain itu kembali tabel (n, tabel (n, x, y-1), x + 1); fi; akhir;
Misalnya, input table(4,1,2)
akan kembali 12
.
Kode untuk table(n,x,y)
agak tidak efisien dan hanya dapat dihitung dalam tabel Laver dalam jumlah waktu yang wajar. Untungnya, ada banyak algoritma yang lebih cepat untuk menghitung tabel Laver klasik daripada yang diberikan di atas.A4
sumber
Ack(9,Ack(8,Ack(8,254)))
adalah batas bawah untuk tabel pertama di mana baris pertama memiliki periode 32, yaitu di mana1*16 < 2^n
?table(n,x,y)
, dan saya pikir akan membutuhkan antara 25 dan 30 negara untuk mengatur konstanta dan lingkaran luar. Satu-satunya perwakilan TM langsung yang dapat saya temukan di esolangs.org adalah esolangs.org/wiki/ScripTur dan tidak terlalu golf.Jawaban:
Binary Lambda Calculus, 215 bit (27 bytes)
kompilasi ke (menggunakan perangkat lunak di https://github.com/tromp/AIT )
Solusi ini sebagian besar disebabkan oleh https://github.com/int-e
sumber
CJam (
3632 byte)Dalam praktiknya, kesalahan ini keluar cukup cepat karena melebihi tumpukan panggilan, tetapi pada mesin tanpa batas teoretis itu benar, dan saya mengerti bahwa menjadi asumsi pertanyaan ini.
sebenarnya tidak benar jika kita men-cache nilai komputasi untuk menghindari penghitungan ulang. Itulah pendekatan yang saya ambil, menggunakan
j
operator (memoisasi) . Ini menguji A 6 dalam milidetik dan meluap pengujian tumpukan A 7 - dan saya benar-benar deoptimisedtable
untuk kepentingan golf.Pembedahan
Jika kita menganggap itu
n
dipahami dari konteksnya, alih-alihkita dapat menghapus kasus khusus pertama, memberi
dan masih bekerja karena
dan untuk yang lain
y
,jadi dengan induksi kita dapatkan
f(2^n, y) = y
.Untuk CJam ternyata lebih mudah untuk membalik urutan parameter. Dan alih-alih menggunakan rentang
1 .. 2^n
saya menggunakan rentang0 .. 2^n - 1
dengan mengurangi setiap nilai, jadi fungsi rekursif yang saya implementasikan adalahsumber
Pyth, 33 byte
Cobalah online! (Jelas bagian pengujian tidak termasuk di sini.)
sumber
fi
dalam kode?