Les fonctions récursives sont lambda-définissables
On encode les fonctions récursives en lambda-calcul.\rAttention, beaucoup de livres donnent des preuves fausses !
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 912 | Fonctions récursives primitives et non primitives. Exemples.2021 |
| 5 | 929 | Lambda-calcul pur comme modèle de calcul. Exemples.2021 |
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 : Gayral
Références :
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