Mengapa Pemeriksa Bukti diperlukan dalam Bukti Membawa Kode

9

Dalam makalah PLDI'98 klasik karya Necula, "Desain dan implementasi kompiler sertifikasi", verifikasi tingkat tinggi menggunakan:

  1. VCGen untuk menghasilkan kondisi verifikasi (predikat keselamatan)
  2. Teorema logika orde pertama membuktikan kondisi
  3. Pemeriksa bukti LF untuk memeriksa bukti dari langkah (2)

Saya agak bingung dengan langkah (3). Mengapa itu diperlukan sama sekali? Apakah hanya (1) dan (2) tidak cukup? Mengapa kita tidak memercayai bukti yang dihasilkan oleh teorema teorema?

proof-theory automated-theorem-proving program-verification Ram
sumber

Jawaban:

19

Tujuan pemeriksa bukti adalah untuk meminimalkan basis komputasi tepercaya .

Dengan memiliki pemeriksa bukti, baik kompilator maupun teorema tidak perlu benar. Makalah ini menjelaskan hal ini pada Halaman 3:

Neither the compiler nor the prover need to be correct in order to be guaranteed to   
detect incorrect compiler output. This is a significant advantage since the VCGen and  
the  proof checker are significantly simpler than the compiler and the prover.

Pemeriksa bukti hanya beberapa baris kode, dan dapat diperiksa kebenarannya dengan tangan. Sebaliknya, prover otomatis yang berkinerja baik sangat kompleks dan tidak mungkin benar, meskipun dengan prover yang teruji dan digunakan secara luas, kesalahannya ada pada kasus tepi yang mungkin tidak mudah dipicu. Lihatlah kode LOC C 30k yang membentuk Lingeling , pemecah SAT yang canggih untuk melihat betapa rumitnya pembuktian teorema otomatis. Tanpa pemeriksa bukti, Anda harus membuktikan bahwa teorema itu benar. Ini melampaui apa yang secara ekonomi dapat kita lakukan di tahun 2015.

Martin Berger
sumber
Saya terkejut bahwa bukti yang dibuat oleh ATP bisa buggy. (Saya pikir ATP bisa tidak lengkap tetapi tidak tidak sehat / buggy) Saya kurang informasi di sini. Saya akan senang mengetahui jika ada contoh kesalahan mahal dalam bukti yang dihasilkan oleh ATP.
Ram
3
@ Ram Ada ribuan bug kesehatan kecil dalam sejarah setiap pepatah teorema otomatis yang serius. Lihat misalnya stackoverflow.com/questions/12281085/… atau riwayat revisi alat apa pun di github.
cody
@Ram Selain saran hebat Cody, saya sarankan untuk belajar dari pengalaman: menulis ATP kecil seperti pemecah SAT dasar. Itu bisa dilakukan dalam beberapa baris kode. Kemudian coba dan buat itu berkinerja baik dengan menambahkan misalnya belajar klausa, menonton literal atau heuristik pemilihan variabel yang menarik. Kemudian pikirkan tentang pengalaman ...
Martin Berger