Université d'Orléans Année M1 Info Calculabilité Complexité TD n
3
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
3
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Niveau: Supérieur, Master, Bac+4
Université d'Orléans Année 2011-2012 M1 Info — Calculabilité & Complexité TD n? 3 Indécidabilité & Non-calculabilité Problèmes indécidables Réduction (définition) : On dit que le problème A se réduit au problème B s'il existe une machine de Turing (ou un algorithme) qui associe à chaque instance positive (resp. négative) du problème A une instance positive (resp. négative) du problème B. Exercice 1 : Problème de l'arrêt diagonal & problème de l'arrêt. 1. Montrer que toute machine de Turing peut être codée par un unique entier. 2. Problème Diag entrée : une machine de Turing M ayant pour code m. sortie : le calcul de M sur l'entrée m s'arrête-t-il ? Montrer que le problème Diag n'est pas décidable par une machine de Turing. 3. Problème Arrêt entrée : un couple (m,x) où m est le code d'une machine de Turing M et x est une entrée pour M. sortie : le calcul de M sur l'entrée x s'arrête-t-il ? i) Montrer que si un problème indécidable A se réduit à un problème B, alors B est également indécidable. ii) Déduire des questions 2. et de 3i. que le problème de l'Arrêt est indécidable. Exercice 2 : Réductions.
Voir
Université d'Orléans Année 2011-2012 M1 Info — Calculabilité & Complexité TD n? 3 Indécidabilité & Non-calculabilité Problèmes indécidables Réduction (définition) : On dit que le problème A se réduit au problème B s'il existe une machine de Turing (ou un algorithme) qui associe à chaque instance positive (resp. négative) du problème A une instance positive (resp. négative) du problème B. Exercice 1 : Problème de l'arrêt diagonal & problème de l'arrêt. 1. Montrer que toute machine de Turing peut être codée par un unique entier. 2. Problème Diag entrée : une machine de Turing M ayant pour code m. sortie : le calcul de M sur l'entrée m s'arrête-t-il ? Montrer que le problème Diag n'est pas décidable par une machine de Turing. 3. Problème Arrêt entrée : un couple (m,x) où m est le code d'une machine de Turing M et x est une entrée pour M. sortie : le calcul de M sur l'entrée x s'arrête-t-il ? i) Montrer que si un problème indécidable A se réduit à un problème B, alors B est également indécidable. ii) Déduire des questions 2. et de 3i. que le problème de l'Arrêt est indécidable. Exercice 2 : Réductions.
- jeu approprié de tuiles
- m1 info —
- feuille de td n?
- problème de l'arrêt diagonal
- complexité td
- problème arrêt
- tuile
Publié par
Langue
Français
UniversitÉ d’OrlÉans M1 Info— CalculabilitÉ & ComplexitÉ
Indecidabilite & Non-calculabilite
ProblÈmes indÉcidables
AnnÉe 2011-2012 ◦ TD n3
RÉductionOn dit que le problÈme(dÉfinition) :Ase rÉduitau problÈmeBs’il existe une machine de Turing (ou un algorithme) qui associe À chaque instance positive (resp. nÉgative) du problÈmeAune instance positive (resp.nÉgative) du problÈmeB.
Exercice 1: ProblÈmede l’arrt diagonal & problÈme de l’arrt.
1. Montrerque toute machine de Turing peut tre codÉe par un unique entier. 2. ProblÈmeDiag entrÉe: unemachine de TuringMayant pour codem. sortie: lecalcul deMsur l’entrÉems’arrte-t-il ? Montrer que le problÈmeDiagn’est pas dÉcidable par une machine de Turing. 3. ProblÈmeArrt entrÉecouple: un(m, x)oÙmest le code d’une machine de TuringMetxest une entrÉe pourM. sortie: lecalcul deMsur l’entrÉexs’arrte-t-il ? i) Montrerque si un problÈme indÉcidableAse rÉduit À un problÈmeB, alorsB est Également indÉcidable. ii) DÉduiredes questions 2.et de 3i.que le problÈme de l’Arrtest indÉcidable.
Exercice 2: RÉductions. Montrer que les problÈmes suivants sont indÉcidables en procÉdant par rÉduction du problÈme de l’Arrt(ou d’un autre problÈme indÉcidable) : i) ProblÈmeTerminaisonADA entrÉeprogramme P Écrit en: unADAet une entrÉexpour P. sortie: l’exÉcutionde P surxtermine-t-elle ?
ii) ProblÈmeArrtε entrÉe: unemachine de TuringM. sortie: l’exÉcutiondeMsur le mot videεtermine-t-elle ?
1
iii) ProblÈmeArrtUniversel entrÉemachine de Turing: uneM. sortie:Ms’arrte-t-elle sur toutes les entrÉes ?
iv) ProblÈmeArrtsIdentiques entrÉemachines de Turing: deuxM1etM2. sortie:M1etM2s’arrtent-elles sur les mmes entrÉes ?
v) ProblÈmeRessourceUtilisÉe entrÉe: unprogramme P dans un langage donnÉ et une entrÉex. sortieutilisera-t-il une ressource donnÉe (: Pimprimante,port. . ), .lors de son exÉcution surx?
Exercice 3: Pavageset indÉcidabilitÉ.
ProblÈmePavageDuPlan entrÉe:Tun jeu fini de tuiles ett0une tuile. sortiepaver le plan avec: peut-onTen partant det0? En simulant une machine de Turing par un jeu appropriÉ de tuiles puis en procÉdant par rÉduction, montrer que le problÈmePavageDuPlanest indÉcidable.
2
Encore plus d’indÉcidabilitÉ et un petit peu de non-calculabilitÉ
Exercice 4: Non-calculabilitÉde la fonctionBusy Beaver. ◦ On reprend les dÉfinitions et notations de l’exercice 6 de la feuille deTD n2. 1. Enraisonnant par l’absurde, montrer que la fonctionBusy BeaverBB:n7→BB(n) n’est pas calculable par une machine de Turing (on pourra considÉrer plusieurs machines de Turing et leur composition). 2. Montrerque la fonctionMax ShiftS:n7→S(n)n’est pas calculable : i) enraisonnant de la mme faÇon qu’À la question 1. ii) enprocÉdant par rÉduction du problÈme de l’Arrt.
Exercice 5: ThÉorÈmede Rice[Henry Rice, 1953]. ThÉorÈme de RicepropriÉtÉ non triviale (c’est-À-dire qui n’est ni toujours vraie: Toute ni toujours fausse) sur les langages rÉcursivement ÉnumÉrables est indÉcidable. 1. Donnerdes exemples de propriÉtÉs non triviales sur les langages rÉcursivement ÉnumÉrables. 2. Enquoi le problÈme de l’Arrtest-il un cas particulier du thÉorÈme de Rice ? 3. DÉmontrerle thÉorÈme de Rice en raisonnant par l’absurde et en utilisant le problÈme de l’Arrt.
Exercice 6: Quelquesfonctions non-calculables. Montrer que les fonctions suivantes ne sont pas calculables : 1. lafonction partielleRdÉfinie parR(M, x) =n→oÙn→est le nombre de mouvements vers la droite que fait la tte de la machineMlors du calcul sur l’entrÉex. 2. lafonction partielleCdÉfinie parC(M, x) =ncoÙncest le nombre de cases utilisÉes par la machineMlors du calcul sur l’entrÉex.
3
