Apa yang membuat bahasa (dan jenis-sistemnya) mampu membuktikan teorema tentang istilah-istilahnya sendiri?

12

Baru-baru ini saya mencoba menerapkan Aille 's Cedille-Core , bahasa pemrograman minimalis yang mampu membuktikan teorema matematika tentang istilah-istilahnya sendiri. Saya juga telah membuktikan induksi untuk tipe data yang dikodekan dengan λ, yang menjelaskan mengapa ekstensi-nya diperlukan.

Nether kurang, saya masih bertanya-tanya dari mana ekstensi itu berasal. Kenapa mereka apa adanya? Apa yang membenarkan mereka? Saya tahu, misalnya, bahwa beberapa ekstensi, seperti rekursi, merusak bahasa sebagai sistem pembuktian. Jika saya memutuskan untuk juga memperpanjang CoC dengan primitif lainnya, bagaimana saya membenarkan? Saya memahami bukti normalisasi diperlukan, tetapi itu tidak membuktikan bahwa primitif "masuk akal".

Singkatnya, apa yang secara spesifik memenuhi syarat suatu bahasa (dan jenis sistemnya) sebagai suatu sistem yang mampu membuktikan teorema tentang istilah-istilahnya sendiri?

type-theory functional-programming constructive-mathematics Viktor Maia
sumber
Saya membaca sebuah blog yang terkait dengan pertanyaan ini, tetapi saya tidak dapat menemukannya sekarang :( Berisi kalimat "Sistem T sudah cukup!" Atau sesuatu seperti itu dan berbicara tentang sistem tipe dependen.
Labbekak
2
Ditemukan: queuea9.wordpress.com/2010/01/17/... Ini sebenarnya ditulis oleh Aaron Stump sehingga Anda mungkin sudah mengetahuinya.
Labbekak
Rekursi yang tidak dijaga "merusak" bahasa sebagai sistem bukti, rekursi yang dijaga tidak. Untuk membuktikan bahwa primitif itu masuk akal, saya katakan Anda membuat model. Dan untuk membuktikan teorema tentang istilah-istilahnya sendiri, diperlukan semacam isomorfisma Curry – Howard, dan tipe dependen sehingga hal-hal yang Anda buktikan (tipe) dapat berbicara tentang istilah Anda.
xavierm02

Jawaban:

5

[Self-advertising mengikuti, tapi saya pikir ini relevan.]

Ada beberapa pendekatan yang mungkin untuk pertanyaan ini. Salah satu cara (yang saya eksplorasi selama tesis PhD saya dalam konteks bahasa mirip-ML) adalah untuk memperluas sistem tipe dengan lapisan orde pertama, sehingga istilah bahasa dapat dimanipulasi sebagai objek dari logika yang mendasarinya . Tentu saja, Anda juga perlu memasukkan beberapa predikat sehingga ada sesuatu yang perlu diperhatikan. Dalam kasus sistem saya, predikat ini adalah persamaan istilah. Secara khusus, jika dan adalah istilah bahasa, maka tipe hanya dihuni jika dan memang setara (secara observasi). Anda bisa menggunakan quantifier orde pertama untuk menyandikan properti sepertiu t ≡ u t u ∀ v , ( λ x . x )tut≡utu∀v,(λx.x)v≡v dalam jenis, dan mereka dibuktikan dengan membangun program yang menghuninya.

Tentu saja Anda juga dapat mengasumsikan persamaan, dan ada beberapa bentuk kuantifier yang berbeda (diketik / tidak diketik, universal / eksistensial). Mekanisme ini dapat digunakan untuk alasan tentang program apa pun (mereka tidak harus terbukti mengakhiri atau bahkan mengetik). Satu-satunya kendala adalah bahwa program yang digunakan sebagai bukti harus dibuktikan berakhir oleh sistem (rekursi umum yang sewenang-wenang menyebabkan inkonsistensi).

Berikut adalah beberapa referensi jika Anda ingin memeriksanya:

Rodolphe Lepigre
sumber