Czy można zdecydować równoważność w Systemie F (lub innym typowym rachunku λ)?

Wiem, że nie można zdecydować równoważności dla niepoprawnego rachunku lambda. Cytując Barendregt, HP Rachunek lambda: jego składnia i semantyka. Północna Holandia, Amsterdam (1984). :$\beta$

Jeśli A i B są rozłączne, niepuste zbiory terminów lambda, które są zamknięte na zasadzie równości, to A i B są rekurencyjnie nierozdzielne. Wynika z tego, że jeśli A jest nietrywialnym zbiorem terminów lambda zamkniętych na zasadzie równości, to A nie jest rekurencyjne. Nie możemy więc zdecydować o problemie „M = x?” dla konkretnego M. Wynika z tego, że Lambda nie ma modeli rekurencyjnych.

Jeśli mamy system normalizujący, taki jak System F, wówczas możemy zdecydować równoważność „z zewnątrz”, zmniejszając dwa podane warunki i porównując, czy ich normalne formy są takie same, czy nie. Czy jednak możemy to zrobić „od wewnątrz”? Czy istnieje kombinator System-F taki, że dla dwóch kombinacji i mamy jeśli i mają tę samą normalną postać, a przeciwnym razie? Czy można to zrobić przynajmniej dla niektórych ? Aby zbudować kombinator taki sposób, że jest prawdziwe iff$\beta$$E$$M$$N$$E M N = \mbox{true}$$M$$N$$E M N = \mbox{false}$E M E M N N ≡ β$M$$E_M$$E_M N$$N\equiv_\beta M$? Jeśli nie to dlaczego?

Nie, to niemożliwe. Rozważmy następujących dwóch mieszkańców typu .$(A \to B) \to (A \to B)$

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

Są różne formy -Normal, ale nie można go odróżnić od lambda okresie, gdyż jest -expansion z i -expansion konserwy obserwacyjne równoważności w czystej wpisany lambda rachunku.N η M $\beta$$N$$\eta$$M$$\eta$

Cody zapytał, co się stanie, jeśli zmienimy się przez równoważność. Odpowiedź jest nadal przecząca z powodu parametryczności. Rozważ następujące dwa terminy o typie :( ∀ α $\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}$$

Są różne -normalne, -długie , ale są obserwacyjnie równoważne. W rzeczywistości wszystkie funkcje tego typu są równoważne, ponieważ to kodowanie typu jednostki, a więc wszystkie funkcje tego typu musi być równoważnie rozszerzony.η ∀ α $\beta$$\eta$( ∀ α $\forall \alpha.\;\alpha \to \alpha$$(\forall \alpha.\;\alpha \to \alpha) \to (\forall \alpha.\;\alpha \to \alpha)$

Inna możliwa odpowiedź na całkowicie poprawną odpowiedź Neela: Załóżmy, że istnieje kombinator , dobrze napisany w systemie F, taki, który spełnia powyższy warunek. Typ to:$E$$E$

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

Okazuje się, że istnieje bezpłatne twierdzenie, które wyraża, że ​​taki termin jest koniecznie stały :

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

W szczególności jest funkcją zawsze prawdziwą lub funkcją stale fałszywą i nie może być prawdopodobnie „decydentem o równości”.$E$