Apakah ada kalkulus lambda yang diketik yang konsisten dan Turing lengkap?

Apakah ada kalkulus lambda yang diketik di mana logika yang sesuai di bawah korespondensi Curry-Howard konsisten, dan di mana ada ekspresi lambda yang diketik untuk setiap fungsi yang dapat dihitung?

Ini memang pertanyaan yang tidak tepat, tidak memiliki definisi yang tepat tentang "kalkulus lambda yang diketik." Saya pada dasarnya bertanya-tanya apakah ada (a) contoh yang diketahui dari ini, atau (b) bukti ketidakmungkinan yang diketahui untuk sesuatu di bidang ini.

Sunting: @cody memberikan versi yang tepat dari pertanyaan ini dalam jawaban di bawah ini: apakah ada sistem tipe murni logis (LPTS) yang konsisten dan Turing lengkap (dalam arti didefinisikan di bawah)?

type-theory lambda-calculus typed-lambda-calculus curry-howard Morgan Thomas
sumber

Tidak ada kalkulus yang dapat aksioma secara rekursif (lambda atau lainnya) yang fungsi rekursif totalnya dapat dibuktikan semuanya adalah fungsi rekursif, sehingga kalkulus Anda harus melibatkan istilah yang tidak berakhir.

Emil Jeřábek mendukung Monica

Jawaban ini memiliki teorema yang mengatakan Anda tidak dapat memiliki kalkulus apa pun yang lengkap-Turing dan total.

Andrej Bauer

Kemungkinan akan menjawab pertanyaan Anda setelah Anda membuatnya cukup tepat. Saya pikir bukti Andrej tidak perlu rumit (tapi itu menunjukkan lebih): intinya adalah bahwa jika ada sistem yang dijelaskan secara efektif di mana semua fungsi rekursif diwakili sedemikian rupa sehingga Anda dapat mensertifikasi secara sintaksis bahwa suatu ekspresi adalah representasi jujur dari suatu fungsi rekursif (misalnya, dengan memeriksa bahwa itu diketik dengan benar dalam sistem), maka Anda akan mendapatkan fungsi rekursif total universal, yang tidak mungkin.

Emil Jeřábek mendukung Monica

Tentu saja jawaban klasik untuk pertanyaan semacam ini bisa menjadi: diketik

kalkulus dengan jenis persimpangan , karena jenis setiap (dan hanya mereka) hal yang sangat normalisasi. Ini lebih merupakan pertanyaan filosofis untuk bertanya apakah kalkulus mengakui "interpretasi Curry-Howard".

λ

$\lambda$

cody

Sulit untuk lebih tepat di sini karena pertanyaannya tidak tepat.

Andrej Bauer

Jawaban:

Baiklah saya akan coba-coba: Secara umum untuk sistem tipe diberikan , berikut ini benar: $T$

Jika semua istilah tipe baik dalam kalkulus normal, maka $T$ adalahkonsistenbila dilihat sebagai logika. $T$

Buktinya umumnya hasil dengan asumsi Anda memiliki istilah tipe , menggunakan pengurangan subjek untuk mendapatkan bentuk normal, dan kemudian melanjutkan dengan induksi pada struktur istilah tersebut untuk mendapatkan kontradiksi. $\mathrm{absurd}$ $\mathrm{False}$

Itu wajar untuk bertanya-tanya apakah yang terjadi terus, yaitu

Untuk semua jenis sistem , jika adalah logis konsisten , maka setiap jangka baik diketik di adalah normalisasi. $T$ $T$ $T$

Masalah dengan ini adalah bahwa tidak ada gagasan nyata yang paling umum tentang "sistem tipe", dan bahkan kurang kesepakatan tentang makna konsistensi logis untuk sistem tersebut. Namun, kami dapat memverifikasi itu secara empiris

Untuk sistem tipe paling dikenal yang memiliki interpretasi logis, sebaliknya memang berlaku.

