Beta 归约 Lambda 演算

Question

我正在尝试使用减少 beta 来减少以下内容：

(λx.x x) (λx. λy.x x)

我在第一次替换后卡住了，因为它似乎给出了 (λx. λy.x x)(λx. λy.x x)，这会以某种循环结束。我做错了什么？

Answer 1

你没有做错任何事。

表达式 (λx.x x) (λx. λy.x x) beta-reduces 一步到 (λx. λy.x x)(λx. λy.x x)，beta-reduces 到 λy.(λx. λy.x x)(λx. λy.x x) 然后到 λy.λy.(λx. λy.x x)(λx. λy.x x).
在每一步中，每个新表达式都与之前相同，但包含在一个新的抽象中。

在 Lambda 微积分中，归约过程可能不会终止。换句话说，程序可能不会终止（就像在任何图灵完备的编程语言中一样）。

另一个例子是 Ω = (λx.x x)(λx.x x)

Answer 2

这是评估的插图

beta reduction 1
(λ<b>x</b>.<b>x</b> <b>x</b>) (λx.λy.x x)              →β x [x := (λx.λy.x x)]
<del>(λx.</del><b>(λx.λy.x x)</b> <b>(λx.λy.x x)</b><del>)</del>

beta reduction 2
(λ<b>x</b>.λy.<b>x</b> <b>x</b>) (λx.λy.x x)           →β x [x := (λx.λy.x x)]
<del>(λx.</del>λy.<b>(λx.λy.x x)</b> <b>(λx.λy.x x)</b><del>)</del>

result
λy.(λx.λy.x x) (λx.λy.x x)

现在我们达到了弱头范式——也就是说，我们有一个没有任何参数的 lambda λy。

要获得 Head Normal Form，我们可以尝试减少 under lambda ...

reduction 1
λy.(λ<b>x</b>.λy.<b>x</b> <b>x</b>) (λx.λy.x x)       →β x [x := (λx.λy.x x)]
λy.<del>(λx.</del>λy.<b>(λx.λy.x x)</b> <b>(λx.λy.x x)</b><del>)</del>

reduction 2 ...
λy.λy.(λx.λy.x x) (λx.λy.x x)

好的，我们可以立即看到这种模式会重演。每次我们尝试在 lambda 下进行归约时，结果都会被包裹在另一个 λy.

中

所以，这个特定的 lambda 表达式没有 Head Normal Form——也就是说，这个表达式的计算（当应用于一个参数时）永远不会终止；它永远不会达到普通形式。

Beta 归约 Lambda 演算

Beta reduction Lambda calculus

lambda-calculus