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.

Définition

Soient L_1, L_2 \subset \Sigma^*. Une réduction de L_1 à L_2 est une fonction récursive

  • \rho :\Sigma^* \rightarrow \Sigma^*\quad | \quad \omega\in L_1 \Leftrightarrow \rho\left(\omega\right)\in L_2
· 2009/11/23 09:50 · Maurice Lanselle

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 ©. "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 © 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 :

  1. on déplace le contenu du ruban 1 sur le ruban 2.
  2. on fait fonctionner M sur le ruban 1. Si M s'arrête, on fait:
  3. …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
    1. On peut ramener de manière récursive tout MT à une MT à 1 suel état d'arrêt h
    2. 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

 
m1ilc/c_et_c_a.txt · Dernière modification: 2010/01/06 21:20 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki