Ist es möglich, die

Ich weiß, dass es unmöglich ist, die Äquivalenz für einen nicht typisierten Lambda-Kalkül zu bestimmen . Zitat von Barendregt, HP Der Lambda-Kalkül: seine Syntax und Semantik. Nordholland, Amsterdam (1984). :$\beta$

Wenn A und B disjunkt sind, nicht leere Mengen von Lambda-Termen, die unter Gleichheit geschlossen sind, dann sind A und B rekursiv untrennbar. Daraus folgt, dass A nicht rekursiv ist, wenn A eine nichttriviale Menge von unter Gleichheit geschlossenen Lambda-Termen ist. Also können wir das Problem "M = x?" Daraus folgt, dass Lambda keine rekursiven Modelle hat.

Wenn wir ein normalisierendes System wie System F haben, können wir die Äquivalenz "von außen" bestimmen, indem wir die beiden angegebenen Terme reduzieren und vergleichen, ob ihre normalen Formen gleich sind oder nicht. Können wir es jedoch "von innen" tun? Gibt es ein System-F combinator E , so dass für zwei Kombinatoren M und N haben wir E M N = wahr , wenn M und N die gleiche Normalform haben, und E M N = falsch sonst? Oder kann das zumindest für einige Ms gemacht werden ? Um einen Kombinator E M zu konstruieren$\beta$$E$$M$$N$$E M N = \mbox{true}$$M$$N$$E M N = \mbox{false}$$M$$E_M$so dass wahr ist, wenn N ≡ β M ? Wenn nein, warum?$E_M N$$N\equiv_\beta M$

Nein, es ist nicht möglich. Betrachten Sie die folgenden zwei Einwohner des Typs .$(A \to B) \to (A \to B)$

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

Dies sind verschiedene Normalformen, können aber nicht durch einen Lambda-Term unterschieden werden, da N eine η- Expansion von M ist und die η- Expansion die Beobachtungsäquivalenz in einem reinen typisierten Lambda-Kalkül beibehält.$\beta$$N$$\eta$$M$$\eta$

Cody fragte, was passiert, wenn wir ebenfalls durch Äquivalenz modifizieren. Die Antwort ist aufgrund der Parametrizität immer noch negativ. Betrachten Sie die folgenden beiden Terme beim Typ ( ∀ α $\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}$$

Sie haben eine unterschiedliche normale, η- lange Form, sind jedoch beobachtungsmäßig äquivalent. Tatsächlich sind alle Funktionen dieses Typs äquivalent, da ∀ α $\beta$$\eta$ ist die Kodierung des Einheitentyps und damit alle Funktionen des Typs ( ∀ α $\forall \alpha.\;\alpha \to \alpha$ muss extensional äquivalent sein.$(\forall \alpha.\;\alpha \to \alpha) \to (\forall \alpha.\;\alpha \to \alpha)$

Eine weitere mögliche Antwort auf die vollkommen richtige von Neel: Angenommen, es gibt einen Kombinator , der in System F so gut typisiert ist, dass die obige Bedingung zutrifft. Der Typ von E ist:$E$$E$

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

Es stellt sich heraus, dass es einen kostenlosen Satz gibt, der besagt , dass ein solcher Begriff notwendigerweise konstant ist :

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

Insbesondere ist die ständig wahre Funktion oder die ständig falsche Funktion und kann möglicherweise kein "Gleichheitsentscheider" sein.$E$