K组合子的不动点

Question

K组合子为K := (λxy.x)，不动点组合子为Y := λf.(λx.f x x) (λx.f x x)。我试着计算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组合子的正确定义开始。它应该是Y := λf.(λx.f (x x)) (λx.f (x x))(注意x x周围的括号)。因为λ演算是左结合的，所以f x x等于(f x) x，这显然是行不通的。

使用正确的定义，我们得到 <>之前yk = λ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 (yk)之前

由于Y K不能约为I，所以不允许进行以下替换。

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

所以K I e就是

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