Bagaimana ini mengikat Turing Completeness? Sebagai contoh , jika pengecekan tipe dapat dilakukan , maka argumen Andrej menunjukkan bahwa salah satu dari yang berikut ini harus berlaku:

Himpunan semua program yang diketik dengan baik tidak Turing Lengkap.
Ada program mengetik dengan baik non-terminating.

Ini cenderung menunjukkan bahwa:

Tipe sistem yang memiliki interpretasi logis dan konsisten serta berulang secara berulang tidak Turing Lengkap.

Memberikan teorema yang sebenarnya daripada saran memerlukan membuat gagasan tentang sistem tipe dan interpretasi logis yang tepat secara matematis.

Sekarang dua komentar muncul di pikiran:

Ada sistem tipe yang tidak dapat ditentukan , sistem tipe persimpangan yang memiliki interpretasi logis dan dapat mewakili setiap normalisasi -term. Seperti yang Anda katakan, ini tidak persis sama dengan Turing Lengkap, karena jenis fungsi total mungkin perlu diperbarui (disempurnakan, pada kenyataannya) sebelum menerapkannya pada argumen yang diinginkan. Kalkulus adalah kalkulus "gaya kari" dan sama dengan STLC + $\lambda$ dan
$\frac{Γ ⊢ M : τ Γ ⊢ M : σ}{Γ ⊢ M : τ \cap σ}$ $\frac{\Gamma\vdash M:\tau\quad \Gamma\vdash M:\sigma}{\Gamma\vdash M:\tau\cap\sigma}$ Jelas bahwa "interpretasi"mengarah pada interpretasi logis yang konsisten. $\frac{Γ ⊢ M : τ \cap σ}{Γ ⊢ M : τ} \frac{Γ ⊢ M : τ \cap σ}{Γ ⊢ M : σ}$ $\frac{\Gamma\vdash M:\tau\cap\sigma}{\Gamma\vdash M:\tau}\quad \frac{\Gamma\vdash M:\tau\cap\sigma}{\Gamma\vdash M:\sigma}$ $\cap=\wedge$
Ada kelas sistem tipe, Sistem Tipe Murni , di mana pertanyaan seperti itu dapat dibuat tepat. Namun dalam kerangka ini, interpretasi logisnya kurang jelas. Orang mungkin tergoda untuk mengatakan: "PTS konsisten jika memiliki tipe tidak berpenghuni". Tetapi ini tidak berhasil, karena tipe-tipe dapat hidup dalam "alam semesta" yang berbeda, di mana beberapa mungkin konsisten dan beberapa tidak. Coquand dan Herbelin mendefinisikan gagasan Sistem Jenis Murni Logis , di mana pertanyaan itu masuk akal, dan muncul

Setiap LPTS yang tidak konsisten dan tidak tergantung memiliki kombinator perulangan (dan begitu juga Turing Lengkap)

Yang menjawab pertanyaan dalam satu arah (tidak konsisten TC) dalam kasus ini. Sejauh yang saya tahu, pertanyaan untuk LPTS umum masih terbuka dan cukup sulit. $\Rightarrow$

Sunting: Kebalikan dari hasil Coquand-Herbelin tidak semudah yang saya kira! Inilah yang saya kemukakan sejauh ini.

Sebuah Sistem Type Pure logis adalah PTS dengan (setidaknya) macam dan , (setidaknya) aksioma dan (setidaknya) aturan , dengan persyaratan lebih lanjut bahwa tidak ada macam jenis . $\mathrm{Prop}$ $\mathrm{Type}$ $\mathrm{Prop}:\mathrm{Type}$ $(\mathrm{Prop},\mathrm{Prop},\mathrm{Prop})$ $\mathrm{Prop}$

Sekarang saya akan mengambil pernyataan tertentu dari Turing Completeness: perbaiki LPTS dan biarkan menjadi konteksnya $L$ $\Gamma$

Γ = n a t : P r o p, 0 : n a t, S : n a t \to n a t

