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
Leave a comment