Perhitungan fungsi berang-berang yang sibuk

Fungsi sibuk berang-berang max bergeser, $S(n)$ , memiliki nilai yang diketahui untuk . Adakah alasan mendasar dan struktural mengapa kita tidak dapat menemukan untuk ? Apa perbedaan dari dari ? Atau ? Di suatu tempat di sepanjang jalan harus ada beberapa perbedaan mendasar, jika akan, pada prinsipnya, dihitung untuk semua , jadi apa sebenarnya adalah perbedaan ini? $n\leq4$ $S(n)$ $n>4$ $n=4$ $n=5$ $n=6$ $S(n)$ $n$

computability busy-beaver PeteyPabPro
sumber

Jawaban:

Alasan mengapa tidak ada program yang dapat menghitung adalah bahwa jika Anda tahu apa adalah Anda dapat memutuskan masalah penghentian - Anda akan tahu kapan harus berhenti menunggu. Di sisi lain, untuk setiap ada program yang menghitung untuk semua - hanya menggunakan tabel. $S(n)$ $S(n)$ $m$ $S(n)$ $n \leq m$

Jika mungkin untuk membuktikan nilai untuk semua (yaitu, untuk semua kita dapat membuktikan untuk beberapa ) maka kita dapat menghitung dengan mencari melalui semua bukti ( ini mengasumsikan bahwa sistem bukti kami valid). Jadi untuk setiap sistem pembuktian ada nilai minimal yang Anda tidak dapat membuktikan bahwa untuk setiap . $S(n)$ $n$ $n$ $S(n) = \alpha$ $\alpha$ $S(n)$ $n$ $S(n) = \alpha$ $\alpha$

Akhirnya, alasan yang kita tahu mungkin karena adalah jumlah yang sangat kecil. Angka sedikit lebih besar, dan segala sesuatunya menjadi lebih rumit. Tidak ada alasan mendalam mengapa kita tahu tetapi tidak , sama seperti tidak ada alasan yang mendalam mengapa kita tahu Ramsey nomor tetapi tidak (meskipun angka Ramsey tentu saja dapat dihitung) . $S(4)$ $4$ $5$ $S(4)$ $S(5)$ $R(4)$ $R(5)$

Yuval Filmus
sumber

Terima kasih. Paragraf tengah pada dasarnya adalah apa yang saya pikirkan (dan itu adalah bukti dari Godel, benar?). Jadi sebenarnya bisa jadi memiliki bukti dalam sistem formal kami tetapi tidak.

S (4)

$S(4)$

S (5)

$S(5)$

PeteyPabPro

Agaknya. Jika tidak dapat dibuktikan tetapi benar bahwa juga tidak dapat dibuktikan, dan jadi kami memiliki pernyataan yang tidak dapat dibuktikan tidak dibantah.

S (n) = " S (n) "

$S(n)=\text{"}S(n)\text{"}$

S (n) \neq " S (n) "

$S(n)\neq\text{"}S(n)\text{"}$

Yuval Filmus

Anda masih belum benar-benar menjelaskan mengapa kita bisa begitu yakin S (4) benar, sementara S (5) atau lebih tinggi kita tidak pernah tahu. Apakah karena kita bukan 100% tentang S (4), tetapi hanya "sangat hampir" yakin?

Dan W

Kami 100% yakin tentang S (4). Saya tidak berpikir ada alasan mendalam di balik ketidaktahuan kita tentang S (5). Itu hanya batas pengetahuan kita saat ini.

Yuval Filmus

Saya percaya ada sistem bukti yang sangat kuat dan mesin turing 6 negara 2 warna sehingga dapat dibuktikan bahwa tidak ada bukti dalam sistem itu bahwa itu tidak akan pernah berhenti dan tidak akan berhenti sebelum algoritma apa pun yang dapat dibuktikan dalam sistem itu dalam karakter googol untuk akhirnya berhenti berhenti.

Timothy

Scott Aaronson membahas ini di sini . Dia dan rekan penulisnya menemukan batas atas eksplisit pada yang dapat dihitung. $n$ $S(n)$

PeteyPabPro
sumber

Bisakah Anda mengutip bagian yang relevan?

Evil

sudut lain, dengan sketsa jawaban tidak resmi, yang akan membutuhkan waktu lama untuk secara teknis menyempurnakannya dengan penelitian lebih lanjut (yaitu pada dasarnya adalah program penelitian): ada beberapa bukti awal bahwa batas dari apa yang dapat dihitung tentang Beaver Sibuk fungsi adalah ukuran kompleksitas algoritma, dengan dua referensi di bawah ini yang mengisyaratkan arah ini. [1] [2] secara kasar, TM kecil dengan status sangat sedikit tidak dapat mencapai "sebanyak" atau "perilaku canggih" seperti algoritma yang lebih kompleks dengan lebih banyak status. Oleh karena itu perhitungan tampaknya juga memiliki hubungan yang mendalam dengan kompleksitas Kolmogorov . [3] Cara lain untuk melihat ini adalah bahwa apa yang diketahui / dapat dihitung tentang fungsi Sibuk Berang-berang juga bertepatan dengan keadaan canggih dalam teorema otomatis membuktikan, yang (mirip dengan kemajuan teknologi) adalah perbatasan yang terus maju berdasarkan penelitian matematika & ilmu komputer.

[1] Masalah berang-berang yang sibuk, serangan milenium baru , van Heuveln et al

[2] Mesin Turing kecil dan kompetisi berang-berang umum yang disamaratakan , Michel

[3] Saat menjalankan masalah tersingkat , Batfai

vzn
sumber