$\Gamma = \mathrm{nat}:\mathrm{Prop},\ 0:\mathrm{nat},\ S:\mathrm{nat}\rightarrow \mathrm{nat}$

adalahTuring Completeiff untuk setiap fungsi komputabel total ada istilah sehingga dan untuk setiap $L$ $f:\mathbb{N}\rightarrow\mathbb{N}$ $t_f$

Γ ⊢ t_{f} : n a t \to n a t

$\Gamma \vdash t_f : \mathrm{nat}\rightarrow \mathrm{nat}$

n \in N

$n\in\mathbb{N}$

t_{f} (S^{n} 0) \to_{β}^{*} S^{f (n)} 0

$t_f\ (S^n\ 0)\rightarrow^*_{\beta} S^{f(n)}\ 0$

Sekarang argumen diagonalisasi Andrej menunjukkan bahwa ada non-terminating dari tipe . $t$ $\mathrm{nat}$

Sekarang sepertinya kita setengah jalan di sana! Mengingat non terminating jangka , kita ingin mengganti kejadian oleh beberapa jenis generik dan menyingkirkan dan di , dan kami akan memiliki inkonsistensi kami ( dihuni dalam konteks )! $\Gamma \vdash \mathrm{loop}:\mathrm{nat}$ $\mathrm{nat}$ $A$ $0$ $S$ $\Gamma$ $A$ $A:\mathrm{Prop}$

Sayangnya, di sinilah saya buntu, karena mudah untuk mengganti dengan identitas, tetapi jauh lebih sulit untuk dihilangkan. Idealnya kami ingin menggunakan teorema rekursi Kleene, tapi saya belum menemukan jawabannya. $S$ $0$

cody
sumber

OK, jadi dua klarifikasi pertama tentang komentar Anda (1). Apa yang Anda maksudkan ketika Anda mengatakan bahwa sistem tipe persimpangan ini tidak dapat dihitung secara rekursif? Tentu saja set teorema sistem kembali, karena Anda telah memberikannya sebagai kalkulus berurutan langsung. Juga, hasil yang saya lihat terbukti dalam makalah yang Anda tautkan adalah istilah yang dapat diketik dalam sistem adalah istilah yang sangat normal; tetapi bukankah itu berbeda dengan mengatakan bahwa ia dapat mengetik persis fungsi total yang dapat dihitung? Misalnya, bukan

sangat normal, tetapi tidak total?

λ x . x x

$\lambda x. xx$

Morgan Thomas

Sekarang pertanyaan tentang komentar Anda (2). Bagi saya sepertinya teorema yang Anda kutip bukanlah yang kami minati. Dikatakan bahwa untuk setiap LPTS yang tidak bergantung, jika tidak konsisten maka Turing lengkap. Tapi kami ingin tahu apakah untuk setiap LPTS, jika Turing lengkap, maka itu tidak konsisten. Apakah saya salah memahami sesuatu di sini?

Morgan Thomas

@MorganThomas: Ah, Anda benar tentang titik pertama: apa yang saya maksud adalah bahwa sistem tipe tidak bisa decidable , yang, diberikan

, pernyataan

adalah diputuskan. Saya akan memperbaiki ini di pos.

Γ, t, A

$\Gamma, t, A$

Γ ⊢ t : A

$\Gamma\vdash t:A$

cody

Poin kedua: Anda juga benar bahwa seseorang dapat memiliki fungsi non-total yang diketik dengan baik (meskipun orang mungkin tidak perlu menerapkannya pada argumen yang diberikan). Saya akan mengubah jawabannya.

cody

Poin ketiga. Anda benar lagi! Namun kebalikannya (dalam kasus khusus LPTS) agak sepele. Saya akan menguraikan argumen.

cody

Berikut adalah jawaban untuk varian dari precisifikasi @ cody atas pertanyaan saya. Ada LPTS konsisten yang Turing lengkap dalam arti kira-kira @ cody, jika kita mengizinkan pengenalan aksioma tambahan dan aturan pengurangan . Dengan demikian, sistemnya bukanlah LPTS; itu hanya sesuatu yang mirip satu. $\beta$

