==== II.4 Problèmes Indécidables ==== === Théorème (rappel) === * H n'est pas récursif * Il existe des langages récursivement énumérables qui ne sont pas récursifs * La classe des langages récursivement énumerables n'est pas stable par complément * Exemple : * H n'est pas récursif et \$ \bar{H} \$ n'est pas récursivement énumerable. * Problème indécidable correspond à un langage non-récursif. C'est à dire qu'il __n'__existe __pas__ de MT qui décide le langage <=> il n'existe pas d'algorithme qui résout le problème. * Exemple : H n'est pas récursif <=> l'arrêt n'est pas décidable === Réduction de problème === Pour pouvoir démontrer que d'autres problèmes sont indécidables, nous allons employer la réduction de problèmes : montrer que résoudre un nouveau problème permettrait de résoudre un problème qu'on sait déjà indécidable, et d'en conclure que le nouveau doit l'être aussi. {{page>c_et_c_def_reduction|nofooter}} === Théorème === Si \$\rho\$ est une réduction de L1 à L2 * si L2 est récursif alors L1 est récursif * si L1 n'est pas récursif alors L2 n'est pas récursif non plus. == Preuve == Soit M_{\rho} une MT qui implante \$\rho\$ (qui est récursif). | w =>^ M_{\rho} |=> | \$\rho\left(w\right)\$ |=> ^ M_2 | => Y\\ => N | | ||||| Décide L_2 | | | | décide L1 ||||| | * Y : \rho\left(w\right) \in L_2,\quad w\in L_1 * N : \rho\left(w\right) \notin L_2,\quad w\notin L_1 === Théorème === Les problèmes suivants sont indécidables avec des MT : * a) Etant donnée M une MT et \$\omega\in\Sigma^*\$, est-ce que M s'arrête avec \$\omega\$ en entrée? * b) Etant donnée M une MT, est-ce que M s'arrête avec le mot vide en entrée? * c) Etant donnée M une MT, est-ce que M s'arrête avec certains mots en entrée? (existe-il des entrées avec lesquelles la machine s'arrête?) * d) Etant donnée M une MT,, est-ce que M s'arrête quelque soit le mot en entrée? * e) Etant donnée M1 et M2 deux MT, est-ce qu'elles s'arrêtent pour les mêmes entrées? * f) Etant donnée M une MT qui semi-décide L, est-ce que L est rationnel? (resp. algébrique? récursif?) * g) Il existe une MT M pour laquelle le problème suivant est indécidable : "Etant donné \$\omega\in\Sigma^* \$, est que M s'arrête avec \$\omega\$ en entrée? == Preuves === == a == C'est le "halting problem" dont l'indécidabilité a été vu la dernière fois. == b== On fait une réduction \$\rho\$ ramenant le halting problem à ce problème. Soit w =a_1 a_2 a_3 \ldots a_m. Ecrire le mot sur le ruban par une suite de mouvements et écritures : R a_1 R a_2 R a_3 \ldots R a_m L_{\sqcup} avec une machine qui prend w \in \Sigma^* et produit cette séquence \in \Sigma_U^*. Le codage ce cette machine -- fonction récursive -- est laissé en exercice. Ensuite, \rho : \Sigma_U \rightarrow \Sigma_U, "M" \; "w" \mapsto \underbrace{"R a_1 R a_2 R a_3 \ldots R a_m L_{\sqcup} M"}_{M\prime} \rho __est récursive__ (pas triviale à démontrer). "M"\;"w" \in H \Rightleftarrow \rho\left("M" "w"\right) = \underbrace{"R a_1 R a_2 R a_3 \ldots R a_m L_{\sqcup} M"}_{M\prime \text{s'arrete ave le mot vide en entree}} == c== On fait une réduction de problème (b) au problème (c). "M" \mapsto \underbrace{"Efface\quad M"}_{M\prime}. Efface est une MT qui efface le ruban. Mi s'arrete pour une ou des entrées //si et seulement si// M s'arrête avec le mot vide en entrée. Donc le problème (c) est indécidable. == d== Comme dans (3), même réduction. //Si et seulement si// M' s'arrête pour toutes ses entrées... == e== ==f== Soit M une machine de Turing, et w\in \Sigma^*. On construit M', la MT équivalente à la MT à 2 rubans qui réalise l'algorithme suivant : - on déplace le contenu du ruban 1 sur le ruban 2. - on fait fonctionner M sur le ruban 1. Si M s'arrête, on fait: - ...fonctionner U sur le ruban 2. M \mapsto M\prime est récursif. \rho_f: M' s'arrête avec w en entrée <=> M s'arrête avec le mot vide en entrée __et__ U s'arrête avec w en entrée. * L(M') = \Phi : M ne s'arrête pas avec le mot vide (ou \$w \in H\$). * L(M') = H : si M s'arrête avec le mot vide. * \Phi est rationnel (régulier), algébrique (hor sontexte) et récursif. * H : aucun des trois. * \rho_f fait une réduction du problème (b) au problème (f), avec des variantes. == g== U ? ==== Problèmes / Exercices ==== == Passage par un état == Etant donnée une MT M, un état q de M et un mot w\in \Sigma^*, est-ce que M passe par l'état q avec w en entrée? * Est-ce que ce problème est décidable ou indécidable? * Indécidable, car il suffit de considérer q\in H - On peut ramener de manière récursive tout MT à une MT à 1 suel état d'arrêt ''h'' - Pour cette MT M', il suffit de prendre ''q = h'' pour résoudre le halting problem. === Définition === Soit M une MT et k\in \mathbb{N} et w\in \Sigma^*. On dit que M utilise (au moins) k cases du ruban avec le mot w en entrée <=> \exists q\in K : \left(s, \triangleright\sqcup w\right) \vdash_M^{*} \left(q, \triangleright u \underline{a} v \right) \& | u \underline{a} v|\geq k ---- == Utilisation de cases (a) == Etant donnée une MT, M, un mot w\in \Sigma^* et k\in \mathbb{N} est-ce que M utilise au moins k cases avec le mot w en entrée? * Décidable ou indécidable? * Décidable ! | K | \times |\Sigma|^{k-1} peut être très grand, mais __fini__ => on peut détecter des boucles éventuelles. FIXME suite de l'explication à rajouter == Utilisation de cases (b) == Soit M une MT, w\in \Sigma^* et f:\Sigma^* \rightarrow \mathbb{N} une fonction récursive. Est-ce que M utilise au moins f(w) cases avec w en entrée? * Décidable : comme pour le cas précédent, mais avec une phase d'initialisation pour "calculer k" = f(w). == Utilisation de cases (c) == Soit M un MT, w\in \Sigma^*. Est-ce qu'il existe un entier k \geq O tel que M utilise __moins de__ k cases avec w en entrée? * Indécidable. FIXME exercice. ---- ==== Navigation ==== [[c_et_c_9|]] <--> [[c_et_c_b|]]