Les machines de Turing

Ce matériel couvre les machines de Turing, un modèle fondamental en informatique théorique. Il s'adresse aux étudiants en informatique, en théorie des langages et en compilation, souhaitant comprendre la définition, le fonctionnement, les applications et les exemples concrets de machines de Turing, ainsi que leur relation avec les fonctions calculables et la décidabilité.

Description d’une machine de Turing

Une machine de Turing (m.t) est constituée d’un ruban infini divisé en cases, d’une tête de lecture/écriture qui se déplace sur ce ruban, et d’une unité de contrôle avec un nombre fini d’états. Le calcul s’effectue par une suite d’étapes. À chaque étape, la machine lit un symbole sur le ruban, peut changer d’état, modifier le symbole lu, puis déplacer la tête à droite, à gauche ou la laisser sur place. Ces étapes sont définies par des transitions.

Formellement, une machine de Turing M est un quadruplet (Q, X, δ, q0) où :

• Q est l’ensemble fini des états de contrôle.
• X est l’alphabet fini des symboles lus et écrits sur le ruban, incluant le symbole blanc #.
• δ est la fonction de transition : δ : Q × X → Q × X × {1, 0, -}, où 1 signifie déplacement à droite, 0 à gauche, et - arrêt.
• q0 est l’état initial de la machine.
• # est le symbole blanc remplissant initialement toutes les cases du ruban non utilisées.
• qF est un état final dans Q.

Une transition (qi, sj, qij, sij, dij) signifie que, dans l’état qi, lisant le symbole sj, la machine passe à l’état qij, écrit le symbole sij sur la case courante, puis déplace la tête selon dij (droite, gauche ou arrêt).

Fonctionnement d’une machine de Turing

À chaque étape, la machine applique la fonction de transition :

δ : Q × X → Q × X × {1, 0, -}

Par exemple, si δ(q1, a) = (q2, b, 1), cela signifie que dans l’état q1, en lisant le symbole a, la machine écrit b, passe à l’état q2 et déplace la tête d’une case vers la droite.

Exemple 1 : Machine M1 d’effacement des symboles non blancs

