Développement : Implémentation de la beta-réduction dans une machine de Turing

Détails/Enoncé :

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.

Recasages pour l'année 2024 :

  • Pas de recasages pour cette année.

Versions :

  • Auteur :
  • Remarque :
    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
  • Fichier :

Références utilisées dans les versions de ce développement :