何时重命名 lambda 演算中的变量？

Question

我明白为什么重命名变量以避免捕获很重要，但在下面的示例中，我不明白为什么它没有发生。

(λf.λx.f(fx))(λf.λx.fx)

显然减少到

λx.(λf.λx.fx)((λf.λx.fx)x)

但 x 不应该在 (λf.λx.f(fx)) 或 (λf.λx.f(fx)) 中重命名吗？他们不是指不同的 x 吗？

Answer 1

Capture avoidance就是避免捕获free变量。 "Capturing" 绑定变量并没有那么大的伤害：在

λx.(λf.λx.fx)((λf.λx.fx)x)

x的两种用法确实是不同的变量，但这已经编码在术语中：一般来说，子术语中的新抽象将"overwrite"绑定更远的最外层抽象。 这仅仅是由于 lambda 项的计算方式：如果对同一个变量有一个新的抽象，那么更远的旧抽象最终将在子项中失去作用新的抽象以及受内部抽象约束的变量实际上将是与仅受外部抽象约束的变量不同的变量。

你可以试试这个：如果你将λx.(λf.λx.fx)((λf.λx.fx)x)应用到某个术语N，那么根据β减少的定义，这个术语将减少到(λf.λx.fx)((λf.λx.fx)x)[N/x]，即通过将 (λf.λx.fx)((λf.λx.fx)x) 中每个自由 (!) 出现的 x 替换为 N 获得的术语（根据定义，替换仅对自由变量起作用）。 x 在那个词中唯一自由出现的是最后一个；两个子项 (λf.λx.fx) 中的另外两个 x 受它们各自的 λx 约束。所以唯一将被 N 替换的 x 是最后一个，因此 (λx.(λf.λx.fx)((λf.λx.fx)x))N 将减少到 (λf.λx.fx)((λf.λx.fx)N) - x 在子项中的界限(λf.λx.fx)保持不变。

所以x的内层抽象和词尾的x确实是属于不同抽象的不同变量。因此，在申请期间不重命名它们是没有问题的。

话虽这么说，但为了便于阅读，有时进行此类重命名很有用。结果项将 alpha-congruent 到直接替换而不重命名的项。

何时重命名 lambda 演算中的变量？

When to rename variables in lambda calculus?

lambda-calculus