K组合器的不动点

Question

K 组合器为 K := (λxy.x)，定点组合器为 Y := λf.(λx.fxx) (λx.fxx)。我试图计算YK：

YK = (λx.Kxx)(λx.Kxx) = (λx.x)(λx.x) = (λx.x) = I

所以因为YK是K的固定点：

K(YK) = YK
KI = I
KIe = Ie = e

对于任何e。但是 KIe 应该等于 I！

Answer 1

您没有从 Y-combinator 的正确定义开始。它应该是 Y := λf.(λx.f (xx)) (λx.f (xx)) （注意 x x 两边的括号）。
由于 lambda 演算是左结合的，fx x 是等于(fx) x，这显然不起作用。

使用正确的定义，我们得到

Y K := (λf.(λx.f (x x)) (λx.f (x x))) K
       (λx.K (x x)) (λx.K (x x))
       K ((λx.K (x x)) (λx.K (x x)))
       K (Y K)

由于 YK 不会简化为 I，因此不允许进行以下替换。

K (Y K) = Y K
K I = I

所以，KI e 很简单

K I e := (K I) e
         ((λx.λy.x) I) e
         (λy.I) e
         I