[PDF] Calculabilité Cours 3 : réductions

View - Download Calculabilité Cours 3 : réductions

Previous PDF

Next PDF

Calculabilite

Cours 3 : reductionsKevinPerrot{ Aix Marseille Universite { printemps 2019

Table des matieres

3.7 Reductions (many-one) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

3.8 Theoreme de Rice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

3.9 Reductions (oracle) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

3.10 Le probleme de correspondance de Post (PCP) . . . . . . . . . . . . . . .

4

3.11 Indecidabilite de la logique du premier ordre . . . . . . . . . . . . . . . .

5

3.7 Reductions (many-one)

Une des formulations les plus populaires du resultat de Turing en 1936 est donnee par le theoreme de l'arr^et. Voyons maintenant une facon plus epuree de formuler ces idees, qui nous permettront d'aller plus loin de facon elegante. Theoreme 1.Le langageLd=fhMi jMn'accepte pas le mothMign'est pas re. Demonstration.Par l'absurde, supposons qu'une machineMdreconnaisseLd. Considerons alors l'entreehMdidonnee a la machineMd. Deux cas sont possibles. Si Mdn'accepte pashMdialors, par denition du langageLd, le mothMdiest dans L d. OrMdreconnaitLd, doncMdacceptehMdi, une contradiction. Si MdacceptehMdialors, par denition du langageLd, le mothMdin'est pas dans L d. OrMdreconnaitLd, doncMdn'accepte pashMdi, une contradiction.

Dans les deux cas nous arrivons a une contradiction.La preuve est cette fois encore plus simple! Ce resultat nous dit qu'il n'existe pas

de MTMd(un seul et m^eme algorithme qui repond oui/non correctement pour chaque instance) pour decider si une machineMreconnait le mothMi(m^eme si la machineMd a le droit de ne pas s'arr^eter siMne reconnait pashMi). Ce probleme peut sembler articiel, mais il sert degrainepour deriver la non recursivite d'autres problemes (plus

naturels), via une methode qui s'appelle unereduction.Intuitivement, un problemeAse reduit a un problemeBsi connaissant un algorithmepour decider/calculerB, on peut obtenir un algorithme pour decider/calculerA.Denition 2.Unereduction many-one Turingdu langageAau langageBest unefonction calculablef: A!Btelle quew2A()f(w)2B. On noteATmB.On appelleinstancedeLun motw2Ldont on se demande s'il appartient au lan-gageL. Une reduction montre que si le langageBest decidable alors il en est de m^emedu langageA. On utilise ensuite l'idee suivante : pour montrer qu'un langageBest1

indecidable, on choisit un langageAbien connu pour ^etre indecidable, et l'on reduitAaB. On aura alorsBdecidable =)Adecidable etAindecidableet l'on peut en deduire (regle de resolution!) que par consequentBest indecidable.On notera que le raisonnement est tout aussi valide en remplacantdecidableparrecursivement enumerable.1

Corollaire 3.Le langageLu=fhMi#wjMaccepte le motwgn'est pas recursif. Plus precisement, son complementLun'est pas re. Demonstration.Nous allons reduireLdaLuen decrivant une procedure algorithmique pour transformer les instances deLden des instances deLu. Soitwune instance deLd. 1. la mac hinev eriew2Lenc, siwn'est pas un encodage valide alors on retourne l'instancehMpalindromei#abba(on a bienw =2LdethMpalindromei#abba =2Lu); 2. si w=hMiest un encodage valide, alors on retourne l'instancew#w=hMi#hMi (on a bienw2Ldsi et seulement sihMi#hMi 2Lu). Cette reduction montre que siLuest recursivement enumerable alorsLdl'est egalement, or le theoreme 1 nous dit queLdn'est pas recursivement enumerable, doncLunon plus,

et par consequentLun'est pas recursif.Corollaire 4.Le langageLhalt=fhMi jMs'arr^ete quand on la lance sur l'entree videg

n'est pas recursif. Demonstration.Nous allons reduireLuaLhalt. Etant donneehMi#wune instance de L u, nous construisons l'instancehM0isuivante pourLhalt: 1. on v eriehMi 2Lenc, sihMin'est pas un encodage valide alors on retourne l'instancehM0i=hMi; 2. sinon on co nstruithM0iavecM0la machine qui commence par ecrirewsur le ruban (cela est possible en utilisantjwjetats), puis entre dans l'etat initial de M(M0va alors se comporter commeM), et nous rajoutons egalement aM0des transitions, depuis tous les etats non naux ouMs'arr^ete (transition indenie), vers un etat qui boucle a l'inni 2. Dans tous les cas, nous avons bienhMi#w2Lu() hM0i 2Lhalt, donc siLhaltest recursif alorsLuest recursif, or le theoreme 3 nous dit queLun'est pas recursif, donc L

haltn'est pas recursif.Voyez-vous la reduction utilisant le theoreme 4 pour demontrer le theoreme de l'arr^et?

1. Navre pour l'anglicisme,many-onequalie la fonctionf(de plusieurs vers un, il faut comprendre

par la que ni l'injectivite ni la surjectivite ne sont imposees).

2. Pour les fous de formalisme : soithMi#wune instance deLuavecM= (Q;;;;q0;B;qF)

etw=w0:::wk, dans le second cas nous construisonshM0iavecM0= (Q[ fq00;:::;q0k+1g [ fq0loopg;;;0;q00;qF) avec0(q;a) =(q;a) pour toutqetaou(q;a) est denie, et0(q0i;B) = (q0i+1;wki;L) pour tout 0ikan d'ecrirewsur le ruban initiallement vide, et0(q0k+1;B) = (q0;B;R) pour aller dans l'etat initial deMsur le debut du motw, et0(q;a) = (q0loop;B;R) pour tout q2Qeta2 pour lesquels(q;a) est indenie, et enn0(q0loop;a) = (q0loop;B;R) pour touta2. 2

3.8 Theoreme de Rice

Nous avons vu que de nombreuses questions sur les MT sont indecidables. Certaines questions sont clairement decidables, comme par exemple : est-ce qu'une MT donnee a 5 etats? Il s'avere cependant quetoute question non triviale qui concerne unique- ment le langage reconnu par une MT (plut^ot que la machine elle-m^eme) est indecidable. Une question non triviale etant une question qui n'est pas toujours vraie ou toujours fausse. Denition 5.SoitPune famille de langages. On appellePunepropriete non triviale si il existe deux machines de TuringM1etM2telles queL(M1)2PetL(M2)=2P. Theoreme 6.Pour toute propriete non trivialeP, il n'existe aucun algorithme pour decider si une MTMverieL(M)2P. Autrement dit,LP=fhMi jL(M)2Pgn'est pas recursif. Demonstration.Nous utilisons une reduction depuisLu. Sans perte de generalite, nous pouvons supposer;=2P(sinon on considere le complement dePau lieu deP). Puisque Pest non triviale, il existe une MTMPtelle queL(MP)2P. Etant donneehMi#wune instance deLu, nous allons constuire l'instancehM0i(pour le probleme d'appartenance deL(M0) aP) avecM0la machine qui : 1. cop ieson en treeusur un ruban separe pour l'utiliser plus tard; 2. ecritwsur le ruban et place la t^ete sur la premiere lettre dew; 3. en tredans l' etatinitial de M. A partir de laM0simuleM, en ignorantu, jusqu'a ce queMentre dans son etat nal; 4. si Mentre dans son etat nal, alors le motuest recopie sur un ruban blanc (que des symbolesB) et la machineMPest simulee suru. On entre dans un etat nal siMPaccepteu. Etant donne n'importe quelshMietw, la machineM0(et donc son codehM0i) peut eectivement ^etre construite algorithmiquement. La correction de la reduction (hMi#w2Lu() hM0i 2LP) est assuree par les observations : si Macceptew, alorsM0acceptera exactement les motsuqueMPaccepte, donc dans ce casL(M0) =L(MP)2PethM0i 2LP; si Mn'accepte pasw, alorsM0n'accepte aucun motu, donc dans ce casL(M0) = ;=2PethM0i=2LP. On en conclut que si la proprietePest decidable alorsLuest decidable, or le theoreme

3 nous dit queLun'est pas decidable, donc la proprietePn'est pas decidable.Remarque 7.M1simuleM2=M1se comporte commeM2

=M1suit la table de transition deM2.Appliquons le theoreme de Rice. Les problemes suivants sont indecidables :

|est-ce qu'une MT donnee en entree accepte tous les mots? |est-ce queL(M)est un langage regulier pour une MTM? |est-ce qu'une MT donnee accepte tous les palindromes? 3

3.9 Reductions (oracle)

Les reductions Turing que nous avons denies dans la section 3.7 ont une denition simple, mais sont en fait assez restraintes. Nous proposons maintenant une denition plus generale de la notion de reduction, qui correspond exactement a l'idee d'imaginer que nous puissions resoudre un problemeB, et de s'interesser alors a la resolution d'un problemeA. Denition 8.Un langageAestTuring-reductiblea un langageBsi il existe une machine de Turing avecoracleB, qui decide le langageA. On noteATB. Une machine de Turing avec oracleBest une machine qui peut, au cours de son calcul, obtenir autant de reponses qu'elle souhaite sur des questions d'appartenance au langage B: est-ce que telw2B? est-ce que tel autrew02B? Et l'oracle pour le langageBlui donne des reponses oui/non, instantanement. La denition suivante explique comment implementer formellement cette idee dans le modele des machines de Turing. Denition 9.Une machine de TuringMavecoracleBa un ruban supplementaire appele ruban d'oracle, et trois etats speciauxqquestion,qouietqnon. A chaque fois queM entre dans l'etatqquestion, la machine va dans l'etatqoui(siw2B) ouqnon(siw =2B) avecwle contenu du ruban d'oracle. Les reponses aux questions d'appartenance aBsont donnees instantanement, et comptent comme une seule etape de calcul. Gr^ace aux machines avec oracle, on peut denir lacalculabilite relative. C'est l'idee d'une machine branchee a une source d'information (comme par exemple un ordinateur branche a une base donnee, ou au world wide web...) qui est decrite par le langage de l'oracle. Le modele des machines de Turing sans oracle peut ^etre vu comme un modele oine, alors que le modele des machines de Turing avec oracle peut ^etre vu comme un modeleonline. Denition 10.L'ensemble des langages decidables avec oracleBestfAjATBg. Remarque 11.Une machine de Turing avec oracle, dont l'oracle est un langage recursif, decide un langage qui est egalement recursif. Remarque 12.Les reductions Turing many-one et Turing (avec oracle) ne sont pas equivalentes : si Aest Turing many-one reductible aB, alorsAest Turing reductible aB; tout langage r ecursifest T uringr eductible an 'importequel langage (puisque l'or acle est inutile), mais un langage recursif non vide ne peut pas ^etre Turing many- one reduit au langageB=;(puisque quels que soientfatwon aura toujours f(w)=2B). Donc par exemple, le langageest Turing reductible au langage;, mais pas Turing many-one reductible; tout langage est T uringr eductible ason c omplement,mais si Aest Turing many- one reductible aBetBest r.e. alorsAest egalement r.e. Par consequent, le complement du probleme de l'arr^et (qui n'est pas r.e.) n'est pas Turing many-one reductible a son complement (le probleme de l'arr^et, qui est r.e.).

3.10 Le probleme de correspondance de Post (PCP)

Le probleme de correspondance de Post (PCP) est un exemple simplede probleme indecidable qui ne semble pas (a premiere vue) parler de machines de Turing... 4 PCP est un genre de puzzle. Soit un alphabet etDfiniun ensemble ni de dominos, chaque domino etant un couple de mots. Le but est de constituer un assortimentdes dominos deD, c'est-a-dire une sequence de dominos (les repetitions sont autorisees) telle que la concatenation des premiers mots de chaque paire soit egale a la concatenation des seconds mots de chaque paire. Formellement, unassortimentest une suite dek2Ndominos(wi;w0i)

1iktelle que (wi)1ik= (w0i)1ik. Bien entendu,

certains ensembles de dominos admettent des assortiments, alors que d'autres non.

Exemple 13.L'ensemblebcca

;aab ;abbb admet l'assortimentaab ;bcca ;aab ;abbb avec le mot du haut egal au mot du bas. L'ensemble de dominosaab ;ba n'admet pas d'assortiment. On peut encoder les dominos par une cha^ne de caracteres, comme par exemple h bcca ;aab ;abbb i=bc#ca##a#ab##abb#b et la donner en entree a une machine de Turing. Soit

PCP=fhDi jDadmet un assortimentg.

Il se trouve que l'on peut reduireLhaltaPCP, en encodant une machine de Turing Mdans un ensemble de dominosDM, de facon a ce que la construction d'un assortiment des dominos deDMcorresponde forcement a l'execution de la machineDMsur l'entree vide. L'idee est qu'a chaque ajout d'un domino deDMon eectue une nouvelle etape du calcul deM, et la construction d'un assortiment termine (donc un assortiment existe) si et seulement l'execution de la machine sur l'entree vide s'arr^ete.

Theoreme 14.PCPn'est pas recursif.

3.11 Indecidabilite de la logique du premier ordre

Hilbert a pose la question suivante en 1928, a un moment ou les fondements des mathematiques allaient^etre boulverses : (Entscheidungsproblem) est-ce que toutenonce en logique du premier ordre (un fragment des mathematiques) peut ^etre algorithmique- ment

3demontre ou refute? Hilbert pensait que oui, les mathematiques sont belles et

nous allons tout conna^tre d'elles par ce biais. Cette section montre que non. (source :http://kilby.stanford.edu/~rvg/154/handouts/fol.html)

Rappels sur la logique du premier ordre

Une logique du premier ordre est donnee par un langage (Sf;Sr).A Chaque symbole de fonction et predicat est associe une arite (les symboles de fonction d'arite 0 sont des constantes). Les termes sont denis recursivement comme suit : le sv ariablesson tdes termes ; si t1;:::;tnsont des termes et sifest une fonctionn-aire, alorsf(t1;:::;tn) est un terme. Les formules sont denies recursivement comme suit : si t1;:::;tnsont des termes et sipest un predicatn-aire, alorsp(t1;:::;tn) est une formule (atomique);

si et sont des formules, alors:,^ ,_ et=) sont des formules;3. par une procedure automatique, en imaginant remplacer les mathematiciens par des machines...

5 |si est une formule etxune variable, alors8x:et9x:sont des formules. Le theoreme de completude du calcul de la resolution pour la logique du premier ordre dit que si j=alors on peut deriver la close vide?de [ f:g(sous forme clausale, obtenue par mise sous forme prenexe puis skolemisation puis mise sous forme normale conjonctive des formules propositionnelles) avec les regles de factorisation et resolution.

Preuve d'indecidabilite

Theoreme 15.Le probleme de savoir sij=dans la logique du premier ordre est indecidable. Demonstration.Nous allons reduire a ce probleme de decision celui de decider le langage L u=fhMi#wjMaccepte l'entreewg: Etant donnesMetw, nous allons construire ettels que j=si et seulement si hMi#w2Lu. PuisqueLuest n'est pas recursif, on pourra en deduire qu'il ne peut pas exister d'algorithme pour decider si j=(sinon on pourrait construire un algorithme pour deciderLu, or le theoreme 3 nous dit que c'est impossible). SoitM= (QM;M;M;M;qM0;BM;qMF) etwune instance du probleme d'apparte- nance aLu. Nous denissons le langageS= (Sf;Sr) avecSf=f(;0)g[f(a;1)ja2Mg etSr=f(fq;2)jq2QMg: la constante, un symbole de fonction unaireapour toute lettrea2M, et un symbole de predicat binairefqpour tout etatqde la machineM. Voici l'idee que nous allons suivre : les variablesxcorrespondront a des mots sur M, sera utilise pour le mot vide,a(w) sera le motaw, etfq(x;y) signiera queM, sur l'entree w, peut atteindre la conguration xqy(avec xle mot miroir dex).

La formule

f qM0(;w) correspond a la conguration initiale de la machineMsur l'entreew, qui est atteignable, donc cette formule doit ^etre vraie, nous la placons dans nos hypotheses . Attention a la distinction entre le motw(par exempleabba) et le terme de logique correspondant (dans cet exemplea(b(b(a()))), que nous ecrirons aussiabbapour faciliter la lecture). Nous allons maintenant faire en sorte que la formule =9x9y:fqMF(x;y) soit vraie dans cette theorie (c'est-a-dire soit une consequence logique de ) si et seule- ment sihMi#w2Lu(c'est-a-dire ssiMacceptew). Pour cela nous allons ajouter des formules dans , qui nous permettront de deduire que si une conguration est attei- gnable (le predicat correspondant est consequence logique de ), alors la conguration suivante donnee par la fonction de transitionMest egalement atteignable (le predicat correspondant est consequence logique de ). Pour toute transition de la formeM(q;a) = (p;b;R), nous rajoutons dans la formule

8x8y:fq(x;ay) =)fp(bx;y);

et pour toute transition de la formeM(q;a) = (p;b;L), nous rajoutons dans les formules

8x8y:fq(cx;ay) =)fp(x;cby) pour toutc2:

6 Pour ^etre rigoureux nous devons aussi ajouter dans les formules suivantes pour tout q2Q:

8x:fq(x;)()fq(x;B)

8y:fq(;y)()fq(B;y)

La construction de etest terminee. PuisqueMpossede un nombre ni de transitions sur un alphabet de taille nie, est de taille nie. Il nous reste a argumenter que j=si et seulement siMaccepte le motw. Pour le sens indirect, si l'on part de l'hypothese queMacceptewalors il existe une suite de transition de la machine de TuringMa partir de l'entreewqui atteint l'etat nalqMF, et a chacune de ces transitions nous pouvons faire correspondre une application de la regle de resolution a partir de la formulefqM0(;w), et puisqueMsur l'entreewatteint l'etat nalqMFalors nous allons pouvoir deduire que9x9y:fqMF(x;y), c'est-a-dire j=. Pour le sens direct (qui est un peu plus complique a prouver formellement), si l'on part de l'hypothese que j=, alors il existe une suite d'application des regles de resolution et factorisation telle que l'on derivede , et de cette suite d'application nous pouvons en deduire une suite de transitions de la machine de TuringMa partir de l'entreew(en fait, on peut se rendre compte que la regle de factorisation sera inutile, et que les applications de la regle de resolution partent defqM0(;w) pour arriver aen utilisant a chaque etape une formule qui correspond a une transition de la machine de TuringM).7quotesdbs_dbs45.pdfusesText_45

[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

[PDF] hsa prof

[PDF] indemnite tuteur stagiaire education nationale