q1

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

11

fi

fi

fi

fi

fi

VI.2. Fonctionnement d’une machine

de Turing

a fi

a, 1

Acceptation

fi

fi # ###, -

q1

q2

Le mot aaa est accepté

Configuration 1

# #

a a a # # #

Configuration 4 finale

Arrêt + acceptation du mot aaa

# #

q1

a a a # # #

q1

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

12

fi

fi

fi

fi

fi

VI.2. Fonctionnement d’une machine

de Turing

Boucle infinie

b fi

a fi

b, 0

a, 1

fi

fi

####, -

####, -

q2

q1

b fi

a fi

b, 0

a, 1

fi

fi # ###, -

q2

q1

Configuration 1

# #

a b a # # #

q1

Configuration 2

# #

a b a # # #

q1

Configuration 3

# #

a b a # # #

q1

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

13

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

VI.2. Fonctionnement d’une machine

de Turing

Configuration 1

# #

a b a # # #

Boucle infinie

b fi

a fi

b, 0

a, 1

fi

fi

####, -

####, -

q1

Configuration 2

# #

q1

a b a # # #

q1

q1

q2

Configuration 3

# #

a b a # # #

Configuration 4

et ca reboucle

q1

a b a # # #

# #

q1

A cause de la boucle infinie, l’état final n’est jamais atteint, la

machine ne s’arrête jamais et le mot en entrée n’est pas accepté

14

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

VI.3. Utilisation d’une machine de

Turing

Une machine de Turing est utilisée selon deux modes. Le premier mode est d'utiliser

une machine comme accepteur et le second est d'utiliser une machine comme

un calculateur.

Dans le mode accepteur, on fournit un mot d'entrée à la machine et celle-ci répond

par oui ou par non. Quand la machine répond oui, on dit que le machine accepte le mot.

La machine définit alors l'ensemble des mots qui sont acceptés. Par convention, on dit

que la machine accepte un mot w s'il existe au moins un calcul acceptant avec w comme

que la machine accepte un mot w s'il existe au moins un calcul acceptant avec w comme

entrée, c'est-à-dire qui commence avec la configuration q0w. L'élément important de

cette définition est qu'un seul calcul acceptant suffit pour que la machine accepte

même si d'autres calculs bloquent ou n'atteignent jamais une configuration acceptante.

Dans le mode calculateur, on fournit un mot d'entrée à la machine et celle-ci retourne

un ou plusieurs mots de sortie. Quand la machine ne donne toujours qu'un seul mot de

sortie, elle calcule une fonction qui associe le mot de sortie au mot d'entrée. On met

donc le mot d'entrée sur la bande, la machine effectue un calcul jusqu'à ce qu'elle

atteigne un état final et le contenu de la bande constitue alors un des mots de sortie.

Comme il peut y avoir plusieurs calculs acceptants, il peut y avoir plusieurs mots de

sortie. Dans le cas d'une machine déterministe, il y a au plus un seul calcul acceptant et

donc au plus un seul mot de sortie.

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

15

VI.4. Exemple de compteur de parité

Une procédure de reconnaissance par une machine de Turing peut être

spécifiée par une liste finie d’instructions.

Un calcul particulier est effectué par la liste d’instructions, l’état initial q0, le

contenu du ruban au départ et la position initiale de la tête de lecture/écriture

sur le ruban.

sur le ruban.

Exemple : Un compteur de parité des 1

Le ruban contient une séquence de 1 et 0 qui se termine par un délimiteur

droit #. L’état final est atteint et la case sur la quelle pointe la tête de L/E est 0

ou 1 selon que le nombre de 1 est pair ou impair

Les instructions sont les suivantes :

(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, -)

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

16

VI.4. Exemple de compteur de parité

Illustration d’un calcul:

(q0, 0, q0, 0, 1)

(q0, 1, q1, 1, 1)

(q0, B, q2, 0, -)

(q1, 0, q1, 0, 1)

(q1, 1, q0, 1, 1)

(q1, B, q2, 1, -)

1 0 1 1 0 #

Le nombre de 1 est

impair

1 0 1 1 0 #

1

(q0, 1, q1, 1, 1)

(q0, 1, q1, 1, 1)

(q1, 0, q1, 0, 1)

(q1, 0, q1, 0, 1)

(q1, 1, q0, 1, 1)

