Mengapa beberapa mesin inferensi perlu bantuan manusia sementara yang lainnya tidak?

^{Saya belajar Automated Teorema Membuktikan / SMT pemecah / Asisten Bukti sendiri dan posting serangkaian pertanyaan tentang proses, mulai di sini .}

Mengapa bahwa provers teorema otomatis, yaitu ACL2 , dan SMT pemecah tidak perlu bantuan manusia sementara bukti asisten, yaitu Isabelle dan Coq , lakukan?

^{Cari pertanyaan berikutnya seri di sini .}

Validitas rumus urutan yang lebih tinggi secara umum tidak dapat ditentukan dan ruang pencarian sangat besar , sehingga yang dapat Anda harapkan adalah mencoba menemukan bukti - dengan asumsi itu ada - dengan secara cerdik menyebutkan ruang bukti (pikirkan palu godam , tepat disebut) tapi itu kasar. Manusia bisa bermain oracle, menyediakan lemmata kunci untuk panduan bukti.

Prover otomatis, di sisi lain, biasanya hanya berurusan dengan logika (subset dari) yang dapat ditentukan, misalnya logika proposisional atau subkelas dari logika tingkat pertama, sehingga mereka dapat berjalan lama tetapi Anda tahu mereka akan berhasil pada akhirnya.

Perhatikan bahwa ada pendekatan untuk memungkinkan assisstants bukti untuk menemukan orang lemmata penting, misalnya IsaPlanner . Alat tebakan (induktif) lemmata oleh pencacahan dan pengujian acak dan kemudian mencoba untuk membuktikan mereka. Dengan iterasi proses, banyak lemmata dari misalnya tipe data yang khas definisi dapat ditemukan secara otomatis.

ABC kecil

• validitas - rumus ini berlaku memegang apa pun yang Anda tetapkan untuk variabel bebas.
• variabel bebas - variabel yang tidak terikat dengan bilangan seperti dan$\forall$$\exists$
• decidability - a (boolean) properti (Turing) decidable jika ada algoritma yang jawaban "ya" atau "tidak" (benar) setelah jumlah waktu yang terbatas.
• logika proposisional - juga orde nol logika ; tidak ada kuantifikasi diperbolehkan.
• $\forall x. P(x)$$\forall f. f(4) > 0$
• logika orde tinggi - Anda dapat mengukur lebih dari (dan "membangun") objek yang kompleks sewenang-wenang, misalnya fungsi orde tinggi (fungsi yang mengambil fungsi).

Saya akan mengatakan bahwa perbedaan klasik "otomatis membuktikan teorema" (ATP) vs "teorema interaktif pembuktian" (ITP) perlu dipertimbangkan. Jika Anda mengambil sistem ITP terkenal seperti Isabelle / HOL hari ini (Isabelle2013 dari Februari 2013), hal tersebut terintegrasi cukup banyak add-on alat dari portofolio ATP:

• On-board generik alat bukti otomatis: tua-sekolah alat Isabelle seperti fastdan blast(oleh L. Paulson) dan lebih baru provers otomatis seperti metis(oleh J. Hurd).

• ATP eksternal untuk Logika Orde Pertama yang dipanggil melalui Sledgehammer: E prover, SPASS, Vampire. Bukti yang ditemukan dianalisis untuk mengetahui lemon mana yang berkontribusi padanya, mengurangi 10.000 menjadi 10, dan memberi makan hasilnya metis.

• TPS eksternal dengan rekonstruksi bukti parsial, terutama untuk Z3 (oleh S. Boehme).

• Alat untuk menemukan contoh counter pernyataan yang belum terbukti: nitpick / Kodkodi (J. Blanchette) dan Quickcheck (L. Bulwahn).

Apakah semua yang otomatis hal make Isabelle sebuah otomatis prover teorema?

Pada akhirnya, saya pikir perbedaan "ATP" vs "ITP" hanyalah semacam "label" yang memberi tahu bagaimana Anda ingin memposisikan atau "menjual" sistem Anda: ATP mengklaim sebagai "alat tombol-tekan", tetapi dalam berlatih Anda akan harus berinteraksi (secara tidak langsung), dengan memberikan parameter atau petunjuk, atau reformulasi masalah Anda. Itu mungkin benar-benar cukup menantang, karena runtimes panjang yang umum-tempat di masyarakat ATP.

Sebaliknya, sistem ITP dibuat untuk orang-orang yang menunggu di tempat, dengan akses setengah layak untuk negara bukti internal, untuk melihat apa yang hilang untuk menyelesaikan bukti. Sebuah sistem ITP yang wraps up alat ATP dalam cara Isabelle mungkin berubah lebih menarik lebih banyak pengguna dan aplikasi yang lebih, daripada baik ITP atau ATP saja.