¿Es posible decidir la equivalencia

Sé que es imposible decidir la equivalencia para el cálculo lambda sin tipo. Citando a Barendregt, HP El cálculo Lambda: su sintaxis y semántica. Holanda Septentrional, Amsterdam (1984). :$\beta$

Si A y B son disjuntos, conjuntos no vacíos de términos lambda que están cerrados en igualdad, entonces A y B son recursivamente inseparables. Se deduce que si A es un conjunto no trivial de términos lambda cerrados en igualdad, entonces A no es recursivo. Entonces, no podemos decidir el problema "M = x?" para cualquier M. en particular. Además, se deduce que Lambda no tiene modelos recursivos.

Si tenemos un sistema de normalización, como el Sistema F, entonces podemos decidir la equivalencia "desde afuera" reduciendo los dos términos dados y comparando si sus formas normales son las mismas o no. Sin embargo, ¿podemos hacerlo "desde adentro"? ¿Existe un combinador E del Sistema-F tal que para dos combinadores M y N tengamos E M N = verdadero si M y N tienen la misma forma normal, y E M N = falso de lo contrario? ¿O puede hacerse esto al menos para algunas M s? Para construir un combinador E $\beta$$E$$M$$N$$E M N = \mbox{true}$$M$$N$$E M N = \mbox{false}$$M$$E_M$tal que es verdadero si N ≡ β M ? Si no, ¿por qué?$E_M N$$N\equiv_\beta M$

No, no es posible. Considere los siguientes dos habitantes del tipo .$(A \to B) \to (A \to B)$

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

Estas son formas anormales distintas, pero no se pueden distinguir por un término lambda, ya que N es una expansión η de M , y la expansión η conserva la equivalencia observacional en un cálculo lambda tipificado puro.$\beta$$N$$\eta$$M$$\eta$

Cody preguntó qué sucede si también modificamos por -equivalencia. La respuesta sigue siendo negativa, debido a la parametricidad. Considere los siguientes dos términos en el tipo ( ∀ α $\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}$$

Son distintas normales, η- forma larga, pero son observacionalmente equivalentes. De hecho, todas las funciones de este tipo son equivalentes, ya que ∀ α $\beta$$\eta$ es la codificación del tipo de unidad, por lo que todas las funciones del tipo ( ∀ α $\forall \alpha.\;\alpha \to \alpha$ debe ser extensionalmente equivalente.$(\forall \alpha.\;\alpha \to \alpha) \to (\forall \alpha.\;\alpha \to \alpha)$

Otra posible respuesta a una perfectamente correcta de Neel: Supongamos que hay es un combinador , así escribió en el sistema de F tal que mantiene la condición anterior. El tipo de E es:$E$$E$

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

Resulta que hay un teorema de forma gratuita que expresa que dicho término es necesariamente constante :

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

$E$