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.
Il découle de ce résultat que toute fonction $\lambda$-calculable est calculable par une machine de Turing.
| Qualité | Numéro | Titre |
|---|
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 :