Fonctions calculables par une machine de

Turing

def Une machine de Turing calcule une fonction f : Σ^{∗} → Σ^{∗} si, pour tout mot d’entrée w, elle s’arrête toujours dans une configuration ou se trouve f(w) sur le ruban.

Thèse de Turing-Church : Les fonctions calculables par une procédure effective sont les fonctions calculables par une machine de Turing.

Exemple : Écrire une machine de Turing pour additionner deux nombres entiers dans une représentation binaire.