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 

。但KIe應該等於I！

Answer 1

您沒有從Y-combinator的正確定義開始。它應該是Y := λf.(λx.f (x x)) (λx.f (x x))（注意圍繞x x的括號）。 由於lambda-calculus is left-associative,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) 

因爲y K不減少我，下面的替代是不允許的。

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