Menguji apakah bukti arbitrer adalah bundar?

13

Saya sedang memikirkan bukti dan berlari ke pengamatan yang menarik. Jadi bukti setara dengan program melalui Curry-Howard Isomorphism, dan bukti melingkar sesuai dengan rekursi tak terbatas. Tapi kita tahu dari masalah penghentian bahwa dalam pengujian umum apakah program sewenang-wenang berulang selamanya tidak dapat diputuskan. Oleh Curry-Howard, apakah itu berarti tidak ada "pemeriksa bukti" yang dapat menentukan apakah bukti menggunakan penalaran melingkar?

Saya selalu berpikir bahwa bukti seharusnya terdiri dari langkah-langkah yang mudah diperiksa (yang sesuai dengan penerapan aturan inferensi), dan memeriksa semua langkah memberi Anda keyakinan bahwa kesimpulannya akan menyusul. Tapi sekarang saya bertanya-tanya: mungkin sebenarnya tidak mungkin untuk menulis pemeriksa bukti seperti itu, karena tidak ada cara untuk mengatasi masalah penghentian dan mendeteksi alasan melingkar?

logic curry-howard hewasonlyacat
sumber

Jawaban:

15

Sebagian besar sistem bukti tidak memungkinkan untuk bukti melingkar yang tak terbatas, tetapi mereka melakukannya dengan membuat bahasa mereka menjadi non-Turing lengkap.

Dalam bahasa fungsional normal, satu-satunya cara untuk membuat program berjalan selamanya adalah dengan rekursi, dan dalam hal teori, biasanya kita melihat rekursi sebagai kombinator , program ketik : yaitu, dibutuhkan fungsi yang membuat panggilan ke argumen "diri" lainnya, dan mengubahnya menjadi fungsi rekursif tunggal.Y∀Sebuah.(Sebuah→Sebuah)→Sebuah

Sekarang, terapkan isomorfisma Curry-Howard pada hal ini: kita sekarang memiliki bukti bahwa, untuk setiap proposisi , jika menyiratkan sendiri, maka kita dapat membuktikan . Kita bisa membuktikan apa pun dengan cara ini!SebuahSebuahSebuah

Kuncinya di sini adalah bahwa kombinator-Y adalah built-in ke bahasa, itu diambil sebagai aksioma. Jadi, jika Anda menginginkannya tidak menyebabkan masalah, singkirkan saja sebagai aksioma!

Sebagian besar sistem pembuktian formal, karenanya, mengharuskan rekursi Anda dibuat dengan baik. Mereka hanya menerima fungsi yang mereka dapat buktikan akan berhenti. Dan sebagai hasilnya, mereka menolak beberapa program yang berhenti, tetapi mereka tidak dapat membuktikannya.

Coq melakukan ini dengan cara yang cukup terbatas: itu hanya mensyaratkan bahwa setiap fungsi rekursif memiliki argumen di mana setiap panggilan rekursif hanya menggunakan versi yang lebih kecil dari argumen itu. Agda melakukan hal serupa, tetapi dengan sedikit lebih suka memeriksa untuk menerima beberapa program lagi.

Ya ampun
sumber
1
Apakah Coq mengesampingkan beberapa teorema yang sah yang bisa Anda buktikan? Atau apakah selalu ada penyelesaian ketika pemeriksa totalitas terlalu konservatif? (Saya menganggap jawabannya sama dengan asisten pembuktian lain berdasarkan pada teori tipe dependen?)
stovetop
1
@boyers FWIW, dalam Coq seseorang dapat menggunakan Functionatau Program Fixpointkonstruksi untuk membuktikan beberapa fungsi total jika pemeriksa total gagal. Contoh sederhana adalah fungsi gabungan-daftar. Kita perlu membuktikan secara manual kita membagi daftar (dengan panjang> 1) menjadi sublists yang lebih kecil.
Anton Trunov
@boyers Ya, harus ada hal-hal yang tidak dapat Anda buktikan dalam Coq, oleh teorema pertama Gödel. Dalam prakteknya jarang menemukan mereka, tetapi selalu ada argumen diagonal: Coq tidak dapat membuktikan Coq itu sendiri, ia hanya dapat membuktikan subset (subset yang sangat besar, pikiran, termasuk semua fitur tetapi dengan batas yang lebih rendah pada berapa banyak rekursi dapat menangani). Saya ingat pernah membaca bahwa teori Coq setara dengan aksioma Peano plus keberadaan ordinal besar tertentu (dan karenanya bukti yang mengasumsikan ordinal yang lebih besar tidak cocok), tetapi saya tidak dapat menemukan referensi sekarang.
Gilles 'SANGAT berhenti menjadi jahat'
@AntonTrunov Dalam konteks ini, Programdan sejenisnya adalah ikan haring merah. Mereka tidak mengubah teorinya. Apa yang mereka lakukan adalah sintaksis gula untuk menggunakan ukuran dalam bukti: daripada alasan bahwa objek yang Anda minati semakin kecil, Anda menambahkan tingkat tipuan: menghitung beberapa objek lain menjadi lebih kecil (misalnya beberapa ukuran) dan membuktikannya bahwa semakin kecil. Lihat Wfperpustakaan.
Gilles 'SANGAT berhenti menjadi jahat'
@Gilles Saya berasumsi konteksnya adalah tentang sisi praktis (konkret), seperti ketika heuristik Coq gagal ... Bisakah Anda mencoba menemukan kertas yang Anda sebutkan? Tautan akan sangat dihargai.
Anton Trunov