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

Stef Graillat

Description

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 ...

Informations

• Publié par: Chyok
• Nombre de lectures: 70
• Langue: Français

Extrait

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,Σ,Γ, δ,q 0 ,B,F) DÉfinition 1 Le langage acceptÉ par la MT M notÉ L(M)est dÉfini par

∗ ∗ L(M) ={w∈Σ :q 0 w`α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: 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 controlleurle 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 :

{(q 1 ,Y 1 ,D 1 ), . . . ,(q k ,Y k ,D k )}

ThÉorÈme 2 Soit M N une MT non-dÉterministe. Alors il existe une MT dÉterministe M D telle que L(M N ) =L(M D ).

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 TuringM 2 est aussi accept par une machine de TuringM 1 soumise aux restrictions suivantes : Le controlleur deM 1 est toujours situ À gauche de sa position initiale. M 1 n’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 dansM 2 .

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,X 1 ,X 2 , . . . ,X k ) = (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rableL u constitu de (M,w)oÙ 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:w1wet 1west vu comme le codage binaire d’un entier ε11 0102 011015 ∗ On peut donc parler dui-ime mot de{0,1}!

Codage d’une machine de Turing:M= (Q,{0,1},Γ, δ,q 1 ,B,F) on suppose que les tats sontq 1 ,q 2 , . . . ,q r avecq 1 l’tat initial etq 2 l’unique tat final on suppose que les symboles du ruban sontX 1 ,X 2 , . . . ,X s avec X 1 =0,X 2 =1 etX 3 =B L=D 1 etR=D 2

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:δ(q i ,X j k ,X ` ,D m )est cod par 0 10 10 10 10

Code pour une MT: on concatene les codesC i pour les transitions en les sparant avec 11C 1 11C 2 11∙ ∙ ∙11C n−1 11C n Exemple:M= ({q 1 ,q 2 ,q 3 },{0,1},{0,1,B}, δ,q 1 ,B,{q 2 })avec δ(q 1 ,1) = (q 3 ,0,R,δ(q 3 ,0) = (q 1 ,1,R),δ(q 3 ,1) = (q 2 ,0,R), δ(q 3 ,B) = (q 1 ,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 codew i , on peut lui associer l’entieriM i =i-ime MT

Beaucoup d’entiers ne correspondent À une MT (par exemple 11001)

Si le codew i deM i n’est pas valide alors on prend pourM i la MT avec un seul tat et pas de transition qui s’arrte immdiatement sur n’importe quelle entre. Par consquentL(M i ) =∅.

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 diagonaleL d est l’ensemble des mots w i tels que w i ∈/L(M i )

Autrement dit,L d est l’ensemble des motswtels que la MT de codew n’accepte pas le motw

ThÉorÈme 6 Le langage L d n’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 siM i acceptew j et 0 sinon. Les mots deL d correspondent À ceux ayant 0 sur la diagonale. Est-il possible queL d ?soit dans une colonne de la matrice

S. Graillat (Univ. Paris 6)

LI347 (cours n˚10)

18 / 20

Le langage diagonale (suite)

SiL d =L(M)alors il existeitel queM=M i . Mais alors, siw i ∈L d alorsM i acceptew i . Mais par dfinition deL d , on en dduit quew i /∈L d d’oÙ la contradiction

siw i /∈L d alorsM i n’accepte pasw i et doncw i ∈L d d’oÙ la contradiction Par consquentMne peut exister etL d n’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:L u 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