有没有两个lambda项是外延相等但有不同的范式?

(以下为 = 作为 \equiv_{\beta\eta} )

我认为你想要的是直接应用bhm定理。定理指出:

定理(b hm,1968) 让 f , g 是两个βeta正规形式的闭lambda项,不等于α转换。那么就存在封闭条件 a_1 … a_n 在beta-eta标准形式下 x, y 它认为:

  f a_1 ... a_n x y = x
  g a_1 ... a_n x y = y

一个直接的推论是:

Corollary: 如果 f 和 G 是βeta正规形式的两个闭项,它们不等于α转换,那么它们在外延上是不等价的。

证明: 为了矛盾起见,假设 f G 在NF中是不同的,但是 是 广义上等价的。选择 a_1, ..., a_n 就像BHM定理一样。自从 f , G 假设是广义等价的,那么 f a_1 必须等于 g a_1 。但这是自相矛盾的 f a_1 ... a_n x y = x != y = g a_1 ... a_n x y 任意不平等 x 和 y . 因此,假设必须是错误的,并且 f 和 G 毕竟不能在扩展上等价。

现在:

Corollary: 假设 f , G 是两个具有现有正规形式的闭lambda项 nf 和 ng 分别是。它认为: 核因子 相当于 天然气 当且仅当 f 和 G 在广义上是等价的。

证明: 单向:如果 核因子 相当于 天然气 达到α转换,然后 f 和 G 由于合流而具有广泛的等价性(church-rosser定理)。相反的方向:与前面的推论相反,如果 核因子 和 NG 在外延上是等价的,那么它们必须等于α转换。

所以,你的问题的答案是“不,没有两个词是广泛相等的,但有不同的正常形式”。不过,这对你没有多大帮助,因为正常形式的存在是不可判定的。因此,举例来说,它并不是一下子就可以判定两个任意程序的等价性。