Penjelasan sederhana mengapa fungsi komputasi tertentu tidak dapat diwakili oleh istilah yang diketik?

Membaca makalah Pengantar Kalkulus Lambda , saya menemukan sebuah paragraf yang tidak terlalu saya mengerti, di halaman 34 (huruf miring saya):

Dalam masing-masing dari dua paradigma ada beberapa versi kalkulus lambda yang diketik. Dalam banyak sistem penting, terutama yang ala Gereja, istilah yang memiliki tipe selalu memiliki bentuk normal. Dengan tidak terselesaikannya masalah penghentian ini menyiratkan bahwa tidak semua fungsi yang dapat dihitung dapat diwakili oleh istilah yang diketik, lihat Barendregt (1990), Teorema 4.2.15. Ini tidak seburuk kedengarannya, karena untuk menemukan fungsi yang dapat dihitung yang tidak dapat diwakili, seseorang harus berdiri di atas kepala. Sebagai contoh dalam 2, urutan kedua mengetik lambda kalkulus, hanya fungsi rekursif parsial tidak dapat diwakili yang terjadi menjadi total, tetapi tidak dapat dibuktikan dalam analisis matematika (aritmatika urutan kedua).

Saya akrab dengan sebagian besar konsep-konsep ini, tetapi tidak konsep fungsi rekursif parsial, atau konsep fungsi total terbukti. Namun, ini bukan yang saya minati.

Saya mencari penjelasan sederhana mengapa fungsi komputasi tertentu tidak dapat diwakili oleh istilah yang diketik, serta mengapa fungsi tersebut hanya dapat ditemukan 'dengan berdiri di atas kepala seseorang.'

Mengingat Anda tidak ingin mempelajari konsep yang tepat, berikut adalah penjelasan intuitif. Dalam diskusi di bawah ini, "fungsi" selalu mengacu pada fungsi yang memetakan bilangan asli ke bilangan alami (mungkin tidak ditentukan pada beberapa argumen).

Bahasa pemrograman apa pun yang memiliki

1. sintaksis yang dapat dihitung dan aturan evaluasi, dan
2. mengimplementasikan setiap fungsi yang dapat dihitung total

tentu mengimplementasikan beberapa fungsi parsial .

Untuk melihat ini, anggaplah demikian halnya bahwa setiap fungsi yang dapat didefinisikan dalam bahasa ini adalah total. Karena bahasa tersebut memiliki sintaksis yang dapat dihitung, kami dapat menghitung semua definisi fungsi (hanya menyebutkan semua string dan memfilter yang menyebabkan kesalahan sintaksis). Karena aturan evaluasi dapat dihitung, asumsi kedua memungkinkan kita untuk menyimpulkan bahwa dalam bahasa kita, kita dapat mendefinisikan fungsi total eval(n,m)yang mengevaluasi fungsi yang ndapat didefinisikan ke- m( pada dasarnya ini adalah juru bahasa mini yang ditulis dalam bahasa itu sendiri). Tapi kemudian fungsinya

λ k . (1 + eval(k,k))

adalah fungsi total yang dapat didefinisikan yang berbeda dari setiap fungsi total yang dapat didefinisikan, suatu kontradiksi.

Cukup ketik -calculus memenuhi syarat pertama dan hanya mendefinisikan fungsi total. Karena itu tidak memenuhi syarat kedua.$\lambda$

Sejauh "berdiri di atas kepala Anda" yang bersangkutan, untuk -calculus yang sangat normal , cukup mudah untuk memberikan fungsi total yang tidak dapat didefinisikan dalam kalkulus, yaitu prosedur normalisasi itu sendiri. Tidak terlalu penting seberapa suka kalkulus normal Anda yang sangat normal, bisa jadi polymorphic -calculus, atau teori tipe Martin-Lof, atau Kalkulus konstruksi. (Latihan: jika Anda bisa menerapkan prosedur normalisasi, Anda bisa menerapkan di atas.)$\lambda$$\lambda$eval

Saya menemukan bahwa jawaban Merijn menangani bagian pertama dari pertanyaan Anda dengan cukup baik. Saya akan mencoba menjawab bagian kedua: mengapa menemukan fungsi yang dapat dihitung tetapi tidak dapat diwakili dalam polymorphic -calculus membutuhkan "berdiri di atas kepala".$\lambda$

