Les machines de Turing
Langages réguliers / Automates finis
• Le langage L={anbm/n,m>=0} est reconnu par un automate à état
fini qui est une machine composée d’un ruban d’entrée qui
supporte un mot en entrée et menue d’une tête de lecture
pointant sur ce ruban, on ne peut que lire un symbole et avancer,
a a b b b
a
Tête de lecture b
b
A B
Langages non contextuels/ Automates à Pile
• Exemple L={anbn/n>=0} est reconnu par un automate à pile
dispose d’un ruban de lecture auquel on a ajouté une pile. Il
dispose d’une tête de lecture sur le ruban et d’une tête de lecture
écriture (empiler/dépiler) sur la pile,
a a a b b b
Tête de lecture
a, e/A
q B, A/e
b, A/e
A B
Tête de lecture
Z0
/ecriture
Langages dépendants du contexte
• Exemple L={anbn cn /n>=0} reconnu par les machines de turing
• Une MT est composée d’une bande infinie ou semi-infinie, d’une partie de
contrôle constituée d’un nombre fini d’états possibles, des transitions qui
régissent les calculs de la machine et d’une tête de lecture/écriture. En
fonction de la case courante et de l’état courant elle peut, écrire sur sa case
courante, déplacer sa tête de lecture/écriture à gauche, à droite ou rester
stationnaire et éventuellement changer d’état.
Ruban infini
Tête de
q lecture/écriture
Langages dépendants du contexte
• Exemple L={anbn cn /n>=0} reconnu par les machines de turing
• Initialement la machine est remplie par des dièses, le mot à
analyser va occuper une partie de ce ruban
Ruban infini
# # # # # # # #
Tête de
q lecture/écriture
Définition formelle
• Une machine de turing est un quintuple (Q,X, δ, q0, qf) avec:
• Q: est l’ensemble des états de contrôles
• X ensemble fini de symboles lus et écrits sur la bande contenant #, il contient
l’alphabet d’entrée et l’alphabet de sortie sur la bande
• δ: Q*X->Q*X*{1,0,-1} la fonction de transition de la machine: est un
ensemble fini de transitions de la forme (qi,sj,qij, sij, dij) où qi et qj sont des
états, sj et sij sont des symboles de bande et dij est un élèment de {droite:1,
gauche:0 et Arret:-}. Une transition est aussi notée: qi,sj->qij,sij,dij
• Q0: est l’état initial
• # est le symbole blanc qui, au départ, remplit toutes les positions de la
bande autres que celles contenant la donnée initiale
• Qf est l’état final,
Définition formelle
• qi,sj->qij,sij,dij:
Dans un état qi, lisant un symbole sj, la machine va dans l’état qij, remplace
le symbole lu par sij et effectue un déplacement dij, Les instructions pour
une machine de Turing sont représentées par des quintuples: (qi, sj, qij, sii,
dij)
Sj→sij,dij
qi qj
Exemples
• Exemple1: δ(q1,a)=(q2,b,0) : Lire a, on le remplace par b, se
déplacer à gauche
a→b,0
q1 q2
• Exemple2: δ(q1,a)=(q2,b,1) : Lire a, on le remplace par b, se
déplacer à droite
a→b,1
q1 q2
Acceptation de mots
• Un mot accepté: si la machine s’arrête dans un état final et le mot
est entièrement lu
• Un mot rejeté: si la machine s’arrête dans un état non final ou la
machine entre dans une boucle infinie,
Exemple de machine de Turing
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q0
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q0
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q1
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q2
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q3
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q3
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q3
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q3
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q1
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q1
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q2
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q2
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q2
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q2
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q3
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q1
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q2
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q3
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
q3
• Exemple L={anbn cn /n>=0}, w=aaabbbccc
# # a a a b b b c c c # #
qf
# # a a a b b b c c c # #
Composition de Machines (les Macros)
• On peut combiner des machines simples (de base –sous
programmes) pour obtenir une machine composée
• Machine de base:
• Machine d’écriture de symbole: écriture d’un symbole sans déplacer la
tête et indépendamment du contenu de la bande
• Machine de déplacement de la tête: une machine pour déplacer la tête
de la bande à droite ou à gauche
Machines de base (Abréviation)
• R #: qui trouve le premier blanc à droite
• L #: qui trouve le premier blanc à gauche
• R #: qui trouve le premier non blanc à droite
• L #: qui trouve le premier non blanc à gauche
Exemple
Copie d’un mot (C)
• chercher le premier blanc à gauche,
• T: avancer à droite d’une case
• Si la case contient un symbole σ différent de # alors écrire #
• Chercher le deuxième # à D de la tête écrire σ
• Chercher le deuxième # à G de la tête écrire σ (le remettre)
• Aller à T
• Sinon avancer à droite jusqu’au premier #
# # a b c # a b c # # # #
Copie d’un mot (C)
Décalage à gauche # # w #
Shift Left SL
# W # #
• chercher le premier blanc à gauche,
• T: avancer à droite d’une case
• Si la case contient a différent de # alors reculer à gauche écrire a
• Avance à droite d’une case
• Aller à T
• Sinon avancer à droite jusqu’au premier #
reculer à gauche écrire #
Application
• F(w)=ww
• La machine est copie suivi de décalage à gauche
# W # # #
# W # w #
# W W #
Thèse de Church
• Si il existe un algorithme qui calcule f(x) alors il existe une
machine de Turing qui exécute l’algorithme qui calcule f(x)
Modes d’utilisation d’une machine de Turing
• Mode accepteur: on fournit un mot d’entrée à la machine et celle-ci
répond par oui si le mot appartient à un langage particulier (elle passe à un
état final), ou par non s’il n’appartient pas (passe à un état bloquant), ou ni
par oui ni par non (boucle infinie)
Exemple: La machine de Turing qui accepte L={anbncn/n >= 1}
• Mode calculateur: on fournit un mot d’entrée à la machine et celle-ci
retourne un ou plusieurs mots de sortie, dans ce mode d’utilisation, la tête
de lecture/écriture doit être remise au début du mot résultat
Exemple: La machine de Turing qui fait calcule le successeur d’un nombre
binaire f(x)=x+1
