Lambda演算归约解释

Question

我对接下来的两个lambda表达式的b缩减有一些问题，有人可以给我解释一下如何解决它们：

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

Answer 1

因此，lambda演算很像在编程中使用参数。lambda标记一个函数，名称标记参数的名称以及传递给它的内容。它的其余部分只是代码的输入。

因此，使用您的第一个示例：

(λf.λx.F (f x))

(f x)是输入

λf是函数，可以将f看作参数名

F是它的应用方式。

现在，可以忽略λx。

因此，第一个缩减将是取(f x)，意识到它是f的一个参数，然后将其传递给f函数，以便在第二个f处应用。

(λf .)λx.F (f x))

(f x)传递给f

((f x) .λx.f )

(f x)应用于函数

λx.F x

还有一步要做，但我会让你去做。

此外，当没有括号时，将输入视为两个不同的值。这个家伙在解释它方面真的很有帮助。https://www.youtube.com/watch?v=S_WzF6BHadc，他有一个系列的讲座。