TEST
4
matricola: ______________________________
nome (solo se non si ricorda la matricola):
__________________________________
- What is the notion that is formally studied by the theory of
beta-conversion?
- Show all the lambda terms that can be obtained from the
following one by means of a single step of beta-reduction
( λx.(x ( (λy.y)x
)))(z(λy.(yz)))
- Prove that the set of lambda terms that can be
beta-reduced in zero or more steps to the term λx.x,
namely {M | M -->> λx.x},
is
not decidable.