本文介绍了为了证明SKK和II是beta等价的,lambda演算的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我是lambda微积分新手,努力证明以下几点。
SKK和II是Beta测试等值。
其中
S = lambda xyz.xz(yz)
K = lambda xy.x
I = lambda xx
我试图通过打开它来降低SKK,但是无处可见,它变得混乱。不要认为SKK可以在不扩展S,K的情况下进一步缩小。
SKK
=(λxyz.xz(yz))KK
→λz.Kz(Kz)(实际上,对于这两个参数,分两步实现)
Kz
=(λxy .x)z
→λy.z
λz.Kz(Kz)
→λz。(λy.z)(λy.z)(again,several steps)
→λz.z
= I
(您应该能够证明 II→I
)
I am new to lambda calculus and struggling to prove the following.
SKK and II are beta equivalent.
where
S = lambda xyz.xz(yz)K = lambda xy.xI = lambda x.x
I tried to beta reduce SKK by opening it up, but got nowhere, it becomes to messy. Dont think SKK can be reduced further without expanding S, K.
解决方案
SKK
= (λxyz.xz(yz))KK
→ λz.Kz(Kz) (in two steps actually, for the two parameters)
Kz
= (λxy.x)z
→ λy.z
λz.Kz(Kz)
→ λz.(λy.z)(λy.z) (again, several steps)
→ λz.z
= I
(You should be able to prove that II → I
)
这篇关于为了证明SKK和II是beta等价的,lambda演算的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!