Apakah ada kalkulus lambda yang diketik lengkap dari Turing?

Apakah ada kalkulasi lambda yang diketik lengkap dari Turing? Jika demikian, apa beberapa contohnya?

Ya tentu. Banyak kalkulus lambda yang diketik hanya menerima istilah yang sangat normal , oleh desain, sehingga mereka tidak dapat mengekspresikan perhitungan sewenang-wenang. Tetapi sistem tipe bisa apa saja yang Anda suka; buat itu cukup luas, dan Anda dapat mengekspresikan semua perhitungan deterministik.

Sistem tipe sepele yang mencakup fragmen lengkap-Turing dari kalkulus lambda adalah sistem yang menerima setiap istilah yang diketik dengan baik (dengan tipe teratas ).

$$\dfrac{}{\Gamma \vdash M : \top}$$

Lebih praktis, bahasa pemrograman fungsional yang diketik secara statis pada intinya memiliki kalkulus lambda yang diketik yang memungkinkan kombinator fixpoint juga diketik dengan baik. Sebagai contoh, mulai dengan kalkulus lambda yang diketik sederhana (atau sistem tipe ML atau sistem F atau sistem tipe lain pilihan Anda) dan tambahkan aturan yang membuat beberapa kombinator fixpoint seperti diketik dengan baik. Γ ⊢ f : T → $\mathbf{Y} = \lambda f. (\lambda x. f (x\,x)) (\lambda x. f (x\,x))$ Aturan-aturan yang disajikan di atas agak canggung, karena mereka membuat istilah seperti

$$\dfrac{\Gamma \vdash f : T \rightarrow T} {\Gamma \vdash \mathbf{Y}\,f : T} \qquad \dfrac{\Gamma \vdash f : T \rightarrow T} {\Gamma \vdash (\lambda x. f (x\,x)) (\lambda x. f (x\,x)) : T}$$ diketik dengan baik meskipun konstituennya tidak diketik dengan baik - mereka tidak sepenuhnya komposisional. Perbaikan sederhana adalah menambahkan kombinator fixpoint sebagai konstanta bahasa dan memberikan aturan delta untuk itu; maka itu adalah masalah sederhana untuk memiliki sistem tipe dan semantik reduksi denganpengawetan tipe. Anda menjauh dari kalkulus lambda murni ke bidang kalkulus lambda dengan konstanta. $\mathbf{Y}\,f$ $$\begin{gather*} \dfrac{}{\Gamma \vdash \textbf{fix} : (T \rightarrow T) \rightarrow T} \\ \textbf{fix}\,f \to f (\textbf{fix}\,f) \\ \end{gather*}$$

Berpegang pada kalkulus lambda murni, sistem tipe yang menarik adalah kalkulus lambda dengan tipe persimpangan.

$$\dfrac{\Gamma \vdash M : T_1 \quad \Gamma \vdash M : T_2} {\Gamma \vdash M : T_1 \wedge T_2} (\wedge I) \qquad\qquad \dfrac{} {\Gamma \vdash M : \top} (\top I)$$

Jenis titik-temu memiliki sifat yang menarik sehubungan dengan normalisasi:

• $\top I$
• $\top$

Lihat Karakterisasi istilah lambda yang memiliki tipe serikat untuk wawasan tentang mengapa jenis persimpangan memiliki cakupan yang luar biasa.

Jadi, Anda memiliki sistem tipe yang mendefinisikan bahasa lengkap Turing (karena setiap istilah diketik dengan baik), dan karakterisasi sederhana penghentian komputasi. Tentu saja, karena sistem tipe ini mencirikan normalisasi, maka tidak dapat ditentukan.

_{$(\top I)$$(\wedge I)$$I$$\wedge$$\top$$\rightarrow$$\rightarrow$}