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

18

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}$ $M$ $E_M$ $E_M N$ $N\equiv_\beta M$ ? Jeśli nie to dlaczego?

— Petr Pudlák
źródło

19

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. = λ fa . fa \\ N. = λ fa . λ za . fa za \end{array}

$\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. $\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. & = & λ fa : (\forall α . α \to α) . Λ α . λ x : α . fa [\forall α . α \to α] (Λ β . λ y : β . y) [α] x \\ N. & = & λ fa : (\forall α . α \to α) . Λ α . λ x : α . fa [α] x \end{array}

$\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)$

— Neel Krishnaswami
źródło

2

Ok, to samo pytanie z -equivalence :)

β, η

$\beta,\eta$

— cody

11

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$

mi : \forall α . α \to α \to b o o l

$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., mi T. t u = mi T. t^{'} u^{'}

$\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$

— cody
źródło