Implémentation de la beta-réduction dans une machine de Turing
On décrit ici le fonctionnement d'une machine de Turing capable d'effectuer un pas de $\beta$-réduction sur un $\lambda$-terme.\r\rIl découle de ce résultat que toute fonction $\lambda$-calculable est calculable par une machine de Turing.
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 913 | Machines de Turing. Applications.2021 |
| 5 | 929 | Lambda-calcul pur comme modèle de calcul. Exemples.2021 |
Utilisateur : Gayral
Ce résultat n'est à ma connaissance pas référencé, mais on peut s'inspirer du fichier suivant et détailler plus en avant le fonctionnement de la machine décrite :
https://www.irif.fr/~carton/Enseignement/Complexite/ENS/Redaction/2009-2010/pablo.rauzy.pdf
Références :