✦ COGNITIA · Cours interactif

Algorithmes : puissance, limites et performance

Comprendre ce qu’un ordinateur peut résoudre, mesurer l’efficacité des algorithmes et repousser les limites du calcul.

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.