Université d'Orléans Année M1 Info Calculabilité Complexité TD n

Description

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.

• jeu approprié de tuiles


• m1 info —


• feuille de td n?


• problème de l'arrêt diagonal


• complexité td


• problème arrêt


• tuile

Informations

• Publié par: larec
• Nombre de lectures: 55
• Langue: Français

Extrait

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’arrt diagonal & problÈme de l’arrt.

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’arrte-t-il ? Montrer que le problÈmeDiagn’est pas dÉcidable par une machine de Turing. 3. ProblÈmeArrt entrÉecouple: un(m, x)oÙmest le code d’une machine de TuringMetxest une entrÉe pourM. sortie: lecalcul deMsur l’entrÉexs’arrte-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’Arrtest 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’Arrt(ou d’un autre problÈme indÉcidable) : i) ProblÈmeTerminaison ADA entrÉeprogramme P Écrit en: unADAet une entrÉexpour P. sortie: l’exÉcutionde P surxtermine-t-elle ?

ii) ProblÈmeArrt ε entrÉe: unemachine de TuringM. sortie: l’exÉcutiondeMsur le mot videεtermine-t-elle ?

1

iii) ProblÈmeArrtUniversel entrÉemachine de Turing: uneM. sortie:Ms’arrte-t-elle sur toutes les entrÉes ?

iv) ProblÈmeArrtsIdentiques entrÉemachines de Turing: deuxM 1 etM 2 . sortie:M 1 etM 2 s’arrtent-elles sur les mmes 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 ett 0 une tuile. sortiepaver le plan avec: peut-onTen partant det 0 ? 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 mme faÇon qu’À la question 1. ii) enprocÉdant par rÉduction du problÈme de l’Arrt.

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’Arrtest-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’Arrt.

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 tte de la machineMlors du calcul sur l’entrÉex. 2. lafonction partielleCdÉfinie parC(M, x) =n c oÙn c est le nombre de cases utilisÉes par la machineMlors du calcul sur l’entrÉex.

3