La machine M1 = ({q0}, {a, #}, δ, q0) avec :

• δ(q0, a) = (q0, #, 1) : remplace 'a' par '#' et avance à droite.
• δ(q0, #) = (q0, #, -) : reste sur place si symbole blanc.

Cette machine efface une suite de 'a' sur le ruban en les remplaçant par des '#'.

Exemple 2 : Machine M2 de déplacement de la tête à gauche jusqu’au blanc ‘#’

La machine M2 = ({q0}, {a, #}, δ, q0) avec :

• δ(q0, a) = (q0, a, 0) : en lisant 'a', reste dans q0 et déplace la tête à gauche.
• δ(q0, #) = (q0, #, -) : arrêt sur symbole blanc.

Exemple de calcul avec déplacement et écriture

Si δ(q1, a) = (q2, b, 1), alors la machine, en état q1 lisant 'a', écrit 'b', passe en q2 et déplace la tête à droite.

Acceptation et rejet d’un mot

• Un mot est accepté si la machine s’arrête dans un état final après avoir entièrement lu le mot.
• Un mot est rejeté si la machine s’arrête dans un état non final ou entre dans une boucle infinie.

Exemple : Machine acceptant a*

La machine accepte toute chaîne composée uniquement de 'a'. Si un autre symbole apparaît, la machine rejette ou boucle.

Boucle infinie

Une machine peut entrer dans une boucle infinie si les transitions la ramènent sans fin à un même état et position, empêchant l’arrêt et l’acceptation.

Utilisation d’une machine de Turing

Une machine de Turing peut être utilisée de deux manières :

• Mode accepteur : On fournit un mot d’entrée. La machine répond "oui" si elle accepte le mot, "non" sinon. Un mot est accepté s’il existe au moins un calcul menant à un état final.
• Mode calculateur : On fournit un mot d’entrée. La machine effectue un calcul jusqu’à atteindre un état final. Le contenu du ruban à l’arrêt est le résultat. Si la machine est déterministe, le résultat est unique.

Exemple de compteur de parité

La machine compte la parité du nombre de '1' dans une chaîne composée de '0' et '1' terminée par un délimiteur '#'. L’état final indique si le nombre de '1' est pair ou impair, en plaçant 0 ou 1 sous la tête de lecture/écriture.

Les instructions sont :

• (q0, 0, q0, 0, 1)
• (q0, 1, q1, 0, 1)
• (q0, #, qF, 0, -)
• (q1, 0, q1, 0, 1)
• (q1, 1, q0, 0, 1)
• (q1, #, qF, 1, -)

Exemple de calcul :

Ruban initial : 1 0 1 1 0 #
Le nombre de 1 est impair → état final qF avec symbole 1 sous la tête.

Si on souhaite remplacer les '1' par des '0' en plus du calcul de parité, on modifie les instructions :

• (q0, 1, q1, 0, 1)
• (q1, 1, q0, 0, 1)

Exemple de vérification de parenthèses

La machine vérifie si une chaîne de parenthèses délimitée par '#' est équilibrée. À l’arrêt, la machine place 0 sous la tête si les parenthèses sont équilibrées, 1 sinon.

Principe :

• Deux états : q0 pour chercher une parenthèse fermante ')' vers la droite, q1 pour chercher une ouvrante '(' vers la gauche.
• Remplacer les parenthèses trouvées par 'x' pour marquer l’effacement.
• Un état q2 vérifie qu’il ne reste plus de parenthèses non appariées en revenant au début.

Alphabet : X = {(, ), x, #}

Instructions :

• (q0, ), q1, x, 0)
• (q0, (, q0, (, 1)
• (q0, #, q2, #, 0)
• (q0, x, q0, x, 1)
• (q1, (, q0, x, 1)
• (q1, #, qF, 1, -)
• (q1, x, q1, x, 0)
• (q2, (, qF, 1, -)
• (q2, #, qF, 0, -)
• (q2, x, q2, x, 0)

Exemple : Machine acceptant {aⁿbⁿ, n ≥ 0}

La machine accepte les mots composés de n 'a' suivis de n 'b'.

Alphabet : X = {a, b, x, #}

Instructions :

• (q0, a, q1, x, 1)
• (q0, #, qF, #, -)
• (q1, a, q1, a, 1)
• (q1, b, q2, x, 0)
• (q1, x, q1, x, 1)
• (q2, x, q2, x, 0)
• (q2, a, q1, x, 1)
• (q2, #, qv, #, 1)
• (qv, x, qv, x, 1)
• (qv, #, qF, #, -)

Le mot "aabb" est accepté, tandis que "aba" est rejeté car la machine ne peut pas lire entièrement le mot.

Exemple : Machine acceptant {aⁿbⁿcⁿ, n ≥ 0}

La machine accepte les mots composés de n 'a', suivis de n 'b', puis de n 'c'.

Alphabet : X = {a, b, c, x, #}

Instructions principales :

• (q0, a, q1, x, 1)
• (q0, #, qF, #, -)
• (q1, a, q1, a, 1)
• (q1, b, q2, x, 1)
• (q2, c, q3, x, 0)
• (q2, x, q2, x, 1)
• (q3, b, q3, b, 0)
• (q3, a, q1, x, 1)
• (q3, #, qv, #, 1)
• (qv, x, qv, x, 1)
• (qv, #, qF, #, -)

Relation avec les calculateurs et fonction T-calculable

Une machine de Turing est un modèle théorique d’ordinateur avec un temps de calcul potentiellement très long et une bonne gestion de l’espace. Elle peut simuler un ordinateur.

Une fonction f(x) est dite T-calculable si une machine de Turing peut calculer ses valeurs à partir d’une représentation standard de l’argument x sur le ruban. Quand la machine s’arrête, la valeur f(x) apparaît sur le ruban. Une représentation standard est souvent en base 1, utilisant le symbole '1'.

Exemple : Fonction ADD(m, n) est T-calculable

La fonction ADD(m, n) = m + n est calculable par une machine de Turing qui, à partir de deux blocs de '1' séparés par un délimiteur B, déplace un des blocs pour les concaténer, obtenant ainsi m + n '1'.

Exemple : Fonction MUL(m, n) = m × n est T-calculable

On utilise une machine à trois rubans :

• Ruban 1 contient m en base 1.
• Ruban 2 contient n en base 1.
• Ruban 3 est vide au départ et contiendra le résultat.

Algorithme :

• Tant que la tête P1 sur le ruban 1 pointe sur '1' :
• Tant que la tête P2 sur le ruban 2 pointe sur '1' :
• Écrire '1' à la position P3 sur le ruban 3.
• Avancer P2 et P3.
• Reculer P2 jusqu’au début.
• Avancer P1.

Thèse de Church

La thèse de Church affirme que :

« Il existe un algorithme qui calcule f(x) » signifie qu’il existe une machine de Turing qui exécute cet algorithme.

Décidabilité

Un problème P est dit décidable s’il existe un algorithme qui, pour chaque entrée x, répond « OUI » ou « NON » à la question « P(x) est-il vrai ? ».

Machine de Turing déterministe et non-déterministe

Une machine de Turing déterministe effectue un seul calcul à la fois, avec une action unique définie pour chaque état et symbole lu.

Une machine de Turing non-déterministe peut choisir entre plusieurs actions à chaque étape. Si l’un des choix mène à l’acceptation, la machine accepte l’entrée. On peut imaginer que la machine se dédouble à chaque choix, explorant toutes les branches en parallèle.

Glossaire des termes clés

• Machine de Turing (m.t) : Modèle abstrait de calcul avec un ruban infini, une tête de lecture/écriture et une unité de contrôle à états finis.
• Ruban : Support infini divisé en cases sur lequel la machine lit et écrit des symboles.
• Tête de lecture/écriture : Dispositif qui lit le symbole courant sur le ruban, écrit un symbole et se déplace.
• État : Configuration interne de la machine, élément de l’ensemble Q.
• Fonction de transition (δ) : Fonction définissant les règles de passage d’un état à un autre, les symboles à écrire et les déplacements.
• Symbole blanc (#) : Symbole remplissant les cases vides du ruban.
• État initial (q0) : État dans lequel la machine commence son calcul.
• État final (qF) : État indiquant la fin du calcul et l’acceptation du mot.
• Calcul : Suite d’étapes appliquant les transitions de la machine.
• Mot accepté : Mot pour lequel la machine s’arrête dans un état final.
• Machine déterministe : Machine avec une transition unique possible pour chaque état et symbole.
• Machine non-déterministe : Machine pouvant choisir entre plusieurs transitions possibles.
• Fonction T-calculable : Fonction calculable par une machine de Turing.
• Décidabilité : Propriété d’un problème d’avoir un algorithme qui répond toujours par oui ou non.

Points clés à retenir

• Une machine de Turing est un modèle abstrait puissant pour étudier le calcul et la décidabilité.
• Elle se compose d’un ruban infini, d’une tête de lecture/écriture et d’un automate à états finis.
• Les transitions définissent les actions : lecture, écriture, changement d’état et déplacement.
• Une machine peut être utilisée comme accepteur (décideur de langage) ou comme calculateur (calcul de fonctions).
• Les exemples concrets illustrent des tâches comme le comptage de parité, la vérification d’équilibre des parenthèses, et la reconnaissance de langages spécifiques.
• La thèse de Church relie les algorithmes aux machines de Turing, affirmant leur équivalence en termes de calculabilité.
• La décidabilité est liée à l’existence d’un algorithme qui répond toujours par oui ou non à une question donnée.
• Les machines déterministes réalisent un seul calcul, tandis que les non-déterministes explorent plusieurs branches de calcul en parallèle.