Lambda表达减少

Question

我无法使用正常顺序（按名称）和应用顺序（按值）减少来解决以下LAMBDA表达式。我一直对两者都得到不同的答案。这是必须使用两种技术进行减少的λ表达式：

$（\ lambda f \ x \ ldotp f \（f \ x））\（\ lambda f \ x \ ldotp f \（f \ x））\ f \x $

Answer 1

我一直在得到不同的答案。

您应该为两个订单获得相同的结果。请展示您的工作，以便社区可以帮助您找到错误。

我的猜测是你错误地替换了 $ f $ 而不是 $ x $ 到底，当 $ f $ 实际上是免费的。

正确的减少过程如下所示。

---

$（\ lambda f \ x \ ldotp f \（f \ x））\（\ lambda f \ x \ ldotp f \（f \ x））\ f \ x $

第一步的正常顺序与应用顺序之间没有区别。

$（\ lambda f \ x \ ldotp f \（f \ x））\（（\ lambda f \ x \ ldotp f \（f \ x））\ f ）\ x $

---

在此步骤中存在差异，因为应用于 $（（\ lambda f \ x \ ldotp f \（f \ x））\ f）$ 不是β正常形式。让我们忽略它并首先使用正常的顺序。

正常顺序

$（（\ lambda f \ x \ ldotp f \（f \ x））\ f）\（（（\ lambda f \ x \ ldotp f \（f \ x））\ f）\ x）$

$（\ lambda x \ ldotp \ f \（f \ x））\（（（\ lambda f \ x \ ldotp f \（f \ x））\ f ）\ x）$

$ f \（f \（f \（（\ lambda f \ x \ ldotp f \（f \ x））\ f）\ x））$ < / p>

$ f \（f \（f \（f \ x）））$

---

让我们回到第一步。

$（\ lambda f \ x \ ldotp f \（f \ x））\（（\ lambda f \ x \ ldotp f \（f \ x））\ f ）\ x $

---

这次让我们使用申请订单

应用程序顺序

$（\ lambda f \ x \ ldotp f \（f \ x））\（\ lambda x \ ldotp f \（f \ x））\ x $

$（\ lambda x \ ldotp f \（f \ x））\（（\ lambda x \ ldotp f \（f \ x））\ x）$

$（\ lambda x \ ldotp f \（f \ x））\（f \（f \ x））$

$ f \（f \（f \（f \ x）））$

---

具有正常顺序，我们将表达式减少为：

$ f \（f \（f \（f \ x）））$

具有应用程序，我们将表达式减少为：

$ f \（f \（f \（f \ x）））$

结果是相同的。