La lecture en ligne est gratuite
Télécharger
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