是否有λ项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术语中使用任何名称作为绑定变量,因此术语\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