From: Shin-ichiro HARA <sinara@...>
Date: 2002-05-13T20:02:19+09:00
Subject: [ruby-list:35093] 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)
>   Y = S (K (U I)) U

これはちょっとおかしくないですか？少なくとも (U I) = I I = I 
だから Y = S (K I) U となってしまいますね。

Y を I, K, S で書こうとすると、なんかかなり複雑になりそうなん
ですが、、、難しいですね。


>U = proc{|f| proc{|x| f[f][x]}}
>
>_fact = proc{|f| proc{|x|
>   if( x > 0 )
>     x * f[f][x-1]
>   else
>     1
>   end
>}}
>
>fact = U[_fact]

これには２つ疑問がありまして、一つは、先の U を忠実に書けば U
は遅延なしに U = proc{|f| f[f]} となるのではないかと。実際、

U = proc{|f| f[f]}

_fact = proc{|f| proc{|x|
   if( x > 0 )
     x * f[f][x-1]
   else
     1
   end
}}

fact = U[_fact]

で、十分動くコードです。

もう一つは、_fact の中で f[f] が使われているという所です。
Y の良くできたところは proc の本体の中身の f を f[f] に
自動的に変換してくれるところです。で、その瞬間に遅延評価
云々が必要になるので、あれだけ複雑なコードになるわけです。


しかしやっぱり、遅延評価の所が気になるなあ。簡約では無視さ
れちゃうから。ここは理論化されているのでしょうか。