Pertimbangkan kalkulus konstruksi (atau anggota favorit Anda dari kubus). Ini adalah LPTS, tetapi kami akan menambahkan hal-hal tambahan yang membuatnya bukan LPTS. Pilih simbol konstan , dan tambahkan aksioma: $\lambda$ $\text{nat}, 0, S$

⊢ nat : *

$\vdash \text{nat} : \ast$

⊢ 0 : nat

$\vdash 0 : \text{nat}$

⊢ S : nat \to nat

$\vdash S : \text{nat} \to \text{nat}$

Indeks program mesin Turing dengan bilangan alami, dan untuk setiap bilangan alami , pilih simbol konstan , tambahkan aksioma , dan untuk semua , tambahkan aturan pengurangan $e$ $f_e$ $f_e : \text{nat} \to \text{nat}$ $e,x \in \mathbb{N}$ $\beta$

f_{e} (x) \to_{β} Φ_{e} (x),

$f_e(x) \to_\beta \Phi_e(x),$

$\Phi_e(x)$ $e$ $x$ $\Phi_e(x)$ $\beta$ $\beta$

Sekarang, teori ini jelas Turing lengkap dalam arti kasar @ cody, hanya dengan kekerasan; tetapi klaimnya juga konsisten. Mari kita buat modelnya.

$U_1 \in U_2 \in U_3$

$\emptyset, \mathbb{N}, 0, S \in U_1$ $S$
$a \in b \in U_i$ $a \in U_i$
$A, B \in U_i$ $B^A \in U_i$
$A \in U_i$ $f : A \to U_i$ $\prod_{a \in A} f(a) \in U_i$

$U_i$

$v$ $U_2$ $v$ $I_v$

$I_v(x) = v(x)$ $x$
$I_v(\ast) = U_1, I_v(\Box) = U_2$
$I_v(\text{nat}) = \mathbb{N}, I_v(0) = 0, I_v(S) = S$
$I_v(f_e) = \Phi_e$ $\mathbb{N} \to \mathbb{N}$ $e$
$I_v(AB) = I_v(A)(I_v(B))$ $I_v(A)$ $I_v(B)$ $I_v(AB) = 0$
$I_v(\lambda x : A. B)$ $a \in I_v(A)$ $I_{v[x:=a]}(B)$
$I_v(\Pi x : A. B) = \prod_{a \in I_v(A)} I_{v[x:=a]}(B)$

$A$ $I_v(A) \in U_3$ $v$ $A : B$ $v \models A : B$ $I_v(A) \in I_v(B)$ $\Gamma \models A : B$ $v$ $v \models x : C$ $(x : C) \in \Gamma$ $v \models A : B$

$\Gamma \vdash A : B$ $\Gamma \models A : B$ $x,y$ $y : \ast \models x : y$ $y$ $\emptyset$

$\beta$

Morgan Thomas
sumber

A

$A$

f_{e} (x) \to Φ_{e} (x)

$f_e(x)\rightarrow \Phi_e(x)$ $\iota$

β

$\beta$

β

$\beta$

f_{e} (x)

$f_e(x)$

ι

$\iota$

β

$\beta$

Saya pikir kamu benar. Ini bukan bidang saya, jadi saya agak canggung melakukan sesuatu. :-) Saya pikir bukti Anda bekerja, dan satu konsekuensi yang menarik, jika saya benar, adalah bahwa teori ini tidak memiliki kekuatan konsistensi yang sangat banyak. Sepertinya teori yang berpotensi sangat kuat, karena memiliki jenis dan bilangan alami, yang seharusnya memungkinkan Anda menginterpretasikan teori himpunan; tetapi ternyata Anda tidak bisa, karena Anda dapat membuktikannya konsisten tanpa menggunakan teori himpunan yang kuat!

Morgan Thomas