Apa gunanya konversi di lambda calculus?

Saya pikir saya tidak memahaminya, tetapi konversi ke saya sebagai konversi yang tidak melakukan apa-apa, kasus khusus konversi di mana hasilnya hanya istilah dalam abstraksi lambda karena tidak ada apa-apa untuk melakukan, semacam konversi gunanya.$\eta$$\beta$$\beta$$\beta$

Jadi mungkin -conversion adalah sesuatu yang benar-benar mendalam dan berbeda dari ini, tetapi, jika itu adalah, saya tidak mendapatkan itu, dan saya harap Anda dapat membantu saya dengan itu.$\eta$

(Terima kasih dan maaf, saya tahu ini adalah bagian dasar dari kalkulus lambda)

Pembaruan [2011-09-20]: Saya memperluas paragraf tentang -ekspansi dan ekstensionalitas. Terima kasih kepada Anton Salikhmetov karena menunjukkan referensi yang bagus.$\eta$

$\eta$ -conversion adalah kasus khusus - konversi hanya dalam kasus khusus ketika itu sendiri merupakan abstraksi, misalnya, jika thenTetapi bagaimana jika adalah variabel, atau aplikasi yang tidak direduksi menjadi abstraksi?$(\lambda x . f x) = f$$\beta$f = λ y . y y ( λ x . f x ) = ( λ x . ( λ y . y y ) x ) = β ( λ x . x x ) = α f . $f$$f = \lambda y . y y$

$$(\lambda x . f x) = (\lambda x . (\lambda y . y y) x) =_\beta (\lambda x . x x) =_\alpha f.$$ $f$

Dengan cara -rule adalah seperti jenis khusus dari extensionality, tetapi kita harus sedikit berhati-hati tentang bagaimana yang dinyatakan. Kita dapat menyatakan ekstensionalitas sebagai:$\eta$

1. untuk semua -terms dan , jika maka , atauM N M x = N x M = $\lambda$$M$$N$$M x = N x$$M = N$
2. untuk semua jika ∀ x . f x = g x lalu f = g .$f, g$$\forall x . f x = g x$$f = g$

Yang pertama adalah meta-statement tentang syarat-syarat -calculus. Di dalamnya x muncul sebagai variabel formal, yaitu, itu adalah bagian dari λ- kalkulus. Hal ini dapat dibuktikan dari aturan β η , lihat misalnya Teorema 2.1.29 dalam "Lambda Calculus: Syntax and Semantics" oleh Barendregt (1985). Ini dapat dipahami sebagai pernyataan tentang semua fungsi yang dapat didefinisikan , yaitu, yang merupakan denotasi dari λ -terms.$\lambda$$x$$\lambda$$\beta\eta$$\lambda$

Pernyataan kedua adalah bagaimana ahli matematika biasanya memahami pernyataan matematika. Teori -calculus menggambarkan jenis struktur tertentu, mari kita sebut mereka " λ -models ". Model λ mungkin tidak dapat dihitung, sehingga tidak ada jaminan bahwa setiap elemennya berhubungan dengan λ -term (sama seperti ada bilangan real lebih banyak daripada ekspresi yang menggambarkan real). Ekstensionalitas kemudian mengatakan: jika kita mengambil dua hal f dan g dalam model- λ , jika f x = g x untuk semua x dalam model, maka f = $\lambda$$\lambda$$\lambda$$\lambda$$f$$g$$\lambda$$f x = g x$$x$$f = g$. Sekarang bahkan jika model memenuhi aturan- , itu tidak perlu memenuhi ekstensionalitas dalam pengertian ini. (Referensi diperlukan di sini, dan saya pikir kita perlu berhati-hati bagaimana kesetaraan ditafsirkan.)$\eta$

Ada beberapa cara di mana kita dapat memotivasi konversi - dan η . Saya akan secara acak memilih kategori-theoretik, menyamar sebagai λ -kalkulus, dan orang lain dapat menjelaskan alasan lain.$\beta$$\eta$$\lambda$

