Apa yang membuat inferensi tipe untuk tipe dependen tidak dapat diputuskan?

Saya telah melihatnya menyebutkan bahwa sistem tipe dependen tidak dapat disimpulkan, tetapi dapat diperiksa. Saya bertanya-tanya apakah ada penjelasan sederhana mengapa demikian, dan apakah ada atau tidak ada batas "ketergantungan" di mana jenis dapat diindeks oleh nilai-nilai, di bawah ini jenis inferensi yang mungkin dan di atas yang tidak?

Untuk versi yang agak sederhana dari teori tipe dependen, Gilles Dowek memberikan bukti ketakpastian kemampuan mengetik dalam konteks yang tidak kosong:

Gilles Dowek, Ketidakpastian kemampuan mengetik di -kalkulus$\lambda\Pi$

Yang bisa ditemukan di sini .

$\lambda$

Idenya adalah untuk menyandikan masalah korespondensi Post sebagai masalah konversi jenis, dan kemudian dengan hati-hati membangun istilah yang dapat diketik jika dua jenis spesifik dapat dikonversi. Ini menggunakan pengetahuan tentang bentuk bentuk normal, yang selalu ada dalam kalkulus ini. Artikel ini pendek dan ditulis dengan baik, jadi saya tidak akan membahas lebih detail di sini.

$\lambda$

JB Wells, Kemampuan Mengenal dan memeriksa tipe dalam Sistem F adalah setara dan tidak dapat diputuskan .

Ini dapat ditemukan di sini . Yang saya tahu tentang hal itu adalah bahwa itu mengurangi masalah semi-unifikasi (yang merupakan instantiasi modulo unifikasi kuantifiers universal, dan tidak dapat dipastikan) untuk mengetikkan pengecekan pada Sistem F.

Akhirnya cukup mudah untuk menunjukkan bahwa penghuni keluarga yang tergantung tidak dapat diputuskan: cukup menyandikan masalah Post ke dalam indeks konstruktor. Berikut ini beberapa slide karya Nicolas Oury yang menggambarkan sketsa itu.

Seperti apakah ada "batas", itu sangat tergantung pada apa yang Anda coba lakukan dengan tipe dependen Anda, dan ada banyak perkiraan yang mencoba menjadi decidable, atau setidaknya cukup dekat untuk dapat digunakan. Pertanyaan-pertanyaan ini masih merupakan bagian dari penelitian aktif.

Salah satu jalan yang mungkin adalah bidang "tipe penyempurnaan" di mana bahasa ekspresi dependensi tipe dibatasi untuk memungkinkan pemeriksaan lihat yang dapat ditentukan, misalnya Jenis Cairan . Jarang bahwa inferensi tipe penuh dapat ditentukan bahkan dalam sistem ini sekalipun.