3

对于 Y 组合子定理，

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

这是什么F意思？什么是固定点F(x) = x +1？我的理解是x+1=x没有解决办法？

对于下面的证明：

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)意思？

4

2 回答 2

3

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

关于xx：一般来说，lambda 演算f x是一个函数应用程序，xx“x 应用于 x”也是如此，或者x(x). 请注意 x 如何既是正在应用的函数又是传递给它的值。

所以，如果F(x) = x+1, 你有F(xx) = x(x)+1, W = λx.(x(x)+1), 并且X=W(W)将是函数：

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

这可能看起来很抽象，因为如果您尝试将 X 扩展为任何具体值，您会发现该过程永远不会结束。但不要让这困扰你；尽管如此，这X是一个固定点，F因为

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).
于 2014-01-02T01:28:21.870 回答
3

函数的固定点是什么以及 lambda 演算符号似乎有点混乱。

首先λx.F(xx)是一个函数，它接受一个参数 x 并将 x “应用”到 x 和“然后” “应用” F 到结果，所以更像是function (x) { return F(x(x)); }，但不要从字面上理解它，因为在 lambda 演算中它是关于参数的替换和那里不是您需要进行替换的顺序（我用于简化的是应用顺序）。

因此，使用简单的文本重写语义重写为类 C 语法（实际上是 JavaScript，因为它具有第一类函数）的证明如下所示：

var W = function (x) { return F(x(x)); }
var X = W(W);

W(W) => (function (x) { return F(x(x)); }(W))
     => return F(W(W))
     => return F(X)
     => F(X)

现在回到固定点。你给出了一个不存在定点的代数例子......对于函数，它更像是“找到一个固定点ADD1(x) = x + 1”

var F = function (x) { return x + 1; }
var W = function (x) { return F(x(x)); }
      = function (x) { return function (x) { return x + 1; }(x(x)); }
var X = W(W);

W(W) => function (x) { return function (x) { return x + 1; }(x(x)); }(W)
     => return function (x) { return x + 1; }(W(W))
     => return W(W) + 1
     => W(W) + 1
     => X + 1
     => F(X)

我希望熟悉的语法使它不那么混乱而不是更多:)

于 2014-01-02T01:45:32.657 回答