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

Stef Graillat

Description

Calculabilité - Décidabilité (LI347)oCours n 11Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚11) 1 / 35Résumé du cours précédentVariante de machines de Turing : MT multi-pistes, MT multi-rubans,MT non déterministe, MT à ruban semi-infini, machines multi-piles,machines à compteurs (à 2 compteurs). Toutes ses machines ont lamême « possibilité » de calcul que la MTLangages recursifs et récursivement énumérables : les langagesacceptés par une machine de Turing (MT) sont dits récursivementénumérables (RE). Un langage RE qui est reconnu par une MT quis’arrête toujours est dit récursif.Le langage L : c’est le langage des mots sur {0,1} tels que,dinterprété comme une MT, ne sont pas dans le langage reconnu parcette MT. C’est un exemple de langage non RE.S. Graillat (Univ. Paris 6) LI347 (cours n˚11) 2 / 35Langages récursifs et classes de langagesDéfinition 1Un langage L est récursif si L = L(M) pour une MT M telle quesi w ∈ L alors M accepte w (et s’arrête)si w ∈/ L alors M n’accepte pas w mais s’arrêteUne telle machine de Turing correspond à notre notion informelled’algorithmeClasses de langages :récursif = décidable : la MT reconnaisant le langage s’arrete toujoursrécursivement énumerable mais pas récursive : la MT reconnaisant lelangage s’arrête si elle accepte un motExemple : Lunon récursivement énumerable : il n’existe pas de MT reconnaissant celangageExemple : LdS. Graillat (Univ. Paris 6) ...

Informations

• Publié par: Baheh
• Nombre de lectures: 41
• Langue: Français

Extrait

.SPav.ni(UatllaiGr

Stef Graillat

Université Pierre et Marie Curie (Paris 6)

74c(uosrir6sL)3I5

Variante de machines de Turing : MT multi-pistes, MT multi-rubans, MT non déterministe, MT à ruban semi-infini, machines multi-piles, machines à compteurs (à 2 compteurs). Toutes ses machines ont la même « possibilité » de calcul que la MT Langages recursifs et récursivement énumérables : les langages acceptés par une machine de Turing (MT) sont dits récursivement énumérables (RE). Un langage RE qui est reconnu par une MT qui s’arrête toujours est dit récursif . Le langage L d : c’est le langage des mots sur { 0 , 1 } tels que, interprété comme une MT, ne sont pas dans le langage reconnu par cette MT. C’est un exemple de langage non RE.

Résumé du cours précédent

S. Graillat (Univ. Paris 6)

LI347 (cours n˚11)

1 / 35

Calculabilité - Décidabilité (LI347) Cours n o 11

n˚11)2/3

Langages récursifs et classes de langages

Définition 1 Un langage L est récursif si L = L ( M ) pour une MT M telle que si w ∈ L alors M accepte w (et s’arrête) si w / ∈ L alors M n’accepte pas w mais s’arrête Une telle machine de Turing correspond à notre notion informelle d’algorithme Classes de langages : récursif = décidable : la MT reconnaisant le langage s’arrete toujours récursivement énumerable mais 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˚11)

Propriétés des langages récursifs

3 / 35

Langages récursifs ⇒ algorithmes Outils pour prouver qu’un langage est RE sans être récursif. Théorème 1 Si L est un langage récursif, alors L est un langage récursif. Preuve : Si L est récursif alors L = L ( M ) pour une MT M qui s’arrete toujours. On tranforme M en une MT M 0 qui accepte quand M n’accepte pas et vice versa. Corollaire 1 Si L est récursivement énumérable et si L n’est pas récursivement énumérable alors L ne peut pas être récursif

S. Graillat (Univ. Paris 6) LI347 (cours n˚11)

4 / 35

