K组合子的不动点

Question

< p > 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

因为K的不动点是YK：

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

对于任意 e，但是KIe 应该等于 I！

- xuanji

Answer 1

您没有从正确的定义开始翻译Y组合子。应该是Y := λf.(λx.f (x x)) (λx.f (x x))（注意x x周围的括号）。 由于lambda演算符是左结合，因此f x x等于(f x) 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

因此，K I e 简单来说

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

- eriktous