[PDF] Examen Final Corrigé rédigé par Paul Brunet et Laure Gonnord 1

View - Download Examen Final Corrigé rédigé par Paul Brunet et Laure Gonnord 1

Previous PDF

Next PDF

Master Info - 2014-2015

MIF15 Complexite et Calculabilite

Examen Final

Corrige redige par Paul Brunet et Laure Gonnord

Duree 1H30

Notes de cours et de TD autorisees. Livres et appareils electroniques interdits.

Le bareme est donne a titreindicatif.

1 Machines de Turing

SoitM= (K;;;;q0;F) la machine de Turing d'etat initialq0, avec acceptation par etat nal (unique etat acceptantq6), d'alphabet =fa;bg, d'alphabet de ruban =fa;b;X;Y;#g, avec la fonction de transitionschematisee par le dessin ci-dessous :q

0#=#Dq

1a=XDY=Y D

q 2a=aD

Y=Y Db=Y D

q

3b=Y Gq

4a=aG

Y=Y GX=XDq

5Y=Y D

#=#Sq

6Question 1(1 point)

Le mota2b4est-il accepte parM? Donner les congurations successives.Solution: Partant de la conguration initiale (#aabbbb#;q0), on obtient sans aucun probleme que ce mot est reconnu.

Question 2(1 point)

Sans donner les congurations successives, dire si les motsa2b3eta2b5sont acceptes par

M.Solution:

Aucun de ces deux mots n'est accepte, le premier mot bloque la machine enq3, le deuxieme dans l'etatq1.MIF15 Complexite et Calculabilite, Master Info - 2014-2015 1/8

Question 3(2 points)

Quel langage est reconnu par cette machine de Turing?On justiera proprement par double inclusion.Solution: Le langage estL=fanb2njn1g. Il est clair qu'un mot deLest accepte par la machine de Turing (exhiber une derivation qui realisenfois le cycle (q1;q2;q3;q4;q1)). Dans l'autre sens, un chemin acceptant de la machine de Turing a forcement prisn >1 fois le cycle (q1;q2;q3;q4;q1), et ce cycle a pour eet de remplacer unaparXet deuxbpar un seul Y. Il est assez clair ensuite que les mots reconnus sont uniquement de la formeaibj. Par construction, la partie de droite (la n de l'execution) deMn'est prise que lorsqu'il ne reste plus deaa lire dans le mot, et cette partie est bloquante s'il reste desb. Ceci montre l'inclusion inverse.

Question 4(2 points)

Modier cette machine pour reconna^tre le langagefan+1b2njn1g.Justier.Solution: Il sut d'ajouter un etatq7, entreq0etq1, qui remplace le premierapar unXavant d'executer la machine M sur le reste du mot.q

0#=#Dq

7a=XDq

1a=XDY=Y D

q 2a=aD

Y=Y Db=Y D

q

3b=Y Gq

4a=aG

Y=Y GX=XDq

5Y=Y D

#=#Sq

62 Fonctions primitives recursives et-recursives

Question 5(1 point)

Sous quelle(s) condition(s) (susante(s)) une fonction denie par cas est-elle primitive recursive?On donnera un enonce precis, qu'on ne demande pas de prouver, et que l'on considerera comme vrai pour la suite.Solution: Soitf:Np!Netg:Np!Ndeux fonctions primitives recursives et:Np! f0;1gun predicat primitif recursif, alorsh:Np!Ndenie par : h(x1;:::;xp) =( f(x1;:::;xp) si(x1;:::xp) = 1 g(x1;:::;xp) sinon est primitive recursive.MIF15 Complexite et Calculabilite, Master Info - 2014-2015 2/8

Question 6(1 point)

Montrer que la fonctionmaxn:Nn!Nqui a (x1;:::xn) associe le maximum desnentiers x

1;:::xnest primitive recursive.On peut considerer acquis que le predicatest primitif

recursif. On attend une redaction avec des arguments precis, mais sans forcement detailler l'utilisation des operateursComp;Rec;id, ...Solution: On montre par recurrence surn2 que le maxn-aire est primitif recursif :

P ourn= 2,max2(x1;x2) =(

x

1six2x1

x

2sinon.et la question precedente susent a

conclure. Supp osonsque maxnd'ariten2 soit primitif. Alors, en ecrivant : max n+1(x1;:::;xn;0) =maxn(x1;:::;xn) max n+1(x1;:::;xn;m+ 1) =( m+ 1 simaxn(x1;:::;xn)m+ 1 max n(x1;:::;xn) sinon.

Ceci montre quemaxn+1. est primitive recursive.

Question 7(1 point)

Montrer, en utilisant le schema de minimisation (\schema-"), que les fonctions suivantes sont-recursives : (a)f(n) =pnsinest un carre parfait, indeni sinon. (b)f(x;y) =E(x=y) la partie entiere de la division dexpary.Solution:

Sans trop de suspense :

(a)f(n) =:k[k2=n] (b)f(x;y) =:k[ky > x]1.

3 Grammaires

Question 8(1 point)

Quels langages sont engendres par les grammaires suivantes : (a)G= (fS;Ag;fa;b;cg;R;S) avecR=fS!aSjbA;A!bAjcg. (b)G= (fSg;fag;R;S) avecR=fS!aSaaSjaaag. On justiera soigneusement, mais rapidement.Solution: Par emme du correcteur, on donne uniquement les langages. (a)L(G) =a?bb?c. (b)L(G) =fa3kjkimpairg.

Question 9(2 points)

Donner des grammaires pour les langages suivants :MIF15 Complexite et Calculabilite, Master Info - 2014-2015 3/8

(a)Les mots sur l'alphab etfa;bgqui sont egaux a leur mot miroir. (b) Les mots sur l'alphab etfa;b;cgqui contiennent autant deaque deb.Solution: (a)S!aSajbSbjajbj" (b) Autan tde aque debn'est pas dicile a realiser, et ensuite on bricole pour ajouter descun peu partout :

S!CaCSCbCjCbCSCaCj"jC

C!cCj"

Une autre solution, en utilisant une grammaire contextuelle :

S!ABSjcSj"

AB!BA Ac!cA A!a Bc!cB B!b Pour cette grammaire, on introduit autant deaque debet un nombre arbitraire de c, puis on melange les lettres pour obtenir le mot recherche.

Il resterait a justier.

4 Indecidabilite : le Probleme de Correspondance de Post.

Soit un alphabet ni, etP??un ensemble ni de dominos etiquetes par des mots sur l'alphabet (des paires de mots, donc). Le Probleme de Correspondance de Post (PCP), introduit par Emil Post en 1946, consiste a determiner s'il existe une sequence de dominos deP tels que le mot obtenu par la concatenation des premieres composantes est identique a celui forme par la concatenation des secondes composantes. Plus formellement, on cherche a determiner l'existence d'une suite (ui;vi)06i6ntelle que :806i6n;(ui;vi)2Petu0u1un= v

0v1vn.

Question 10(2 points)

Resoudre PCP\a la main"pour les instances suivantes.Si une correspondance existe, on la donnera explicitement. Sinon, on justiera soigneusement qu'une telle correspondance n'existe pas. (a)P0=f(a;aaa);(aaaa;a)g; (b)P1=f(aab;ab);(bab;ba);(aab;abab)g; (c)P2=f(a;ab);(ba;aba);(b;aba);(bba;b)g;

(d)P3=f(ab;bb);(aa;ba);(ab;abb);(bb;bab)g.MIF15 Complexite et Calculabilite, Master Info - 2014-2015 4/8

Solution:

Les solutions qui suivent melangent deux notations, la notation par paire (gauche;droite) qui est celle de l'enonce et la notation par dominohaut bas, qui est plus lisible. (a)

On a une c orrespondance,en faisan ta

aaaa aaaa aaaaaaa aaaaa a, ce qui donne en haut comme en basaaaaaaaaaaa. (b) Une telle corresp ondancen'existe pas. En eet, une corresp ondancene p eutd emarrer par les paires 1 ou 3 parce qu'alors le mot de gauche commence paraabet celui de droite parab. Si elle commence par la deuxieme paire, alors a gauche on ababet a droiteba, du coup comme aucune des deux autres paires ne contient un mot qui commence par bcomme deuxieme composante, on est oblige de rajouter une occurence de la paire

2. Seules les paires 2 peuvent donc ^etre encha^nees pour creer une correspondance.

Comme les mots de la paire 2 ont des tailles dierentes, on ne pourra jamais obtenir de correspondance. (c)

Il existe une corresp ondance: a

abbba bba aba. Cela donne des deux c^otesabbaba. (d) Imp ossibleaussi, car les paires 3 et 4 fon tgrossir le m otde droite (plus vite que celui de gauche), et on n'a aucune possibilite de retablir la taille. De plus on ne peut demarrer une correspondance par 1 ou 2.

Question 11(1 point)

Donner un algorithme pour decider PCP dans le cas ou ne contient qu'une seule lettre.Solution: Soit =fag, on peut remarquer que pour tout motw2?, on aw=ajwj. On peut montrer qu'il existe une correspondance dansPsi et seulement si : soit on a u v2Ptel quejuj=jvj; soit il existe u 1v 1;u 2v

22Ptels queju1j>jv1jetju2j

Si il existeu

v2Ptel quejuj=jvj, la sequence contenant uniquementu vest une correspondance, puisqueu=ajuj=ajvj=v. Si il existeu 1v 1;u 2v

22Ptels queju1j>jv1j

etju2j0 etju1j jv1j>0 et la sequenceu 1v

1jv2jju2ju

2v

2ju1jjv1j

forme une correspondance car on obtient en haut a qui est egal aajv1j(jv2jju2j)ajv2j(ju1jjv1j), le mot qu'on obtient en bas. Si en revanche on n'est pas dans cette situation, cela signie que soit 8u v2P;juj>jvj;MIF15 Complexite et Calculabilite, Master Info - 2014-2015 5/8 |soit 8u v2P;jujjvj, alors pour toute sequence de dominosu 0v 0u nv n, on a

On en deduit que

u

0u1un=aju0u1unj6=ajv0v1vnj=v0v1vn:

Par consequent tester si il existe une correspondance constituee de dominos dePrevient a tester si il existeu 1v 1etu 2v

2dansPveriantju1j>jv1jetju2j6jv2j, ce qui est decidable.

On considere maintenant une variante de PCP, le Probleme de Correspondance de Post Modie (PCPM). Pour ce probleme, on considere un ensemble ni de dominosPet un domino initial (u0;v0)2P, et on cherche a determiner l'existence d'une correspondance qui commence par (u0;v0). On considere comme acquis que PCPM est indecidable: en eet il existe une reduction du probleme de l'arr^et d'une machine de Turing vers PCPM. On va maintenant montrer que PCP est indecidable, en reduisant depuis PCPM. On commence par introduire deux fonctions pets. Soit $ un nouveau symbole n'appartenant pas a , pour tout motw=a1a2an(lesai sont les lettres), on denit :( p(w) = $a1$a2$an s(w) =a1$a2$an$

Question 12(2 points)

Montrer que les fonctionspetsverient les proprietes suivantes : (a) p ourdeux mots vetw,p(vw) =p(v)p(w) ets(vw) =s(v)s(w);Solution:

Siv=a1a2anetw=b1b2bm, alors

p(vw) =p(a1a2anb1b2bm) =$a1$a2$an$b1$b2$bm =($a1$a2$an)($b1$b2$bm) =p(w)p(v) s(vw) =s(a1a2anb1b2bm) =a1$a2$an$b1$b2$bm$ =(a1$a2$an$)(b1$b2$bm$) =s(w)s(v) (b) p ourtout mot w,p(w)$ = $s(w).MIF15 Complexite et Calculabilite, Master Info - 2014-2015 6/8

Solution:

p(a1a2an)$ = $a1$a2$an$ = $a1$a2$an$ = $s(a1a2an) SoitP;(u0;v0) une instance une PCPM, on denitP0=f(p(u0);$s(v0))g [P1[P2avec : P

1=f(p(u);s(v))j(u;v)2Pg

P

2=f(p(u)$;s(v))j(u;v)2Pg

Question 13(2 points)

Montrer queP;(u0;v0) admet une solution pour PCPM si et seulement siP0admet une solution pour PCP.Solution: Supposons d'abord que l'instance originale de PCPM a une solutionu 0v 0u nv n, avec le haut et le bas egaux a un certain motw: u

0u1un=v0v1vn=w

Gr^ace a la question 12, on a :

p(w)$ =p(u0)p(u1)p(u2)p(un1)p(un)$ =$s(w) =$s(v0)s(v1)s(v2)s(vn1)s(vn):

Par denition deP0, on a

|p(u0)$s(v0)2P0; |816k < n;p(uk)s(uk)2P1P0; |p(un)$s(vn)2P2P0.

Par consequent la sequencep(u0)$s(v0)p(u1)s(v1)p(u2)s(v2)p(un1)s(vn1)p(un)$s(vn)est une correspondance deP0.

SiP0admet une solution, on peut remarquer qu'elle commence necessairement parp(u0)$s(v0)(c'est le seul domino pour lequel la partie superieure et la partie inferieure commencent par

la m^eme lettre) et nit forcement par un domino deP2, puisque ce sont les seuls dont les parties superieure et inferieure nissent par la m^eme lettre. Par consequent toute solution deP0est de la formep(u0)$s(v0)p(u1)s(v1)p(un1)s(vn1)p(un)$s(vn)ouu 0v 0u 1v 1u 2v 2u n1v n1u nv nest une solution deP.MIF15 Complexite et Calculabilite, Master Info - 2014-2015 7/8

Question 14(1 point)

En deduire que PCP est indecidable.Solution:

Notons(P;(u0;v0)) =P0, deni comme precedement.est une fonction calculable, et gr^ace a la question 13 on sait que : (P;(u0;v0))2PCPM,(P)2PCP: Par consequentest unereductionde PCPM vers PCP, et comme PCPM est indecidable, PCP l'est aussi.MIF15 Complexite et Calculabilite, Master Info - 2014-2015 8/8quotesdbs_dbs45.pdfusesText_45

[PDF] fonction calculable

[PDF] langage récursif

[PDF] épaisseur atmosphère saturne

[PDF] fonction primitive récursive exercice corrigé

[PDF] théorème de godel démonstration

[PDF] codage de godel

[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal