带有教会数字的 1 的后继者的缩减步骤

Question

我试图了解在正常订单减少后执行以下减少的正确步骤。我不明白执行减少的正确顺序是什么，为什么，在这个表达式中：

(λn.λs.λz.n s (sz)) (λs.λz.s z)

你能帮帮我吗？

注意：这个归约也可以看作是函数后继

(λn.λs.λz.n s (sz))

应用于教会数字 1

(λs.λz.s z)

知道数字零表示为：

(λs.λz.z)

Answer 1

正常的，又名 leftmost-outermost，归约顺序尝试首先归约最左边的最外层子项。

由于您正在寻找最外层的术语，因此您需要确定术语的主要组成部分，记住每个术语都是一个变量，是对术语的抽象或术语的应用：

(λn.λs.λz.n s (s z)) (λs.λz.s z)
---------LHS-------- ----RHS----
----------APPLICATION-----------

主项的left-hand边（LHS）是最左边的最外边，所以是归约的起点。它的最外层抽象是 λn 并且该术语中有一个绑定变量 n ，因此它将被替换为 right-hand 术语：

λn.λs.λz.n s (s z)
--       -

但是，由于LHS和RHS都包含s和z变量，你需要先在其中一个中重命名它们；我选择重命名 RHS 中的那些：

λs.λz.s z -> λa.λb.a b

现在您可以删除 λn 抽象并将 n 变量替换为 λa.λb.a b:

λn.λs.λz.n s (s z) -> λs.λz.(λa.λb.a b) s (s z)
--       -                  -----n-----

是时候寻找下一个减持点了：

λs.λz.(λa.λb.a b) s (s z)

因为 lambda 演算是 left-associative，这等同于：

λs.λz.(((λa.λb.a b) s) (s z))

下一个最左边最外层的可归约项是 (λa.λb.a b) s，它归约为 (λb.s b):

λs.λz.(((λa.λb.a b) s) (s z)) -> λs.λz.((λb.s b) (s z))
         --    -    -                       -

最后一个可归约项是 (λb.s b) (s z)，其中 b 替换为 (s z)：

λs.λz.((λb.s b) (s z)) -> λs.λz.(s (s z))
        --   -  -----              -----

这导致了正常形式的最终状态：

λs.λz.s (s z)

reduction steps for successor of 1 with Church numerals