(q1, #, qF, 1 , -)

0 fi 0, 1

1 fi

1,1

q0

q0

q1

q1

0 fi 0, 1

1 fi 1, 1

fi 0, -

fi

1, -

qF

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

17

VI.4. Exemple de compteur de parité

Illustration d’un calcul:

(q0, 0, q0, 0, 1)

(q0, 1, q1, 1, 1)

(q0, 1, q1, 1, 1)

(q0, B, q2, 0, -)

(q0, #, qF, 0, -)

(q1, #, q2, 1, -)

(q1, 0, q1, 0, 1)

(q1, 0, q1, 0, 1)

(q1, 1, q0, 1, 1)

(q1, 1, q0, 1, 1)

Le nombre de 1 est

pair

1 0 1 #

1 0 1 #

0

0 fi

0, 1

1 fi 1, 1

(1, 1, 1)

q0

q0

q0

q0

q0

q0

q1

q1

q1

q1

0 fi 0, 1

(0, 0, 1)

1 fi 1, 1

(1, 1, 1)

fi

0, -

fi

1, -

qF

q2

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

18

VI.4. Exemple de compteur de parité

Si, en plus du calcul de la parité, on demande de remplacer les 1 par 0, nous

obtenons les instructions suivantes:

(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, -)

0, 1

0 fi

1 fi

0, 1

q0

q0

q1

q1

0 fi

0, 1

1 0 1 1 0 #

10 0 10 10 0 B1

Le nombre de 1 est

impair

(q0, 1, q1, 0, 1)

(q0, 1, q1, 0, 1)

(q1, 0, q1, 0, 1)

(q1, 0, q1, 0, 1)

(q1, 1, q0, 0, 1)

(q1, #, qF, 1, -)

1 fi 0, 1

fi 0, -

fi

1, -

qF

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

19

Exercice

Exercice : Vérification des parenthèses

On dispose au départ d’une chaine qui contient des parenthèses. La chaine est

délimitée à droite et à gauche par le symbole #. A l’arrêt de la machine, le symbole

sous la tête de lecture/écriture est 0 si les parenthèses sont bien équilibrées et 1 dans

sous la tête de lecture/écriture est 0 si les parenthèses sont bien équilibrées et 1 dans

le cas contraire.

Donner les instructions pour une machine de Turing qui permet de répondre par 0 ou 1

si les parenthèses sont équilibrées ou non.

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

20

VI.5. Exemple de vérification de

parenthèses

Corrigé:

On démarre sur la première parenthèse. Le calcul consiste à aller chercher vers la

droite la première parenthèse fermante,

l’effacer et revenir vers la gauche pour

chercher la première parenthèse ouvrante à partir de là, l’effacer puis recommencer la

recherche (fermante, ouvrante).

recherche (fermante, ouvrante).

Nous avons besoin donc de deux états: un qui sert à se déplacer à droite (q0) pour

chercher une fermante et un qui sert à se déplacer à gauche (q1) pour chercher une

ouvrante.

Enfin, il se peut que l’on ne rencontre plus de parenthèses fermantes, auquel

cas il faut revenir au point de départ de la chaine en vérifiant qu’il n’ y a plus

d’ouvrante non plus. Un état q2 effectue cette vérification en reculant.

Nous utilisons le symbole x pour remplacer les parenthèses rencontrées pour ne pas

les reprendre une deuxième fois.

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

21

Exercice

X = {(, ), x, #}

Les instructions sont les suivantes :

(q0, ), q1, x, 0)

(q0, (, q0, (, 1)

(q0, #, q2, #, 0)

(q0, x, q0, x, 1)

(q0, x, q0, x, 1)

(q1, (, q0, x, 1)

(q1, #, qF, 1, -)

(q1, x, q1, x, 0)

(q1, x, q1, x, 0)

(q2, (, qF, 1, -)

(q2, #, qF, 0, -)

(q2, x, q2, x, 0)

qF est l’état final

qF est l’état final

(fi

x fi

(, 1

x, 1

q0

) fi

(fi

x, 0

x, 1

fi #, 0

q1

x fi

x, 0

fi 1, -

q2

(fi 1, -

fi

0, -

qF

x fi

x, 0

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

22

Exercice

Une machine de Turing qui accepte {anbn, n ‡ 0}

X = {a, b, x, #}

Les instructions sont les suivantes :

(q0, a, q1, x, 1)

(q0, #, qF, #,-)

(q2, x, q2, x, 0)

(q2, a, q1, x, 1)

(q1, a, q1, a, 1)

(q1, b, q2, x, 0)

(q1, x, q1, x, 1)

(q1, x, q1, x, 1)

Le mot aabb est accepté

1 0 1 1 0 #

(qv, x, qv, x, 1)

(qv, #, qF, #, -)

(q2, #, qv, #, 1)

(q2, #, qv, #, 1)

qF

fi #, -

fi #, -

a fi

x, 1

q1

q0

x fi

a fi

x, 1

a, 1

a fi

x, 1

b fi

x, 0

qv

#fi #, 1

q2

x fi

x, 0

xfi

x, 1

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

23

Exercice

Le mot aba n’est pas accepté

a a b b #

x

x

x b #

q0

q1

x a b b #

x

x

x b #

q1

q1

x a b b #

x

x

x

x #

a fi

x, 1

q1

q0

x fi

a fi

x, 1

a, 1

a fi

a fi

x, 1

x, 1

b fi

x, 0

fi #, -

qF

qF

q0

q0

b fi 1, -

b fi 1, -

b fi 1, -

fi #, -

qv

#fi #, 1

q2

x fi

x, 0

q1

q2

x a x b #

x

x

x

x #

xfi

x, 1

q2

q2

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

24

Exercice

Le mot aabb est accepté

x

x

x

x #

x

x

x

x #

q2

qv

x

x

x

x #

x

x

x

x #

q2

qF

qF

qv

x

x

x

x #

x

x

x

x #

fi #, -

fi #, -

a fi

x, 1

q1

q0

x fi

a fi

x, 1

a, 1

a fi

a fi

x, 1

x, 1

b fi

x, 0

qv

#fi #, 1

q2

x fi

x, 0

qv

x

x

x

x #

qv

qF

xfi

x, 1

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

25

Exercice

Le mot aba n’est pas accepté

a b a # #

x

x a # #

q0

qv

x b a # #

x

x a # #

q1

qv

x

x a # #

x

x a # #

qF

qF

fi #, -

fi #, -

q2

qv

x

x a # #

q2

Arrêt de la machine car d (qv, a)

n’est pas définie. Le mot n’est

pas lu donc le mot aba n’est pas

accepté

a fi

x, 1

q1

q0

x fi

a fi

x, 1

a, 1

a fi

a fi

x, 1

x, 1

b fi

x, 0

qv

#fi #, 1

q2

x fi

x, 0

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

26

Exercice

Le mot aabb est accepté

x

x

x

x #

x

x

x

x #

q2

qv

x

x

x

x #

x

x

x

x #

q2

qF

qF

qv

x

x

x

x #

x

x

x

x #

fi #, -

fi #, -

a fi

x, 1

q1

q0

x fi

a fi

x, 1

a, 1

a fi

a fi

x, 1

x, 1

b fi

x, 0

qv

#fi #, 1

q2

x fi

x, 0

qv

x

x

x

x #

qv

qF

xfi

x, 1

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

27

Exercice

Une machine de Turing qui accepte {anbncn, n ‡ 0}

X = {a, b, x, #}

Les instructions sont les suivantes :

(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)

(q1, x, q1, x, 1)

(q2, b, q2, b, 1)

(q3, #, qv, #, 1)

(q3, x, q3, x, 0)

(qv, x, qv, x, 1)

(qv, x, qv, x, 1)

(qv, #, qF, #, -)

fi #, -

qF

fi #, -

xfi

x, 1

a fi

x, 1

q1

q0

a fi

x, 1

x fi

a fi

x, 1

a, 1

b fi

x, 1

qv

#fi #, 1

q3

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

c fi

x, 0

q2

x fi

x, 1

b fi b, 1

c fi

a fi

x fi

x, 0

x, 1

x, 0

28

VI.6. Relation avec les calculateurs

et fonction T-calculable

Une machine de turing est un modèle pour un ordinateur avec un temps de

calcul très grand et un bon espace de calcul. Il est possible de simuler un

ordinateur sur une machine de turing.

Fonction T- calculable

Fonction T- calculable

Une fonction f(x) est dite Turing calculable (T-calculable) si ses valeurs peuvent

être calculées par une machine de turing dont le ruban contient une

représentation standard de l’argument x. Quand la machine (le calculateur)

s’arrête, la valeur de f(x) apparaît dans une représentation sur le ruban. Une

représentation standard possible est une représentation en Base 1 (symbole

utilisé est 1).

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

29

VI.6. Relation avec les calculateurs

Exercice : Montrer que la fonction ADD(m, n) est T-Calculable pour les entiers

n et m.

Corrigé:

La réponse est la suivante:

B

1

1

B

1

1

B

m

B

1

n

1

B

m+n

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

30

VI.6. Relation avec les calculateurs

(1, 1, 1)

(B, B, 1)

(B, B, 1)

(1, 1, 1)

(B, B, 0)

(B, B, 0)

(1, 1, 0)

(1, B, 0)

(B, B, 0)

(B, 1, 0)

(1, 1, 0)

(B, B, -)

On avance jusqu’au 2ème

le

délimiteur droit B,

décaler d’une case vers

décaler d’une case vers

la gauche et ensuite

remplacer

le premier

délimiteur B rencontré

par 1.

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

31

VI.6. Relation avec les calculateurs

Exercice: Montrer que la fonction Mul(m, n) = m x n est T-calculable et donner

l’algorithme de calcul associé

Corrigé:

On utilise une machine de turing à trois rubans

3

B

B

B

m*n

2

1

B

1

1

B

B

1

m

n

1

B

Tant qu’il y a 1 dans le

ruban1, on copie le contenu

du ruban2 dans le ruban3

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

32

VI.6. Relation avec les calculateurs

Nous utilisons P1, P2 et P3 pour désigner les têtes de L/E respectivement sur

les rubans 1, 2 et 3.

Tant que P1 pointe sur 1 faire

Tant que P2 pointe sur 1 faire

écrire à la position P3 un 1

avancer P1

avancer P1

avancer P3

Fin tant que

Reculer P2

tant que P2 pointe sur 1 Faire

Reculer P2

Fin Tant que

Avancer P1

Avancer P2

Fin Tant que

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

33

VI.6. Relation avec les calculateurs

et fonction T-calculable

Une machine de turing est un modèle pour un ordinateur avec un temps de

calcul très grand et un bon espace de calcul. Il est possible de simuler un

ordinateur sur une machine de turing.

Fonction T- calculable

Fonction T- calculable

Une fonction f(x) est dite Turing calculable (T-calculable) si ses valeurs peuvent

être calculées par une machine de turing dont le ruban contient une

représentation standard de l’argument x. Quand la machine (le calculateur)

s’arrête, la valeur de f(x) apparaît dans une représentation sur le ruban. Une

représentation standard possible est une représentation en Base 1 (symbole

utilisé est 1).

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

34

La thèse de Church

Thèse de Church

Lorsqu’on dit:

Il existe un algorithme qui calcul f(x)

Il existe un algorithme qui calcul f(x)

On voudrait dire :

Il existe une machine de Turing qui

execute l’algorithme (qui calcul f(x))

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

35

Décidabilité

Décidabilité

Intuitivement, P est décidable s’il existe un algorithme qui

pour chaque x répond par “OUI” ou par “NON” à la

question :

question :

“Est-ce que P(x) est vrai ?”.

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

36

Machine de Turing déterministe

Une machine de Turing déterministe est le modèle formel d'une machine

telle que nous les connaissons (nos ordinateurs sont des machines déterministes).

Les machines déterministes font toujours un seul calcul à la fois. Ce calcul est constitué

d'étapes élémentaires; à chacune de ces étapes, pour un état donné de la mémoire de

la machine, l'action élémentaire effectuée sera toujours la même.

Une machine de Turing non-déterministe est une variante purement

Une machine de Turing non-déterministe

théorique des machines de Turing où à chaque étape de son calcul, cette machine peut

effectuer un choix non-déterministe: elle a le choix entre plusieurs actions, et elle en

effectue une.

Si l'un des choix l'amène à accepter l'entrée, on considère qu'elle a fait ce choix-là. En

quelque sorte, elle devine toujours juste.

A chaque choix non-déterministe, elle se dédouble, les clones poursuivent le calcul en

parallèle suivant les branches du choix. Si l'un des clones accepte l'entrée, on dit que la

machine accepte l'entrée.

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

37

Machine de Turing déterministe

Un mot w = a1a2…an

S’il existe au moins un calcul :

˛ X* est accepté par une machine non déterministe

a1, b1, d1

a2, b2, d2

an, bn, dn

q0

q1

q2

….. qn-1

qn

q0 a1a2…an|-- a1 q1 a2…an |--…….|-- a1a2…an-1 qn-1 an |-- a1…an qn

Leila Jemni Ben Ayed

Théorie des Langages et Compilation (MT)

38