lIilibsspoe4quyan’ eLLt eLLtoprutisé s niL rsifrécusont effEn leabéruménntemevisrucér saptsLn’efsetursisrécsiapelamrébanému da re unns tleeut’aucervisr)Luotiosangage(Llequ’unlmiopssbitei,elts émunétneiamelbarréstLe es emivrscu neétvimearlbunémneso,niLcursntré rtserucéevistnem enemnutéramée L bl ’nseptsa érucsrvi spasrécursifsetL eentarlbunémneét nonrifoucurs on ré e d L,tneuqésnocraemivrscureitsost ir6sL)3IU(in.vaPn˚11)6/347(cours tnemmunéruceevis aiGratll abér S. le ssiistausiblmposel2sqeeugasealgn ut2aesedsslascreroéhT(se elI )1emè nonrécursifs(Théromè2e E ) expmelp: iesorentrscuemivétneémunlbar te se

Si w ∈ L alors M 1 accepte et donc s’arrête. Si w ∈ / L alors w ∈ L et donc M 2 accepte et donc s’arrête. Par conséquent L = L ( M ) et M s’arrête toujours. Donc L est récursif. S. Graillat (Univ. Paris 6) LI347 (cours n˚11)

5 / 35

5

Propriétés des langages récursivement énumérables

L et L

Théorème 2 Si L et L sont des langages RE, alors L est un langage récursif. Preuve : soit L = L ( M 1 ) et L = L ( M 2 ) . On appelle M la MT qui simule M 1 et M 2 en parallèle.

M 1 accepte accepte

M 2 accepte rejette

w

Le langage universel On définit le langage universel L u comme l’ensemble des mots binaires ( M , w ) où M est une MT et w un mot accepté par M . L u = { ( M , w ) : w ∈ L ( M ) }

Première étape : montrer l’existence d’une MT reconnaissant L u
MT « universelle ». Il existe une MT U telle que L u = L ( U ) . Construction de U U a trois rubans un pour le code ( M , w ) un qui simule le ruban de M un qui mémorise l’état de M U simule M avec w en entrée U accepte ( M , w ) si et seulement si M accepte w S. Graillat (Univ. Paris 6) LI347 (cours n 11) ˚

Le langage universel

7 / 35

Théorème 3 Le langage L u est récursivement énumérable Preuve : en effet, L u = L ( U ) Théorème 4 Le langage L u n’est pas récursif Preuve : Supposons que L u soit récursif. Alors L u serait aussi récursif. On va montrer que s’il existe une MT M reconnaissant L u alors on peut construire une MT reconnaissant L d . Puisque l’on sait que L d n’est pas RE, on aura donc une contradiction. Supposons donc L u = L ( M )

S.GraillatU(in.vaPirs6)LI347(coursn˚11)8/53

e 2 P,elbadicédnit iP e S bldacidéinst 1 Pevnoedcuitredé P 1 es s: Si alorrsP 2 Troéh isexunte e5èm ilS’ 35

Le langage universel (suite)

)10/

P 2

S. Graillat (Univ. Paris 6) LI347 (cours n˚11)

M w copie w 111 w pour L u M 0 pour L d

Description de M 0 1 étant donné w en entrée, M 0 tranforme l’entrée en w 111 w 2 M 0 simule M avec w 111 w en entrée. Si w est w i dans notre numérotation alors, comme M accepte L u , M 0 accepte w i ssi M i accep n’ te pas w i (c’est à dire w i ∈ L d ) On a donc : M 0 accepte w ssi w ∈ L d

P 1

oui non

Problèmes indécidables sur les MT Techniques de réduction à L d (resp. L u ) pour montrer qu’un problème est non RE (resp. RE mais non récursif). Une réduction d’un problème P 1 vers un problème P 2 est une MT prenant en entrée une instance de P 1 et s’arrêtant avec une instance de P 2 sur le ruban.

oui non

9 / 35

accepte accepte rejette rejette

