Exercise 1.36
$P, Q$ の両方が $\beta\text{-nf}$ を持たないもかかわらず、$PQ$ が$\beta\text{-nf}$ を持つような $P, Q$ を見つけよ。
証明
（Intrigila による）
$$\Omega \equiv (\lambda x.xx)(\lambda x.xx)$$
と置く。$P, Q$ を以下のように設定する。
$$\begin{array}{l}
P& \equiv& \lambda y.y(\lambda uvw.w)\Omega\\
Q& \equiv& \lambda z.z\Omega
\end{array}$$
$P, Q$ は共に$\beta\text{-nf}$ではない。
すると、
$$\begin{array}{l}
PQ& \equiv& (\lambda y.y(\lambda uvw.w)\Omega) (\lambda z.z\Omega)\\
& \triangleright_\beta& (\lambda z.z\Omega)(\lambda uvw.w)\Omega\\
& \triangleright_\beta& ((\lambda uvw.w)\Omega)\Omega\\
& \triangleright_\beta& \lambda w.w\
\end{array}$$
$$PQ\ \triangleright_\beta\ \lambda w.w\in\beta\text{-nf}$$
$PQ$ は $\beta\text{-nf}$となる。
from Lambda-Calculus and Combinators: An Introduction
Hindley & Seldin (2008)