TD 3 : Argument diagonal, Réductions

Énoncé (pas les mêmes numéros d’exercices)

EX 1

L_{diag} ≝ \{w_i \vert w_i \not∈ L(M_i)\}

On note $M_i$ la $i$-ième MT (elles sont dénombrables).

ABS : Donc $L_{diag} = L(M_j)$, pour un $j∈ℕ$.

Alors w_j ∈ L_{diag} = L(M_j) ⟺ w_j \not∈ L(M_j) = L_{diag}

EX 2

L_{accepte} ≝ \{⟨M,w⟩ \vert M \text{ accepte } w\}

Mq $L_{accepte}^c = {⟨M,w⟩ \vert M \text{ n’accepte pas } w}$ est tel qu’il existe un mot $w$ et une machine $M$ tq $M_{L_{accepte}^c}(⟨M,w⟩)=\bot$.

Il suffit de montrer qu’il existe un langage récursivement én. et non récursif $L^$ : dans ce cas, M_{L_{accepte}^c}(⟨M_{L^*},w⟩) = \bot pour un $w$ tel que $M_{L^}(w)=\bot$ (il en existe au moins un).


M2 :

Remarquons que $L_{accept} ≝ {⟨M,w⟩ \vert M \text{ accepte } w }$ est récursif ssi L_{accept}^c ≝ \{⟨M,w⟩ \vert M \text{ n'accepte pas } w\} est réc.

ABS : On considère le langage L' ≝ \{⟨M⟩ \vert M \text{ n'accepte pas } ⟨M⟩ \} et la machine M_{L'} : ⟨M⟩ \mapsto ⟨M,⟨M⟩⟩ \vdash_{M_{L_{accept}^{c}}}^{*} 𝛾

(ou : $M_{L’} : ⟨M⟩ ⟶$ simule ${M_{L_{accept}^{c}}}$ sur $⟨M,⟨M⟩⟩$ )

M_{L'} \text{ accepte } ⟨M_{L'}⟩ ⟺ M_{L_{accept}^{c}} \text{ accepte } ⟨M_{L'},⟨M_{L'}⟩⟩ \\ ⟺ M_{L'} \text{ n'accepte pas } ⟨M_{L'}⟩

EX 3

Remarquons que $L_{arret} ≝ {⟨M,w⟩ \vert M(w) \neq \bot }$ est récursif ssi L_{arret}^c ≝ \{⟨M,w⟩ \vert M(w) = \bot \} est réc.

ABS : On considère le langage L' ≝ \{⟨M⟩ \vert M(⟨M⟩) = \bot \} et la machine M_{L'} : ⟨M⟩ \mapsto ⟨M,⟨M⟩⟩ \vdash_{M_{L_{arret}}}^{*} 𝛾

On peut, sans perte de généralité, supposer qu’elle ne rejette aucun mot, quitte à la faire boucler indéfiniment sur les mots initialement rejetés (le langage reconnu est le même).

⟨M_{L'}⟩ ∈ L' ⟺ M_{L_{arret}^{c}} \text{ accepte } ⟨M_{L'},⟨M_{L'}⟩⟩ \\ ⟺ M_{L'}(⟨M_{L'}⟩) = \bot ⟺ ⟨M_{L'}⟩ \not∈ L_{M_{L'}} = L'

EX 4

M1 :

L_∅ ≝ \{⟨M⟩ \vert L(M) = ∅ \}

ABS : Si $M_∅$ reconnaît $L_∅$ : alors en considérant N_{M,w} : w' \mapsto ⟨M, w⟩ \text{ et simule $M_U$ dessus, en} \begin{cases} \text{acceptant si ça termine} \\ \text{ne terminant pas sinon.} \end{cases} dont le langage est non vide ssi $M(w) \neq \bot$ et M_{arret} : ⟨M, w⟩ \mapsto ⟨N_{M,w}⟩ \text{ et simule $\overline{M_∅}$ dessus}


M2 : On crée la machine $M_{arret}$ qui, à une machine $M$, on associe la machine $M’$ qui accepte ssi $M$ s’arrête (en remplaçant les “reject” par des “accept”), et la machine $M’’$ qui rejette tous les $w \neq 𝜀$ (ces mots ne seront pas dans le langage reconnu), et qui simule $M’(w)$ quand $w=𝜀$.

Puis : on simule $M_∅$ sur $⟨M’‘⟩$.

Le langage de $M’’$ est non vide ssi il contient $𝜀$, ssi $M(w)$ termine.

EX 5

M1 :

À toute machine $M$, on associe la machine $f(M)$ où on a remplacé les “reject” par des $\bot$ (boucle indéfiniment) (ainsi, $f(M)$ termine ssi $M$ accepte) ($f$ est calculable, avec la machine universelle).

M_{arret} : ⟨M, w⟩ \mapsto ⟨f(M),w⟩ \text{ et simule $M_{arret}$ dessus}

M2 :

$M_{accept}$ simule $M_{arret}$ :

  • si reject ($M$ ne termine pas) ⟶ reject
  • sinon : on simule $M$ sur $w$ avec la machine universelle.

EX 6

$𝕬≼𝕭$ :

  • EX 4 : $𝕬 = L_{arret}$, $𝕭 = L_∅$
  • EX 5 : $𝕬 = L_{arret}$, $𝕭 = L_{accept}$

EX 6

1.

Donnée : $⟨M⟩$

Question: $M$ s’arrête-t-elle sur $𝜀$ ?

On réduit le problème de l’arrêt (plus facile) au problème de l’arrêt sur $𝜀$ (plus difficile).

$f : ⟨M,w⟩ \mapsto ⟨M_w⟩$ où, pour tout $w$, $M_w$ efface l’entrée, écrit $w$, et exécute $M$.

f(⟨M,w⟩) ∈ Arret_𝜀 ⟺ M_w \text{ s'arrête sur } 𝜀 \\ ⟺ M \text{ s'arrête sur } 𝜔 ⟺ ⟨M,w⟩ ∈ Arret

2.

Donnée : $⟨M⟩$

Question: $M$ s’arrête-t-elle sur au moins une donnée ?

$P_{arret} ≼ P_{arret_sur_une_donnee}$

$f : ⟨M,w⟩ \mapsto ⟨M’⟩$ où

  • $M’(𝜀)$ simule $M$ sur $w$
  • $M’(w) = \bot$

$⟨M’⟩$ est une instance acceptante de $P_{arret_sur_une_donnee}$ ssi $M’$ s’arrête sur $𝜀$ ssi $M$ s’arrête sur $w$.

3.

Donnée : $⟨M⟩, ⟨M’⟩$

Question: $L(M) = L(M’)$ ?

$P_{arret} ≼ P_{langages_égaux}$

$f : ⟨M, w⟩ \mapsto ⟨M’_w⟩, ⟨M’‘_w⟩$ où

  • $M’_w$ n’accepte que $w$, rejette tout le reste (machine fixée)
  • $M’‘_w$ simule $M$ sur $w$ si l’entrée est $w$, reject sinon
\{w\} = L(M'_w) = L(M''_w) ⟺ M''_w \text{ accepte } w ⟺ M \text{ accepte } w

Leave a Comment