Apa perbedaan antara bukti dan program (atau antara proposisi dan tipe)?

Mengingat Curry-Howard Correspondence tersebar begitu luas / meluas, apakah ada perbedaan antara bukti dan program (atau antara proposisi dan tipe)? Bisakah kita benar-benar mengidentifikasi mereka?

Bahasa pemrograman yang digunakan orang sehari-hari tidak begitu cocok dengan korespondensi Curry-Howard, karena sistem tipenya terlalu lemah. Untuk mengatakan sesuatu yang menarik menggunakan Curry-Howard untuk program-program penting, seseorang perlu memiliki sistem tipe yang lebih canggih. Buku Adapting Proofs-as-programs mendorong sudut ini dengan tujuan mensintesis program-program penting. Dengan tipe dependen menjadi lebih dan lebih populer, tentu saja dalam bahasa fungsional penelitian ( Agda , Epigram ), perbedaannya menjadi lebih blurrier. Tentu saja Anda dapat melakukan sintesa / ekstraksi program dalam prover teorema Coq (dan mungkin yang lain), yang tentu saja didasarkan pada Curry-Howard.

Korespondensi Curry-Howard juga dapat digunakan dalam situasi di mana bukti tidak begitu jelas sesuai dengan program (atau mereka bukan program yang akan dijalankan oleh siapa pun). Salah satu contohnya adalah otorisasi pembawa bukti . Proposisi sesuai dengan pernyataan tentang siapa yang berwenang untuk melakukan apa. Bukti memberikan bukti yang diperlukan yang dimiliki oleh suatu proposisi, sehingga permintaan otorisasi diizinkan. Untuk menyandikan bukti, istilah bukti diperkenalkan (melalui Curry-Howard). Ketentuan bukti dikirim antar pihak sebagai representasi bukti validitas permintaan otorisasi, tetapi tidak dianggap sebagai program.

Dalam Coq, ada 2 jenis (Prop dan Set), mereka digunakan oleh programmer untuk memisahkan apa bukti yang tidak akan menghasilkan kode aktual dan bagian dari bukti yang akan digunakan untuk mengekstrak kode yang sedang berjalan (program Anda).

Itu adalah solusi yang bagus untuk masalah yang Anda tanyakan, bagaimana mengidentifikasi apa yang dimaksudkan untuk menghasilkan kode mesin (program) dan apa yang ada untuk melengkapi bukti proposisi (atau tipe).

AFAIK tidak ada cara otomatis untuk membedakan keduanya. Ini mungkin sesuatu yang menarik untuk penelitian? Atau mungkin seseorang dapat menunjukkan bahwa itu jelas tidak mungkin?

Dengan tipe dependen tidak hanya tidak ada perbedaan yang jelas antara bukti dan program tetapi juga tidak ada perbedaan antara program dan tipe! Satu-satunya perbedaan adalah di mana jenis (atau program) muncul, menjadikannya bagian dari tempat "program" atau tempat "tipe" dari istilah yang diberikan.

Sebuah contoh akan membuatnya lebih jelas, saya harap:

Ketika Anda menggunakan fungsi identitas dengan tipe dependen, Anda harus melewati tipe yang akan digunakan fungsi itu! Jenis ini digunakan sebagai nilai dalam "program" Anda!

Kalkulus Lambda yang tidak diketik:

$\lambda{x}.x$

Dengan Jenis Tanggungan:

id: (A: Set) -> A -> A

$(\lambda{A}.(\lambda{x}.x))$

Jika Anda menggunakan fungsi ini, maka Anda akan melakukannya seperti contoh ini:

id Naturals 1

Perhatikan bahwa "tipe" (dalam hal ini Set of Naturals) dilewatkan sebagai nilai yang dibuang sehingga tidak akan pernah dihitung, tetapi tetap berada di bagian "program" dari istilah tersebut. Itu yang juga akan terjadi dengan bagian "bukti", mereka harus ada di sana untuk istilah untuk mengetik-periksa tetapi selama perhitungan mereka akan dibuang.

