TEST
5
matricola: ______________________________
nome (solo se non si ricorda la matricola):
__________________________________
- Fornire la definizione di λ-definibilita'
per funzioni dai naturali ai naturali.
- Dimostrare che il lambda-termine λnfx.f(nfx)
rappresenta la funzione "incremento di 1" sui naturali.
- 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.