Mari kita perhatikan -calculus yang diketik (karena kurang membingungkan, tetapi lebih atau kurang alasan yang sama bekerja untuk λ -calculus yang tidak diketik). Salah satu hukum dasar yang harus memegang adalah hukum eksponensial C A × B ≅ ( C B ) A . (Saya menggunakan notasi A → B dan B A secara bergantian, memilih mana yang terlihat lebih baik.) Apa isomorfisma i : C A × B → ( C B ) A dan j $\lambda$$\lambda$

$$C^{A \times B} \cong (C^B)^A.$$ $A \to B$$B^A$$i : C^{A \times B} \to (C^B)^A$ terlihat seperti, ditulis dalam λ -calculus? Agaknya mereka akan saya = λ f : C A × B . λ a : A . λ b : B . f ⟨ a , b ⟩ dan j = λ g : ( C B ) A . λ p : A × $j : (C^B)^A \to C^{A \times B}$$\lambda$ $$i = \lambda f : C^{A \times B} . \lambda a : A . \lambda b : B . f \langle a, b \rangle$$ Perhitungan pendek dengan beberapa β -reductions (termasuk β -reductions π 1 ⟨ a , b ⟩ = a dan π 2 ⟨ a , b ⟩ = b untuk produk) memberitahu kita bahwa, untuk setiap g : ( C B ) Sebuah kita memiliki i ( j g ) $$j = \lambda g : (C^B)^A . \lambda p : A \times B . g (\pi_1 p) (\pi_2 p).$$ $\beta$$\beta$$\pi_1 \langle a, b \rangle = a$$\pi_2 \langle a, b \rangle = b$$g : (C^B)^A$ Karena i dan j adalah invers satu sama lain, kami berharap i ( j g ) = g , tetapi untuk benar-benar membuktikan ini kita perlu menggunakan η -reduction dua kali: i ( j g ) = ( λ a : A . Λ b : B . g a b ) = η $$i (j g) = \lambda a : A . \lambda b : B . g a b.$$ $i$$j$$i (j g) = g$$\eta$ Jadi ini adalah salah satu alasan untuk memilikipengurangan η . Latihan: η -rule mana yang diperlukan untuk menunjukkan bahwa j ( i f ) = f ? $$i(j g) = (\lambda a : A . \lambda b : B . g a b) =_\eta (\lambda a : A . g a) =_\eta g.$$ $\eta$$\eta$$j (i f) = f$

Untuk menjawab pertanyaan ini, kami dapat memberikan kutipan berikut dari monograf yang sesuai “Lambda Calculus. Sintaks dan Semantiknya “(Barendregt, 1981):

$\beta\eta$$\lambda$$\lambda + \text{ext}$$\text{ext}$$M x = N x \Rightarrow M = N$

$M =_{\beta\eta} N \Leftrightarrow \lambda\eta \vdash M = N \Leftrightarrow \lambda + \text{ext} \vdash M = N$

[Buktinya didasarkan pada teorema berikut.]

$\lambda + \text{ext}$$\lambda\eta$$(\text{ext}) \Rightarrow (\eta)$

$\lambda\eta$

$M$$N$$\lambda\eta \vdash M = N$$\lambda\eta + M = N$

Teori HP-complete [after Hilbert-Post] berhubungan dengan teori konsisten maksimum dalam teori model untuk logika orde pertama.

$\lambda$$\beta$$\eta$

• $\lambda x y.x$$\lambda x y.y$ $\beta\eta$$\beta\eta$

• $\iota$
  

  1. $u\ =_\iota\ v \Rightarrow t\ u\ =_\iota\ t\ v$

  2. $\beta\eta$$t$$u$$t=_\iota u$$t\neq_{\beta\eta}u$

$t$$u$$t=_{\beta\eta\iota}u$

Ini adalah konsekuensi dari teorema Böhm.

$\eta$

$=_{\beta \eta}$$\rightarrow_{\beta\eta}$$M=N$$\lambda x.M = \lambda x.N$$=_{\beta}$

$=_{\beta}$$=_{\beta\eta}$$\lambda x. Mx = M$$Mx=Nx$$M=N$