Calculabilité - Décidabilité (LI347) [0.3cm] Cours no10
10
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
10
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Calculabilité - Décidabilité (LI347)oCours n 10Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚10) 1 / 20Résumé du cours précédentMachine de Turing : une machine de Turing est un modèle decalculateur qui a la même puissance de calcul que les ordinateursactuels et que les autres définitions mathématiques de calculateurs.Une MT consiste en un automate fini, un ruban infini composé decellules et d’une tête de lecture qui est au dessus d’une cellule. Unmouvement de la MT dépend de l’état de l’automate et du symbolecontenu dans la cellule sous la tête de lecture. Lors d’un mouvement,la MT change d’état, écrit dans la cellule sous la tête de lecture etdéplace la tête de lecture vers la gauche ou vers la droiteAcceptation par une MT : une MT est initialisée en mettant le mot enentrée sur le ruban et toutes les autres cellules du ruban contiennent lesymbole blanc. Le mot en entrée est accepté sur la MT rentre dans unétat acceptantS. Graillat (Univ. Paris 6) LI347 (cours n˚10) 2 / 20Résumé du cours précédent (suite)Langages récursivement énumerables : les langages acceptés par uneMT sont appelé les langages récursivement énumerablesConfiguration d’une MT : on peut décrire l’état d’une MT par unechaine de symbole de longueur finie incluant le contenu de toutes lescellules du symbole non blanc le plus à gauche à celui le plus à droite.L’état et la position de la tête de lecture sont donnés en placant l’étatdans ...
Voir
CalculabilitÉ - DÉcidabilitÉ (LI347)
S. Graillat (Univ. Paris 6)
o Cours n 10
Stef Graillat
UniversitÉ Pierre et Marie Curie (Paris 6)
LI347 (cours n˚10)
RÉsumÉ du cours prÉcÉdent
1 / 20
Machine de Turing: une machine de Turing est un modle de calculateur qui a la mme puissance de calcul que les ordinateurs actuels et que les autres dfinitions mathmatiques de calculateurs. Une MT consiste en unautomate fini, unrubaninfini compos de cellules et d’unette de lecturequi est au dessus d’une cellule. Un mouvement de la MT dpend de l’tat de l’automate et du symbole contenu dans la cellule sous la tte de lecture. Lors d’un mouvement, la MT change d’tat, crit dans la cellule sous la tte de lecture et dplace la tte de lecture vers la gauche ou vers la droite
Acceptation par une MT: une MT est initialise en mettant le mot en entre sur le ruban et toutes les autres cellules du ruban contiennent le symbole blanc. Le mot en entre est accept sur la MT rentre dans un tat acceptant
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
2 / 20
RÉsumÉ du cours prÉcÉdent (suite)
Langages rcursivement numerables: les langages accepts par une MT sont appel les langagesrcursivement numerables
Configuration d’une MT: on peut dcrire l’tat d’une MT par une chaine de symbole de longueur finie incluant le contenu de toutes les cellules du symbole non blanc le plus À gauche À celui le plus À droite. L’tat et la position de la tte de lecture sont donns en placant l’tat dans la chaine À gauche de la cellule place sous la tte de lecture
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
Langage reconnu par une machine de Turing
3 / 20
Ècriture du mot donn en entre sur le ruban etM= (Q,Σ,Γ, δ,q0,B,F) DÉfinition 1 Le langage acceptÉ par la MT M notÉ L(M)est dÉfini par
∗ ∗ L(M) ={w∈Σ :q0w`αpβavec p∈F}
DÉfinition 2 L’ensemble des langages acceptÉs par une machine de Turing est appelÉ ensemble deslangages rÉcursivement ÉnumÉrables(RE).
Autre mode d’acceptation: arrt de la machine siδ(q,X)n’est pas dfini.
On peut toujours supposer qu’une machine de Turing s’arrte si elle rentre dans un tat acceptant. S. Graillat (Univ. Paris 6) LI347 (cours n˚10) 4 / 20
Langage reconnu par une machine de Turing (suite)
Mais une machine de Turing peut ne pas s’arrter mme si elle n’accepte pas son entre.
DÉfinition 3 Un langage estrÉcursifs’il est reconnu par une machine de Turing qui s’arrte toujours que le mot soit acceptÉ ou non.
Cela correspond À la notion d’algorithme
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
Techniques de programmation sur les machines de Turing
5 / 20
Mmorisation de donnes dans le controlleurle controlleur est dot d’une capacit de mmorisation finie.
Ruban À plusieurs pistes. L’alphabetΓest alors constitu den-uplets.
Sous-routines : une táche est associe À un sous-ensemble d’tats
Ceci ne change en rien la puissance de calcul des MT
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
6 / 20
Extensions de Multi-ruban
la machine de Turing simple – MT
L’entre est copie sur le premire ruban. Toutes les autres cellules contiennent le symbole blanc. La machine est À l’tat initial. Le controlleur est situ À gauche du premier symbole de l’entre Un changement d’tat : Les dplacements du controlleur sur chacun des rubans sont indpendants les uns des autres. Sur chaque ruban, les changements de symboles sont indpendants les uns des autres.
ThÉorÈme 1 Tout langage acceptÉ par une MT multi-ruban est rÉcursivement ÉnumÉrable.
S. Graillat (Univ. Paris 6)
ComplexitÉ
LI347 (cours n˚10)
7 / 20
Nombre de pas, de transitions, effectues par une MT M lorsque l’entre estw.
SiMne s’arrte pas, ce nombre est infini.
DÉfinition 4 ComplexitÉ en temps : T(n) =le maximum des pas effectuÉs par M pour tous les mots de longueur n.
Le temps pris par une MT À un ruban pour simulernchangements dans 2 une MT Àkrubans estO(n)(pourkfix).
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
8 / 20
Extensions de la machine de Turing simple – MT non-dÉterministe
Dans le cas non-dterministe,δ(q,X)est un ensemble fini de triplets :
{(q1,Y1,D1), . . . ,(qk,Yk,Dk)}
ThÉorÈme 2 Soit MNune MT non-dÉterministe. Alors il existe une MT dÉterministe MD telle que L(MN) =L(MD).
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
Restrictions sur les MT – MT À ruban semi-infinie
9 / 20
Tout langage accept par une Machine de TuringM2est aussi accept par une machine de TuringM1soumise aux restrictions suivantes : Le controlleur deM1est toujours situ À gauche de sa position initiale. M1n’crit jamais le symbole blanc
Pour la preuve considrer plusieurs pistes du ruban, la seconde piste dcrivant ce qui se passe À gauche de la position initiale du controlleur dansM2.
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
10 / 20
Restrictions sur les MT – Machines multi-piles
Exemple de langage non hors-contexte reconnu par une MT Que se passe-t-il si on dote un AP de plusieurs piles ?
Une machine Àkpiles est un AP aveckpiles. Un changement de configuration est induit par : L’tat de l’AP Le symbole d’entre lu Le haut de chaque pile. δ(q,a,X1,X2, . . . ,Xk) = (p, γ1, γ2, . . . , γk) Acceptation par tat final. Marqueur de fin$pour l’entre. ThÉorÈme 3 Si un langage L est acceptÉ par une MT alors il est acceptÉ par un AP À deux piles.
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
Restrictions sur les MT – Machines À compteurs
11 / 20
Mme structure qu’une machine multi-pile mais chaque pile est remplace par un compteur. Les changements dpendent de l’tat courant et de la nullit ou non des compteurs. Ils induisent un changement d’tat et l’ajout ou la soustraction de 1 À chacun des compteurs (mais le rsultat des soustractions ne peut pas tre ngatif). Èvidemment, tout langage accept par une machine À compteur est rcursivement numrable. Si on n’a qu’un seul compteur, le langage accept est rcursivement numrable. ThÉorÈme 4 Tout langage rÉcursivement enumÉrables est acceptÉ par une machine À trois compteurs.
ThÉorÈme 5 Tout langage rÉcursivement enumÉrables est acceptÉ par une machine À deux compteurs. S. Graillat (Univ. Paris 6) LI347 (cours n˚10) 12 / 20
Partie IV : DÉcidabilitÉ – IndÉcidabilitÉ
S. Graillat (Univ. Paris 6)
IndÉcidabilitÉ
LI347 (cours n˚10)
But: Prouver que le langage rcursivement numrableLuconstitu de (M,w)oÙ Mest une MT encode en binaire ∗ west un mot de{0,1} Macceptew. estindcidable
Si ce problme est indcidable sur des entres binaires alors il le sera surement avec un alphabet quelconque
13 / 20
Premire tape: coder une machine de Turing comme un mot constitu de 0 et 1 et exhiber un langage qui n’est pas rcursivement numrable
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
14 / 20
Codage d’une machine de Turing
Ènumration des mots binaires:w1wet 1west vu comme le codage binaire d’un entier ε11 0102 011015 ∗ On peut donc parler dui-ime mot de{0,1}!
Codage d’une machine de Turing:M= (Q,{0,1},Γ, δ,q1,B,F) on suppose que les tats sontq1,q2, . . . ,qravecq1l’tat initial etq2 l’unique tat final on suppose que les symboles du ruban sontX1,X2, . . . ,Xsavec X1=0,X2=1 etX3=B L=D1etR=D2
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
Codage d’une machine de Turing (suite)
15 / 20
i j k l m ) = (q Code des transitions:δ(qi,Xj k,X`,Dm)est cod par 0 10 10 10 10
Code pour une MT: on concatene les codesCipour les transitions en les sparant avec 11C111C211∙ ∙ ∙11Cn−111Cn Exemple:M= ({q1,q2,q3},{0,1},{0,1,B}, δ,q1,B,{q2})avec δ(q1,1) = (q3,0,R,δ(q3,0) = (q1,1,R),δ(q3,1) = (q2,0,R), δ(q3,B) = (q1,1,L) Code pour les transitions : 0100100010100 0001010100100 00010010010100 0001000100010010 Code pourM: 01001000101001100010101001001100010010010100110001000100010010
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
16 / 20
Codage d’une machine de Turing (suite)
Ètant donne une machine de TuringMde codewi, on peut lui associer l’entieriMi=i-ime MT
Beaucoup d’entiers ne correspondent À une MT (par exemple 11001)
Si le codewideMin’est pas valide alors on prend pourMila MT avec un seul tat et pas de transition qui s’arrte immdiatement sur n’importe quelle entre. Par consquentL(Mi) =∅.
Une paire(M,w)constitue d’une MT et d’un mot est encod par :code deM111w
S. Graillat (Univ. Paris 6)
Le langage diagonale
LI347 (cours n˚10)
17 / 20
DÉfinition 5 Lelangage diagonaleLdest l’ensemble des mots witels que wi∈/L(Mi)
Autrement dit,Ldest l’ensemble des motswtels que la MT de codew n’accepte pas le motw
ThÉorÈme 6 Le langage Ldn’est pas un langage rÉcursivement ÉnumÉrable
Preuve :Considrons la matrice avec les MT d’indiceien ligne etjen colonne. La case(i,j)vaut 1 siMiacceptewjet 0 sinon. Les mots deLd correspondent À ceux ayant 0 sur la diagonale. Est-il possible queLd?soit dans une colonne de la matrice
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
18 / 20
Le langage diagonale (suite)
SiLd=L(M)alors il existeitel queM=Mi. Mais alors, siwi∈LdalorsMiacceptewi. Mais par dfinition deLd, on en dduit quewi/∈Ldd’oÙ la contradiction
siwi/∈LdalorsMin’accepte paswiet doncwi∈Ldd’oÙ la contradiction Par consquentMne peut exister etLdn’est pas rcursivement numrable
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
Langages rÉcursifs et classes de langages
DÉfinition 6 Un langage L estrÉcursifsi L=L(M)pour une MT M telle que si w∈(et s’arrte)accepte w L alors M si w/∈n’accepte pas w mais s’arrteL alors M
Une telle machine de Turing correspond À notre notion informelle d’algorithme
19 / 20
Classes de langages: rcursif = dcidable: la MT reconnaisant le langage s’arrete toujours rcursivement numerablemais pas rcursive : la MT reconnaisant le langage s’arrte si elle accepte un mot Exemple:Lu non rcursivement numerable: il n’existe pas de MT reconnaissant ce langage Exemple:L d S. Graillat (Univ. Paris 6) LI347 (cours n˚10) 20 / 20
