Lambda calculus, $M$ doesn't have a normal form, $N$ has normal form. Find $M N$ that has a normal form?

Question

I'm trying to understand more about $\lambda$-calculus through exercises so I'm stuck with this one:

Being:

• $M$ a $\lambda$-term without normal form (we can't find a normal form, such as the term $(\lambda x. x x) (\lambda x. x x)$), and

• $N$ a $\lambda$-term with a normal form.

Can we find an expression such as

$$(M N)$$

that has a normal form?

Thanks for the help.

Answer 1

Consider $(\lambda f.f\,A)(K B)$, where $A$ is any $\lambda$-term with no normal form (e.g., $(\lambda x. x x)(\lambda x. x x)$), $K$ is the $K$-combinator ($\lambda x .\lambda y. x$) and $B$ is any normal form $\lambda$-term, (e.g., $\lambda x.x$). Then $(\lambda f.f\,A)$ has no normal form, but if you choose the leftmost $\beta$-redex at each step you have:

$$ (\lambda f.f\,A)(K B) \rightsquigarrow K B A \rightsquigarrow B $$

So $B$ is a normal form for $(\lambda f.f\,A)(K B)$.