我的任务是展示
S(KK)I = K
现在由于S需要三个参数，所以我只是一开始就卡在不知道如何解决这个问题。我看到两个论点，即(KK)和I，但没有第三个我可以“发现”。在这种情况下会发生什么？它已经对我有用了，只需省略S xyz = xz(yz)中的z，这产生了KK(I)并因此产生了K。不过这对我来说似乎是错误的，所以我想在这里问一下。这是正确的方法吗？
例如，我也不明白KI会发生什么，因为K也需要两个参数并且只得到I。我的解决方案是正确的还是我必须采取不同的方式？
问问题
134 次
2 回答
0
解决您的问题的最简单方法是使用 eta-conversion。即，每个项 M 的行为就像一个项 (λx.M x)（当然，x 在 M 中不能是自由的）。因此，如果您要评估的组合器缺少一些参数，您可以对该术语进行 eta 转换，然后应用这些组合器。
鉴于您的示例，您需要两个 eta 转换。下面给出了第一个之后的减少。
S(KK)I -> λx.S(KK)Ix -> λx.KKx(Ix) -> λx.K(Ix)
现在您有了缺少第二个参数的外部组合子 K。如果你对最外层的项进行 eta 转换：λy.(λx.K ( I x )) y，你将得到 λy。K ( I y)，这不是很有趣。但是您可以将 eta 转换应用于该术语的子术语，例如 lambda 抽象体。因此，您可以转换 λx。K ( I x) 到 λx.(λy. K ( I x) y)。这导致λx.λy。I x，归约为 λx.λy.x，此项是K组合子的定义。瞧！
事实上，你可以在不使用 eta 转换的情况下证明组合子的等价性，但是你需要使用一些不太友好的公理作为重写规则（有关详细信息，请参阅 Henk P. Barendregt (1984) 的第 7 章。The Lambda Calculus : 它的语法和语义）。
于 2020-09-14T01:54:28.300 回答
0
我的想法是S(KK)I是一个接受单个参数的函数 - 调用它z。当我们用任意的 调用这个函数时会发生什么z？
S(KK)Iz -> KKz(Iz) -> Kz
所以调用S(KK)I与调用Kz完全相同。因此，S(KK)I和K是同一个函数。z
于 2021-02-18T22:22:55.030 回答