Lambda乘法是如何工作的？

Question

Lambda演算的入门教程

本文介绍了乘法函数

两个数 x 和 y 的乘积可以通过以下函数计算：

(λxyz.x(yz))

那么 2 乘以 2 的积为：

(λxyz.x(yz))22

简化后得到

(λz.2(2z))

读者可以验证，通过进一步简化这个表达式，我们可以得到期望的结果 4。

我不知道如何将 (λz.2(2z)) 简化为 4。有人能给我解释一下吗？

其中 lambda 函数中的 2 是 λsz.s(s(z))，而 4 是 λsz.s(s(s(s(z))))。

- wxw

Answer 1

您可以通过应用替换来正式获得结果，就像您引用的笔记中的之前的例子一样。

因为：

2 ≡ λsz.s(s(z))

首先我们替换(λz.2(2z))中的第二个it（为了避免自由变量被捕获，我们改变变量名称）：

 (λz.2((λxy.x(x(y)))z))

将x替换为z，得到等式：

(λz.2(λy.z(z(y))))

然后我们再次应用定义2（使用新的变量重命名）：

(λz.((λwu.w(w(u)))(λy.z(z(y))))))

将w替换为λy.z(z(y))后，它将变为：

(λz.(λu.(((λy.z(z(y)))((λy.z(z(y)))u)))))

现在我们可以在最右边的lambda中重复替换，用u代替y：

(λz.(λu.((λy.z(z(y)))(z(z(u))))))

最后，我们可以应用最后一个替换，将y替换为z(z(u))：

(λz.(λu.z(z(z(z(u))))))

这是4。

最后要注意的是，通过考虑数字n作为一个具有两个参数的函数，并将第一个参数应用于第二个参数n次，可以使人相信该定义的正确性。因此，(λz.2(2z))是应用两次函数2z的函数，该函数又是应用两次z的函数，因此结果是将其参数应用四次z的函数。

- Renzo