Puede ser útil dar rápidamente el contraejemplo a CR en cálculos mecanografiados con y :ηβη
t = λ x : A . ( λ y: B . y ) x
Y tenemos
t →βλ x : A . X
y
t →ηλ y: B . y
Es inmediato que si , entonces los dos términos resultantes son, de hecho, equivalentes, pero no hay razón para que esto sea así, en términos sin tipo .αA ≡ Bα
En términos escritos , está bastante claro que tiene que ser igual a para que el término resultante esté bien escrito. La gran dificultad que ocurre es esta:B tUNsit
¡Para sistemas con tipos dependientes, la confluencia debe ser probada antes de la preservación del tipo!
Esto se debe a que necesita la propiedad de -inyectividad
para probar la inversión, que se requiere para probar la preservación / reducción del sujeto.Π
Π x : A . si =βηΠ x : A′.si′ ⇔ A =βηUN′∧ B =βηsi′
Por lo tanto, ni siquiera puede probar que las preservan los tipos sin confluencia, ¡pero la confluencia ni siquiera se mantiene en términos sin tipo / sin tipo!βη
Salir de este círculo vicioso requiere algunos trucos técnicos, que son difíciles de resumir aquí, pero podría decirse que el más simple de entender es simplemente dejar de estar interesado en -reducciones, sino concentrarse en -expansions :ηηt →η∗λ x : A . t x
Por supuesto, debe restringir esta regla a términos no y no aplicados para incluso esperar obtener la terminación, pero con estas restricciones parece que el comportamiento de reducción se comporta mucho mejor, y la metateoría funciona sin demasiado muchos problemas. Una buena referencia parece ser Neil Ghani, Eta-Expansiones en la teoría del tipo dependiente .λ
Abel describe un enfoque diferente y recientemente bastante popular, Igualdad algorítmica sin tipo para el marco lógico de Martin-Löf con pares surjectivos .