Appliquer la notion
Que renvoie la machine de Turing correspondant au diagramme états-transitions ci-dessous lorsqu'on lui donne entrée la valeur 0110 ?
On reste sur l'état de départ tant que la tête de lecture lit VIDE. On passe ensuite à l'état 1, sur lequel on reste tant qu'on lit une donnée. Chaque fois, cette donnée est inversée (lecture de 0 = écriture de 1, et inversement). Enfin, dès que la donnée est terminée, on passe à l'état final.