atllni(UPav.s6ri3IL)c(74sruo11˚n 1 estnon-REalorsPe 2 tson-nER .SrGia

srvimeneétunémarble. S.Graillat(U lloreria leL 2 agnaL e geesn’astpcuré

M 0

accepte

Théorème 7 n es pas . Le langage L ne ’ t récursif Preuve : L’idée est de réduire L u à L ne . Comme on sait que L u n’est pas récursif, on en déduira que L ne n’est pas récursif. Principe : trouver un algorithme qui tranforme une paire ( M , w ) en une MT M 0 telle que L ( M 0 ) 6 = ∅ ssi w ∈ L ( M )

Problèmes indécidables sur les MT

Problèmes indécidables sur les MT

w M accepte x

Définition 2 On définit les deux langages L e = { M | L ( M ) = ∅} L ne = { M | L ( M ) 6 = ∅} Théorème 6 Le langage L ne est récursivement énumérable. Preuve : on définit une MT non-déterministe M reconnaissant L ne . Fonctionnement de M 1 M prend en entrée une MT M i 2 en utilisant l’indéterminisme, M devine un mot w que M i pourrait eventuellement accepter 3 M teste si M i accepte w 4 si M i accepte w alors M accepte son entrée M i On a L ( M ) = L ne S. Graillat (Univ. Paris 6) LI347 (cours n˚11)

11 / 35

iraP.vin743IL)6sn˚rsou(c352/)111 oC

/453

Théorème de Rice et propriétés des langages RE

Une propriété est triviale ssi elle est soit vide soit égale à l’ensemble des RE.

On appelle propriété des langages RE, un ensemble de langages RE. Propriété « hors-contexte » : ensemble des RE qui sont hors-contexte. Propriété « être vide » : ensemble des RE qui sont vides.

13 / 35

Théorème 8 (Théorème de Rice) Toute propriété non triviale des langages RE est indécidable. Exemples : Le langage accepté par une MT est-il vide ? Le langage accepté par une MT est-il fini ? Le langage accepté par une MT est-il régulier ? Le langage accepté par une MT est-il hors-contexte ? S. Graillat (Univ. Paris 6) LI347 (cours n˚11)

Problème de correspondance de Post (PCP) Définition : deux listes A = w 1 , w 2 , . . . , w k et B = x 1 , x 2 , . . . , x k de mots dans Σ ∗ de même longueur. Pour tout i , ( w i , x i ) est appelé couple correspondant. Une instance du PCP a une solution s’il existe une suite d’entiers i 1 , . . . , i m telle que w i 1 w i 2 ∙ ∙ ∙ w i m = x i 1 x i 2 ∙ ∙ ∙ x i m Exemple :

I347(coursn˚11)1 = 32 xw 1 w 13 x1= 1 x 1 x,1,1est2rw 2 w,3ca .vinU(taL)6siraP 10111101 llaiGrS. AListeB i Liste lusoonti 10 0 3 ne 0 U 012 1 1111 i x i w 1111

SG.al(tarlinsruoc(73/61)11˚ar.PivUn34LI6)is

S. Graillat (Univ. Paris 6)

LI347 (cours n˚11)

Partie V : Classe de complexité

5

On peut réduire L u au PCP.

Problème de correspondance de Post (PCP)

On peut aussi réduire le PCP au problème de l’ambiguité des grammaires hors-contexte.

Théorème 9 Le problème de correspondance de Post est indécidable.

15 / 35

Théorème 10 Tester si une grammaire hors-contexte est ambigue est indécidable.

ruoc1˚ns81)153/.PivisarLI6)7(34SG.arlial(tnU

S. Graillat (Univ. Paris 6)

17 / 35

Rappels

LI347 (cours n˚11)

Soit M une MT déterministe qui s’arrête sur toutes ses entrées. Quel est le temps de calcul de M sur w ? → nombre de transitions avant l’arrêt de M sur w Quel est le temps de calcul de M ? f : N → N n 7→ | w m | ax { temps de calcul de M sur w } = n On dira que M fonctionne en f ( n ) .

Le temps (déterministe)

lim f g ( ( n n ) ) < ∞ = ⇒ f = O ( g ) n →∞

Définition 3 Soit f , g : R → R + . On dira que f = O ( g ) s’il existe c , n 0 dans N tels que ∀ n ≥ n 0 , f ( n ) ≤ cg ( n ) .

La classe P

TIME( t ( n ) )={ L | L est décidé par une MT déterministe en temps O ( t ( n )) } La classe de complexité P est définie comme suit : P = [ TIME ( n k ) k ∈ N Remarque : si p et q sont des polynômes, pq , p + q et p ◦ q sont aussi des polynômes. P est robuste : multi-ruban vs un ruban P correspond aux langages décidables en pratique en un temps réaliste. Exemple : Le langage PATH = {h G , s , t i | un chemin de s à t existe dans le graphe orienté G }

S. Graillat (Univ. Paris 6) LI347 (cours n˚11)

Exemple : le langage PATH

19 / 35

Exemple : Le langage PATH = {h G , s , t i | un chemin de s à t existe dans le graphe orienté G } Preuve : Soit la machine M qui, sur l’entrée h G , s , t i : 1 Marque le nœud s 2 Pour chaque arc ( a , b ) marque b si a est marqué 3 Si au moins un nouveau nœud a été marqué en (2), recommence l’étape (2) 4 Si t est marqué, accepte sinon rejette En conclusion : L ( M ) = PATH

.SGraillat(Univ.aPris)6IL437(cours˚n11)20/53

21 / 35

1˚nsruoc(743IL)6

Calcul en temps polynomial

Dans la taille de l’entrée ! a , b ≥ 0 : taille de h a , b i = O ( log a + log b ) (en binaire) On peut calculer a + b , a − b en O ( log a + log b ) On peut calculer ab et a mod b en O (( log a + log b ) 2 ) Attention : un temps de calcul f ( h a i ) = O ( a ) est exponentiel en la taille de l’entrée O ( log a ) .

LI347 (cours n˚11)

S. Graillat (Univ. Paris 6)

O ( m 3 ) ⊂ O ( m 4 ) = O ( n 2 )

PATH ∈ P

Exemple : le langage PATH (suite)

Temps de calcul de M ? On code le graphe sous forme de matrices d’adjacences, n = |h G , s , t i| = O ( m 2 ) Sur une machine M multi-rubans, la stratégie décrite consomme : O ( m 3 ) 1 Etape 1 : O ( 1 ) 2 Etapes 2 et 3 : pas plus de m fois O ( m 2 ) 3 Etape 4 : O ( 1 ) Comme on a

5/3221)G.arSarisiv.Pt(Unilla