lambda-calculus - 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-combinatorの正しい定義から始めていません。である必要がありますY := λf.(λx.f (x x)) (λx.f (x x))( の周りの括弧に注意してくださいx x)。ラムダ計算は左結合であるため、f x xは に等しく(f x) x、明らかに機能しません。

正しい定義を使用すると、

YK := (λf.(λx.f (xx)) (λx.f (xx))) K
       (λx.K (xx)) (λx.K (xx))
       K ((λx.K (xx)) (λx.K (xx)))
       K (YK)

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