TEST 6

matricola: ______________________________

nome (solo se non si ricorda la matricola): __________________________________

• Write the lambda-term that represents the following function on natural numbers:
                                      h(x)  =  if (x=0) then 0 else (x + (x-1) + h(x-3)).                    Assume to have available the lambda terms  if, add, sub, iszero, pre and Y.
  

• What is the result of the following substitution?     (( λy.xy)( λz.y( λy .x)))[xyz/x]
  

• Show that if a term has a head-normal form which is not an abstraction, i.e. it is of the form xM₁...M_n...., then all its head-normal forms are not abstractions (i.e. do not begin with λy....).