为了证明SKK和II是beta等价的，lambda演算 [英] To prove SKK and II are beta equivalent, lambda calculus

问题描述

我是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.x I = 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演算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！