From: Shin-ichiro HARA <sinara@...>
Date: 2002-05-17T17:16:54+09:00
Subject: [ruby-list:35184] Re: Y Combinator

原です。

 >  I = (λx . x)
 >  K = (λx y . x)
 >  S = (λx y z . x z (y z))
 >
 >の3つのコンビネータを使うだけでチューリングマシンと等価な計算能力

結合法則が成り立たない代数って、馴れないと難しいですね。でもちょっ
と腕を磨いたので、Y に挑戦してみた結果

   U = S I I = λ f . (f f)
   T = S (S (K S) K) (K U)
   Y = S T T

とおくと、Yg = gYg が言えます。（Tg = g(Kg)U) を使う。）

これを Ruby で書くと

   K = proc{|x| proc{|y| x}}
   S = proc{|x| proc{|y| proc{|z| x[z][proc{|t| y[z][t]}]}}}
   I = S[K][K]
   U = S[I][I]
   T = S[S[K[S]][K]][K[U]]
   Y = S[T][T]
   fact = proc{|x| proc{|n| n.zero? ? 1 : n * x[n - 1]}}
   puts Y[fact][5]

ですけど、これはやはりまずくて、うまく動かすには

   S = proc{|x| proc{|y| proc{|z| x[z][y[z]]}}}

とする必要がありました。