规范形式(M B)(M B)

问题描述 投票:0回答:1

是否有λ项M和B,M = / = B,因此M B和(M B)(M B)具有相同的规范形式?

当我还是新的lambda演算时遇到的问题我通过使M =λx.x和B =λy.yΜΒ=(λx.x)(λy.y) - >(β)λy来接近这个问题。

(MB)(MB)=((λx.x)(λy.y))((λx.x)(λy.y)) - >(β)(λy.y)((λx.x)(λy。 y)) - >(β)(λx.x)(λy.y) - >(β)λy.y因此获得相同的规范形式,但我不相信我是正确的(MB)(MB) 。

lambda-calculus
1个回答
0
投票

您发布的减少量是正确的。

有一点需要知道,你可以在lambda术语中使用任何名称作为绑定变量,因此术语\x.x\y.y并没有真正不同;他们是同一个词。这称为alpha等价。

另一件要知道的是,只返回其参数的函数\x.x称为标识函数,并且非常有用。

以下是对M和B不同的问题的答案。 M可以是忽略其参数并返回标识函数的函数:\x.\y.y。 B可以是与M不同的任何术语。然后, (M B) - > \y.y 并且 ((M B) (M B)) - > (\y.y \y.y) - > \y.y

© www.soinside.com 2019 - 2024. All rights reserved.