Chapitre 3 / 12
Machine de Turing
Alphabet, mot, langage et calcul
Une machine de Turing utilise un contrôle fini, une tête de lecture et un ruban. À chaque transition elle écrit un symbole, change d’état et déplace sa tête.
💡 À retenir : Une machine peut accepter, refuser ou ne pas s’arrêter. Le modèle étudié ici reconnaît les mots de longueur paire sur {1}.
🤖 Machine de Turing : longueur paire
Simulation de la machine du support : alphabet d’entrée {1}, acceptation des mots de longueur paire, mot vide compris.