Different notions of normal form were discussed in this chapter, including the full normal form (or simply normal form) and weak head normal form. a) What is the difference between a term having a...

Different notions of normal form were discussed in this chapter, including

the full normal form (or simply normal form) and weak head normal form.

a) What is the difference between a term having a normal form and being

a normal form? Write down some example terms.

b) If a closed term is a weak head normal form, it has to be an abstraction

λx.M. Why?

c) Indicate whether the following λ-terms have a normal form:

– (λx.(λy.yx)z)v

– (λx.xxy)(λx.xxy)

d) Show that the term Ω = (λx.xx)(λx.xx) does not have a normal form.

Find a term different from Ω that is not normalising (i.e., a term such

that every reduction sequence starting from it is infinite).