Lambda微积分(λa.b)((λx.xx)(λx.xx))

Question

我正在寻找一个弱正规化lambda项的例子.我是否正确地说以下内容:

(?a.b)((?x.xx)(?x.xx))

减少到:

b

要么:

没有终止(如果你试图减少(?x.xx)(?x.xx))

我不确定第一次减少是否正确所以只需要一些澄清,谢谢.

Answer 1

如果你首先评估正确的术语,那么它将永远不会达到正常形式,因此它不具有强烈的正常化.如果您首先评估左项,它将立即达到正常形式,因此它是可标准化的并且表明该术语是弱标准化的.它也是无类型lambda演算的非汇合的一个例子.

请注意,您更有可能想要谈论重写系统如何正常化而不是特定术语.因此,该术语是无类型lambda演算的强归一化性质的反例,但没有提供ULC弱归一化(并且不是)的正面证据.