Calculabilité - Décidabilité (LI347) [0.3cm] Cours no10

De
Publié par

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 ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 64
Nombre de pages : 10
Voir plus Voir moins
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 modle de calculateur qui a la mme puissance de calcul que les ordinateurs actuels et que les autres dfinitions mathmatiques de calculateurs. Une MT consiste en unautomate fini, unrubaninfini compos de cellules et d’unette de lecturequi est au dessus d’une cellule. Un mouvement de la MT dpend de l’tat de l’automate et du symbole contenu 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 et dplace la tte de lecture vers la gauche ou vers la droite
Acceptation par une MT: une MT est initialise en mettant le mot en entre sur le ruban et toutes les autres cellules du ruban contiennent le symbole blanc. Le mot en entre 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 rcursivement numerables: les langages accepts par une MT sont appel les langagesrcursivement numerables
Configuration d’une MT: on peut dcrire 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 tte de lecture sont donns en placant l’tat dans la chaine À gauche de la cellule place sous la tte 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 entre 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 pF}
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: arrt de la machine siδ(q,X)n’est pas dfini.
On peut toujours supposer qu’une machine de Turing s’arrte 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’arrter mme si elle n’accepte pas son entre.
DÉfinition 3 Un langage estrÉcursifs’il est reconnu par une machine de Turing qui s’arrte 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
Mmorisation de donnes dans le controlleurle controlleur est dot d’une capacit de mmorisation finie.
Ruban À plusieurs pistes. L’alphabetΓest alors constitu den-uplets.
Sous-routines : une táche est associe À 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’entre est copie sur le premire 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’entre Un changement d’tat : Les dplacements du controlleur sur chacun des rubans sont indpendants les uns des autres. Sur chaque ruban, les changements de symboles sont indpendants 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, effectues par une MT M lorsque l’entre estw.
SiMne s’arrte 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-dterministe,δ(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 considrer plusieurs pistes du ruban, la seconde piste dcrivant 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’entre lu Le haut de chaque pile. δ(q,a,X1,X2, . . . ,Xk) = (p, γ1, γ2, . . . , γk) Acceptation par tat final. Marqueur de fin$pour l’entre. 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
Mme structure qu’une machine multi-pile mais chaque pile est remplace par un compteur. Les changements dpendent 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 rsultat des soustractions ne peut pas tre ngatif). Èvidemment, tout langage accept par une machine À compteur est rcursivement numrable. Si on n’a qu’un seul compteur, le langage accept est rcursivement numrable. 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 rcursivement numrableLuconstitu de (M,w)Mest une MT encode en binaire west un mot de{0,1} Macceptew. estindcidable
Si ce problme est indcidable sur des entres binaires alors il le sera surement avec un alphabet quelconque
13 / 20
Premire tape: coder une machine de Turing comme un mot constitu de 0 et 1 et exhiber un langage qui n’est pas rcursivement numrable
S. Graillat (Univ. Paris 6)
LI347 (cours n˚10)
14 / 20
Codage d’une machine de Turing
Ènumration des mots binaires:w1wet 1west vu comme le codage binaire d’un entier ε11 0102 011015 On peut donc parler dui-ime 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 sparant avec 11C111C211∙ ∙ ∙11Cn111Cn 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 donne une machine de TuringMde codewi, on peut lui associer l’entieriMi=i-ime 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’arrte immdiatement sur n’importe quelle entre. Par consquentL(Mi) =.
Une paire(M,w)constitue 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 :Considrons 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, siwiLdalorsMiacceptewi. Mais par dfinition deLd, on en dduit quewi/Ldd’oÙ la contradiction
siwi/LdalorsMin’accepte paswiet doncwiLdd’oÙ la contradiction Par consquentMne peut exister etLdn’est pas rcursivement numrable
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’arrte)accepte w L alors M si w/n’accepte pas w mais s’arrteL alors M
Une telle machine de Turing correspond À notre notion informelle d’algorithme
19 / 20
Classes de langages: rcursif = dcidable: la MT reconnaisant le langage s’arrete toujours rcursivement numerablemais pas rcursive : la MT reconnaisant le langage s’arrte si elle accepte un mot Exemple:Lu non rcursivement numerable: il n’existe pas de MT reconnaissant ce langage Exemple:L d S. Graillat (Univ. Paris 6) LI347 (cours n˚10) 20 / 20
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.