Saya akan mengambil risiko di sini dan mengatakan bahwa, jika Anda mau sedikit menyipit, bukti dan program terminasi dapat diidentifikasi.

Setiap program penghentian adalah bukti bahwa Anda dapat mengambil inputnya dan menghasilkan outputnya. Ini adalah jenis bukti implikasi yang sangat mendasar.

Tentu saja, untuk membuat implikasi ini membawa informasi lebih bermakna daripada menyatakan yang jelas, Anda harus dapat menunjukkan bahwa program bekerja untuk setiap dan semua contoh input yang diambil dari beberapa kelas dengan makna logis. (Dan juga untuk hasilnya.)

Dari arah lain, bukti apa pun dengan langkah inferensi terbatas adalah program simbolik yang memanipulasi objek dalam beberapa sistem logis. (Jika kita tidak terlalu khawatir tentang apa arti simbol dan aturan logis secara komputasi.)

$\exists x : x \vdash T$

Ini cukup sederhana, tapi saya pikir itu menunjukkan kekokohan ide. (Bahkan jika beberapa orang terikat untuk tidak menyukainya. ;-))

Bukti tidak relevan?

Ketika Anda menulis beberapa program, Anda tertarik dengan kinerjanya, konsumsi memori, dll.
Misalnya, lebih baik menggunakan beberapa algoritma pengurutan yang pintar daripada bubble sort, bahkan jika implementasinya memiliki tipe yang sama (bahkan dalam pengaturan tipe dependen).

Tetapi ketika Anda membuktikan beberapa teorema, itu hanya keberadaan bukti yang Anda minati.

Tentu saja, dari sudut pandang estetika, beberapa bukti lebih sederhana / indah / inspiratif / dll (misalnya bukti dari Buku).

Jika Anda menerima korespondensi Curry-Howard maka pertanyaannya adalah pertanyaan filosofis. "Apakah bukti dan program berbeda? Tentu saja. Bagaimana? Yah, kami menyebut bukti sebagai 'bukti' dan kami menyebut program 'program'."

Atau dengan kata lain, jika ada isomorfisme antara bukti dan program — yang tampaknya jelas ada — maka pertanyaan Anda adalah apakah ada oracle yang mampu membedakan keduanya. Manusia mengkategorikan mereka sebagai yang berbeda (untuk sebagian besar), jadi tentu saja dapat diperdebatkan bahwa oracle semacam itu ada. Pertanyaan penting kemudian menjadi apakah ada perbedaan yang berarti di antara mereka, yang cocok untuk debat filosofis. Apa itu "bukti"? Tidak ada definisi formal tentang apa yang merupakan bukti; itu istilah seni, mirip dengan gagasan "dapat dihitung secara efektif" dalam tesis Gereja-Turing. Untuk itu, "program" juga tidak memiliki definisi formal.

Ini adalah kata-kata bahasa alami yang digunakan untuk mengkategorikan berbagai bidang penyelidikan matematika. Apa yang diamati Curry dan Howard adalah bahwa kedua bidang yang berbeda ini ternyata mempelajari hal yang sama. Memperhatikan hubungan ini penting karena dikatakan bahwa para peneliti yang berbeda ini harus berbicara satu sama lain. Tetapi di tingkat lain, memperhatikan hubungan itu dengan mempercayai perbedaan di antara mereka. Saat menangani masalah, terkadang lebih bermanfaat untuk menganggapnya sebagai masalah pemrograman, sedangkan di lain waktu lebih menguntungkan untuk menganggapnya sebagai masalah logis. Perbedaan perspektif ini, saya pikir, perbedaan penting di antara mereka. Tetapi apakah perbedaan perspektif merupakan perbedaan identitas adalah pertanyaan filosofis yang mendalam yang telah dieksplorasi setidaknya sejauh FregeUeber Sinn und Bedeutung .