Apakah mungkin untuk memutuskan

Saya tahu itu tidak mungkin untuk memutuskan equivalence untuk kalkulus lambda yang tidak diketik. Mengutip Barendregt, HP The Lambda Calculus: Sintaks dan Semantiknya. Holland Utara, Amsterdam (1984). :$\beta$

Jika A dan B terpisah, seperangkat istilah lambda yang ditutup berdasarkan kesetaraan, maka A dan B tidak dapat dipisahkan secara rekursif. Oleh karena itu, jika A adalah seperangkat istilah lambda nontrivial yang ditutup berdasarkan kesetaraan, maka A tidak bersifat rekursif. Jadi, kita tidak bisa memutuskan masalah "M = x?" untuk M. tertentu juga, maka Lambda tidak memiliki model rekursif.

Jika kita memiliki sistem normalisasi, seperti Sistem F, maka kita dapat memutuskan equivalence "from outside" dengan mengurangi dua istilah yang diberikan dan membandingkan apakah bentuk normalnya sama atau tidak. Namun, bisakah kita melakukannya "dari dalam"? Apakah ada Combinator Sistem-F E sehingga untuk dua combinator M dan N kita memiliki E M N = true jika M dan N memiliki bentuk normal yang sama, dan E M N = false jika tidak? Atau bisakah ini dilakukan setidaknya untuk beberapa M ? Untuk membuat combinator E $\beta$$E$$M$$N$$E M N = \mbox{true}$$M$$N$$E M N = \mbox{false}$$M$$E_M$ sehingga adalah true iff $E_M N$ ? Jika tidak, mengapa?$N\equiv_\beta M$

Tidak, itu tidak mungkin. Pertimbangkan dua penghuni tipe berikut $(A \to B) \to (A \to B)$ .

$$\begin{array}{l} M = \lambda f.\;f \\ N = \lambda f.\;\lambda a.\; f\;a \end{array}$$

Ini adalah bentuk -normal yang berbeda, tetapi tidak dapat dibedakan dengan istilah lambda, karena N adalah ekspansi- η dari M , dan $\beta$$N$$\eta$$M$$\eta$ ekspansi- mempertahankan ekuivalensi pengamatan dalam kalkulus lambda yang diketik murni.

Cody bertanya apa yang terjadi jika kita keluar dengan equivalence, juga. Jawabannya masih negatif, karena parametrik. Pertimbangkan dua istilah berikut pada tipe ( ∀ α $\eta$ :$(\forall \alpha.\;\alpha \to \alpha) \to (\forall \alpha.\;\alpha \to \alpha)$

$$\begin{array}{lcl} M & = & \lambda f:(\forall \alpha.\;\alpha \to \alpha).\;\Lambda \alpha.\lambda x:\alpha.\;f \;[\forall \alpha.\;\alpha \to \alpha]\;(\Lambda \beta.\lambda y:\beta.\;y)\;[\alpha]\;x\\ N & = & \lambda f:(\forall \alpha.\;\alpha \to \alpha).\;\Lambda \alpha.\lambda x:\alpha.\;f\;[\alpha]\;x \end{array}$$

Mereka berbeda -normal, bentuk η- panjang, tetapi secara observasi setara. Faktanya, semua fungsi dari tipe ini adalah sama, karena ∀ α $\beta$$\eta$ adalah pengkodean dari tipe unit, dan semua fungsi dari tipe ( ∀ α $\forall \alpha.\;\alpha \to \alpha$ harus setara secara ekstensi.$(\forall \alpha.\;\alpha \to \alpha) \to (\forall \alpha.\;\alpha \to \alpha)$

Jawaban lain mungkin untuk satu sempurna benar Neel: Misalkan ada adalah sebuah combinator , baik diketik dalam sistem F sehingga kondisi di atas berlaku. Jenis E adalah:$E$$E$

$$E : \forall \alpha.\alpha\rightarrow \alpha\rightarrow {\bf bool}$$

Ternyata ada teorema gratis yang menyatakan bahwa istilah seperti itu harus konstan :

$$\forall T,\ t,u,t',u':T,\ E\ T\ t\ u = E\ T\ t'\ u'$$

$E$