3.3

证明:(λx.xxx)(λx.xxx)(\lambda x.xxx)(\lambda x.xxx) 没有 β\beta-nf。

证明

ω3λx.xxx\omega_3 \equiv \lambda x. xxx,则 Ω3ω3ω3\Omega_3 \equiv \omega_3\omega_3

Ω3ω3ω3βω3ω3ω3β\Omega_3 \equiv \omega_3\omega_3\rightarrow_\beta \omega_3\omega_3\omega_3 \rightarrow_\beta \cdots

即有 Ω3βΩ3\Omega_3 \rightarrow_\beta \Omega_3

该归纳树无分叉且无有穷链,所以 (λx.xxx)(λx.xxx)(\lambda x. xxx)(\lambda x. xxx)β\beta-nf