Fonctions récursives, fonctions lamba-calculables

On montre ici l'équivalence :\r$f$ est $\lambda$-calculable $\Leftrightarrow$ $f$ est récursive.\r\rCe développement est mal sourcé, notamment pour le sens directe. Le sens réciproque est bien traité de le P.Odifreddi mais le sens direct est juste donné en idée et contient de plus une arnaque.\r\rOn fera attention à montrer au passage le théorème de la forme normale pendant la démonstration du sens direct.
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
Rajouter une version