An magical fix-point combinator

This is really a magical Y combinator !!!!!
Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L)
where
L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))

Ok, let me give a simple description of Y combinator :
1. 所谓Y-Combinator,就是指一类可以寻找某个函数fix-point的函数…对于fix-point的最直观的认识就是 x = f(x),x 就是f的不动点,that’s enough!
2. 引入Y后,对于任意的F,有 Y F = F (Y F),也就是说Y产生了F的不动点
3. Y-combinator有很多很多种,在不动的lambda形式系统中也有不同的描述形式。
除了本文开头那个让我掉下巴的Y之外,下面在给出几个常见的,使用lambda描述
Y = λf·(λx·f (x x)) (λx·f (x x))
Y’ = (λx. λy. x y x) (λy. λx. y (x y x)) 这一个对应于SK系统中的Y’ = S S K (S (K (S S (S (S S K)))) K) (found by John Tromp)
Θ = (λx. λy. (y (x x y))) (λx. λy. (y (x x y))) (found by Alan Turing)

Then , I give a deduction Y:
Y F = (λx. F (x x)) (λx.F (x x)) = F ( (λx.F (x x)) (λx.F (x x)) = F (Y F)  <= It is actually that simple!!

you can get more informatioin from here.

此条目发表在FP分类目录。将固定链接加入收藏夹。

3 Responses to An magical fix-point combinator

  1. Unknown说道:

    wow gold!All wow gold US Server 24.99$/1000G on sell! Cheap wow gold,wow gold,wow gold,Buy Cheapest/Safe/Fast WoW US EU wow gold Power leveling wow gold from the time you wWorld of Warcraft gold ordered!

    wow power leveling wow power leveling power leveling wow power leveling wow powerleveling wow power levelingcheap wow power leveling wow power leveling buy wow power leveling wow power leveling buy power leveling wow power leveling cheap power leveling wow power leveling wow power leveling wow power leveling wow powerleveling wow power leveling power leveling wow power leveling wow powerleveling wow power leveling buy rolex cheap rolex wow gold wow gold wow gold wow gold -187689745204735

  2. Unknown说道:

    wow gold!All wow gold US Server 24.99$/1000G on sell! Cheap wow gold,wow gold,wow gold,Buy Cheapest/Safe/Fast WoW US EU wow gold Power leveling wow gold from the time you wWorld of Warcraft gold ordered!

    wow power leveling wow power leveling power leveling wow power leveling wow powerleveling wow power levelingcheap wow power leveling wow power leveling buy wow power leveling wow power leveling buy power leveling wow power leveling cheap power leveling wow power leveling wow power leveling wow power leveling wow powerleveling wow power leveling power leveling wow power leveling wow powerleveling wow power leveling buy rolex cheap rolex wow gold wow gold wow gold wow gold -125690688847808

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 登出 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 登出 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 登出 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 登出 /  更改 )

Connecting to %s