Les fonctions récursives sont lambda-définissables
On encode les fonctions récursives en lambda-calcul.
Attention, beaucoup de livres donnent des preuves fausses !
| Qualité | Numéro | Titre |
|---|
Utilisateur : Devevey
On prouve uniquement que les fonctions primitives récursives sont lamda-définissables.
Il faut faire attention aux livres, une partie de la preuve de chaque livre est fausse/trop compliquée, et il faut mélanger les deux preuves pour que ça marche. Aussi, il y a pas mal de typos'
Références :
Classical Recursion Theory - Piergiorgio Odifreddi
Logique et fondements de l'informatique - Rougemont, Lassaigne
Utilisateur : sieghttct
'
Références :
Logique et fondements de l'informatique - Rougemont, Lassaigne
The Lambda Calculus. Its Syntax and Semantics - Henk Barendregt
Classical Recursion Theory - Piergiorgio Odifreddi