对于定点组合器 Y，什么是 \x.f(xx) [英] for fixed point combinator Y, what is \x.f(xx)

问题描述

对于 Y 组合子定理，

For the Y combinator theorem,

 For every function F there exists an X such that FX=X

这里的 F 是什么意思?F(x) = x +1 的不动点是什么?我的理解是 x+1=x 没有解决方案?

what's the F mean here? what's the fixed point for F(x) = x +1? My understanding is that x+1=x does not have a solution?

对于下面的证明:

For any function F, let W be the function λx.F(xx) and let X = WW.
    We claim that X is a fixed point of F. Demonstrated as follows

    X = WW
    X = λx.F(xx) W
    X = F(WW)
    X = FX 

λx.F(xx) 是如何定义的?再次以 F(x) = x + 1 为例，F(xx) 是什么意思?

How's λx.F(xx) defined? again using F(x) = x + 1 as example, what's F(xx) mean?

推荐答案

你是对的，当 x 是一个方程时，x+1 = x 没有解数字.这里发生的事情是 x 不限于是一个数字；它可以是函数的函数.

You are right in that the equation x+1 = x has no solution when x is a number. What's going on here is that x is not restricted to being a number; it can be a function of functions.

关于xx:通常在lambda演算中fx是一个函数应用，所以xx是x应用于x"，或者<代码>x(x).请注意 x 如何既是被应用的函数又是传递给它的值.

About xx: In general in lambda calculus f x is a function application, so xx is "x applied to x", or x(x). Note how x is both the function that is being applied and the value being passed to it.

所以，如果F(x) = x+1，你有F(xx) = x(x)+1，W = λx.(x(x)+1) 和 X=W(W) 就是函数:

So, if F(x) = x+1, you have F(xx) = x(x)+1, W = λx.(x(x)+1), and X=W(W) would be the function:

X = W(W) = (λx.(x(x)+1)) (λy.(y(y)+1))

这可能看起来很抽象，因为如果您尝试将 X 扩展为任何具体值，您会发现该过程永无止境.但不要让它打扰你；尽管 X 是 F 的不动点，因为

This may seem very abstract because if you try to expand X on any concrete value you'll find that the process never ends. But don't let that bother you; in spite of that X is a fixed point of F because

F(X) = F(W(W))             by definition of X = W(W)
     = (λx.F(x(x))) W      using the fact that (λt.f(t))x is f(x)
     = W(W)                by definition of W = λx.F(x(x))
     = X                   by definition of X = W(W).

这篇关于对于定点组合器 Y，什么是 \x.f(xx)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！