不动点组合子

在$\lambda$ 演算或组合子逻辑中, 不动点组合子是满足如下条件的表达式 $Z$:$$n(Zn)=Zn$$在重写系统的视角下, 一般表现为如下的重写关系:$$(Zn)\to n(Zn).$$$\mathbf{Y}$ 组合子是最著名的不动点组合子.

1构造

在 $\lambda$ 演算中

定义 1.1. 在 $\lambda$ 演算中, $\mathbf{Y}$ 组合子为如下表达式: $$\lambda n.(\lambda s.n(ss))(\lambda s.n(ss))$$也可以从映射的视角看待: $$Y(n)::=(\lambda s.n(ss))(\lambda s.n(ss))$$

在组合子逻辑中

定义 1.2. 在部分组合代数 $A$ 中, Y 组合子为如下表达式: $$s(k(sii))(s(s(ks)k)(k(sii)))$$其中 $i=skk$.

2用法

(...)