Saya khawatir ini memerlukan beberapa penjelasan dari konsep-konsep yang Anda tidak tertarik. Fungsi recusive parsial adalah -term yang mewakili fungsi dari ke . Sebuah -istilah diterapkan pada perwakilan dari sejumlah alami dikirim ke jika dan hanya jika tidak tidak memiliki bentuk normal. Jika tidak ada nomor yang dikirim ke kami mengatakan bahwa fungsinya total . Sekarang idenya adalah bahwa tidak ada teori logis dapat membuktikan bahwa istilah$\lambda$$\mathbb{N}$$\mathbb{N}\cup\{\bot\}$$\lambda$$t$$n$$\bot$$t\ n$$\bot$$T$$t$mewakili fungsi total untuk setiap fungsi total , selalu ada "blind spot" di mana berakhir pada semua input , tetapi pernyataan$t$$t$$n$

adalah diputuskan di . Jika pernyataan di atas adalah dapat dibuktikan di , kita mengatakan bahwa fungsi diwakili oleh adalah provably Total . Bahwa tidak semua fungsi total yang provably total dalam merupakan konsekuensi dari (varian dari) Godel Ketidaklengkapan Teorema untuk .$T$$T$$t$$T$$T$

Sekarang intinya adalah bahwa sebagian besar program yang ingin kita tulis secara konkret (pengurutan daftar, grafik traversal, sistem operasi) bukan hanya fungsi total, tetapi juga terbukti total dalam sistem logis yang masuk akal, seperti Aritmatika Peano.

Sekarang untuk polymorphic -calculus. Dapat ditunjukkan bahwa istilah yang dapat diketikkan dalam kalkulus ini adalah istilah yang persisnya mewakili fungsi yang dapat dibuktikan total dalam Aritmatika Peano Orde Kedua. Aritmatika Peano Orde Kedua jauh, jauh lebih kuat daripada Aritmatika Peano biasa.$\lambda$

Ini berarti dengan penjelasan di atas bahwa ada istilah yang total tetapi tidak terbukti total, tetapi fungsi tersebut sangat jarang, karena mereka sudah jarang untuk Aritmatika Peano (dan jauh lebih jarang dalam teori orde kedua). Oleh karena itu pernyataan "berdiri di atas kepala Anda".

Saya merasa agak sulit untuk secara singkat menuliskan buktinya, tetapi saya harap penjelasan ini memberi Anda cukup intuisi untuk melihat mengapa istilah yang diketik sederhana tidak dapat mewakili semua istilah yang tidak diketik.

Kalkulus lambda yang diketik sederhana sangat normal. Setiap pengurangan akan membawa kita lebih dekat ke bentuk normal. Ketika fungsi diterapkan pada nilai tipe ia akan direduksi menjadi fungsi tipe . Dengan jumlah argumen terbatas, dibutuhkan sejumlah langkah reduksi yang terbatas untuk mencapai bentuk -normal, di mana tidak ada pengurangan lebih lanjut.$\beta$$f :: \alpha \rightarrow \beta \rightarrow \gamma$$\alpha$$\beta$$\beta \rightarrow \gamma$$\beta$

Untuk membandingkan ini dengan kalkulus lambda yang tidak diketik. Salah satu kombinator UTLC yang lebih terkenal adalah -combinator:$Y$

$Y = λf.(λx.f\; (x\; x))\; (λx.f\;(x\;x))$

Ketika kami mencoba mengurangi -combinator, hal berikut terjadi:$Y$

Apa pun fungsi yang kami lewati, kami terjebak dalam urutan pengurangan yang tak terbatas! Jika kita mencoba untuk menyematkan tipe STLC pada UTLC -combinator, kami dengan cepat menemukan ini tidak mungkin, karena aplikasi fungsi tidak menyusutkan tipe seperti yang diperlukan dalam STLC. The -combinator jelas dihitung (mewakili, menggunakan rekursi, konsep loop tak terbatas), namun tidak dapat diwakili dalam STLC, karena semua hal STLC yang sangat normalisasi.$Y$$Y$