DM1 : Virus

Calculabilité DM 1 : Virus

On notera $C$ l’ensemble des codes de machines de Turing (abrégé MT).

EX 1

Soit

\(f : \begin{cases} C ⟶ C \\ ⟨M⟩ \mapsto ⟨M'⟩, \text{ où $M$ est une MT} \end{cases}\) calculable.

Montrons qu’il existe une machine $M$ telle que, sur toute donnée $x$ : \(M_U (f(⟨M⟩),⟨x⟩) = ⟨ M(x)⟩\)

On pose : \(g \overset{\text{déf}}{:} \begin{cases} C ⟶ C \\ ⟨M⟩ \mapsto ⟨M(M)⟩, \text{ où } M(M) ≝ x \mapsto \begin{cases} M(⟨M⟩)(x) \text{ si } M(⟨M⟩) \text{ est le code d'une MT} \\ \bot \text{ sinon. } \end{cases}\end{cases}\)

Attenion : il faut montrer que $g$ est calculable ! $g(⟨M⟩)$ pourrait très bien ne pas terminer sur un entrée $⟨M⟩$. Exhiber explicitement $⟨M⟩$.

Alors en notant $M$ la machine $g(⟨M_{f\circ g}⟩)$ :

  • $f(⟨M⟩) = f(⟨g(⟨M_{f\circ g}⟩)⟩) = (f \circ g)(⟨M_{f\circ g}⟩)$, d’où, pour toute donnée $x$, \(M_U (f(⟨M⟩),⟨x⟩) = M_{f\circ g}(⟨ M_{f\circ g}⟩)(x)\) car $f\circ g$ est calculable, en tant que composée de fonctions calculables, et

  • $g(⟨M_{f\circ g}⟩) = M_{f\circ g}(⟨M_{f\circ g}⟩)$, et, pour toute donnée $x$ : \(g(⟨M_{f\circ g}⟩)(x) = M_{f\circ g}(⟨M_{f\circ g}⟩)(x)\) car $M_{f\circ g}(⟨M_{f\circ g}⟩)∈C$, puisque $f, g ∈ C^C$.

Donc $M ≝ g(⟨M_{f\circ g}⟩)$ est est telle que, pour toute donnée $x$ : \(M_U (f(⟨M⟩),⟨x⟩) = ⟨ M(x)⟩\)

EX 2

1

On note $f$ la fonction : \(f : C⟶C, ⟨M⟩ \mapsto ⟨M'_M⟩\) où $M’_M$ est la MT qui, pour tout entrée $x$ (sur le premier ruban), renvoie :

  • $⟨M⟩$ (sur le deuxième ruban) dans un état $q_{emit}$ si $x=𝜀$
  • $\bot$ sinon

La fonction $f$ est calculée par la machine qui, à toute entrée $x$, associe :

  • Le code de $M_x$ si $x ∈ C$
  • $\bot$ sinon

Donc par l’exercice 1, il existe une machine $ℳ$ telle que, pour toute donnée $x$ : \(M_U (⟨M'_ℳ⟩,⟨x⟩) = ⟨ ℳ(x)⟩\)

Et en particulier, pour $x=𝜀$, il vient que :

$ℳ$ est un virus.

2

On note $M_d$ la machine :

\[M_d : C∋⟨M⟩ \mapsto \begin{cases} accept \text{ si $M$ est un virus} \\ reject \text{ ou } \bot \text{ sinon} \end{cases}\]

$M_d$ prend en entrée une donnée $x$, et :

  • si $x ∈ C$ : $M_d$ simule $x$ sur $𝜀$ (en utilisant le deuxième ruban, qui est initialisé à $$𝜀$), puis :
    • si le calcul de $x$ sur $𝜀$ passe par une configuration $(q_{emit},(w_1, w_2),(𝜀, $⟨M⟩))$ : $M_d$ s’arrête sur $accept$.
    • sinon, $M_d$ s’arrête sur $reject$ (si le calcul termine) ou renvoie $\bot$.
  • sinon : $M_d$ s’arrête sur $reject$

Il vient alors que :

Pour toute machine $M$, $M_d$ accepte $⟨M⟩$ si, et seulement si, $M$ est un virus.

Donc l’ensemble des codes de virus \(V ≝ \{⟨M⟩ ∈ C \vert \text{le calcul de $M(𝜀)$ passe par $(q_{emit},(w_1, w_2),(𝜀, \$⟨M⟩))$}\}\) est récursivement énumérable.

3

Montrons que $V$ n’est pas récursif, i.e, d’après l’exercice 2 - question 2, que $V$ n’est pas co-récursivement énumérable.

Problème $𝒫$ :

  • Donnée : $⟨M’⟩ ∈ C$
  • Question : $⟨M’⟩∈ \overline{V}$ ?

On réduit le problème du non-arrêt $\overline{𝒫_{arrêt}}$ à $𝒫$.

Soit $g$ la fonction calculable qui prend en entrée un couple $(⟨M⟩,⟨w⟩) ∈ C \times {données}$ et qui retourne $⟨ℳ_{M,w}⟩∈C$, où :

$ℳ_{M,w}$ prend en entrée une donnée $x$ et :

  • Si $x=𝜀$ :
    • simule $M$ sur $w$, puis :
      • si $M(w)\neq \bot$ : écrit $⟨ℳ_{M,w}⟩$ sur le deuxième ruban, dans un état $q_{emit} ∉ Q_{M}$.
      • ne termine pas, sinon
  • rejette sinon

NB :

Une telle machine $ℳ_{M,w}$ existe, car en considérant la fonction calculable : \(f_{M,w} : C⟶C, ⟨M'⟩ \mapsto ⟨M''_{M',M,w}⟩\) où $M’‘_{M’,M,w}$ est la MT qui, pour tout entrée $x$ (sur le premier ruban) :

  • Si $x=𝜀$ :
    • simule $M$ sur $w$, puis :
      • si $M(w)\neq \bot$ : écrit $⟨M’⟩$ sur le deuxième ruban, dans un état $q_{emit} ∉ Q_{M}$.
      • ne termine pas, sinon
  • rejette sinon

$f_{M,w}$ admet un “point fixe” (au sens de l’exercice 1), qu’on note $ℳ_{M,w}$.

Comme \(∀M, M(w) \neq \bot ⟺ ℳ_{M,w} ∈ V\)

c’est-à-dire :

\[∀M, M(w) = \bot ⟺ ℳ_{M,w} ∈ \overline{V}\]

alors on a bien \(\overline{𝒫_{arrêt}} ≼ 𝒫\)

et

$\overline{V}$ n’est pas récursivement énumérable, d’où $V$ n’est pas récursif.

EX 3

1) On pose $V_0 ≝ V$, et pour tout $n∈ℕ$ : $M ∈ V_{n+1}$ si, et seulement si :

  • $M∈V_n$

ou

  • $M(𝜀)$ passe par une configuration dans laquelle le ruban de sortie contient le code d’une machine de $V_n$.

Alors il vient que $𝒱 = \bigcup\limits_{n∈ℕ} V_n$

Par récurrence sur $n∈ℕ$ : “$V_n$ est récursivement énumérable”

  • Pour $n=0$ : prouvé dans l’exercice 2
  • Pour $n>0$ :

On note $M_{d_n}$ la machine :

\[M_{d_n} : C∋⟨M⟩ \mapsto \begin{cases} accept \text{ si $M$ est un infectée par un virus} \\ reject \text{ ou } \bot \text{ sinon} \end{cases}\]

$M_{d_n}$ prend en entrée une donnée $x$, et :

  • si $x ∈ C$ : $M_{d_n}$ simule $x$ sur $𝜀$ sur le premier ruban, puis, à chaque configuration $(q_{emit},(w_1, w_2),(𝜀, $⟨M’⟩))$ du calcul $x(𝜀)$ : $M_{d_{n-1}}$ est simulée sur $M’$, sur le deuxième ruban.
    • si $M_{d_{n-1}}$ accepte $M’$ : $M_{d_n}$ accepte $x$
    • sinon : $M_{d_n}$ rejette ou ne termine pas (selon que $M_{d_{n-1}}(M’)$ termine ou pas).
  • sinon : $M_{d_n}$ rejette.

Alors, par hypothèse de récurrence : pour toute machine $M$, $M_{d_n}$ accepte $⟨M⟩$ si, et seulement si, $M ∈ V_n$.

On conclut donc que $𝒱 = \bigcup\limits_{n∈ℕ} V_n$ est récursivement énumérable.

Attention : une union infinie de langages réc. én. n’est pas forcément réc. én.

Ex :

\(Arret = \bigcup_{n∈ℕ} Arret_n\) où

\[Arret_n ≝ \{⟨M,w⟩ | M \text{ ne termine pas sur } w ∧ |⟨M,w⟩|≤n \}\]

2)

On a montré que : $∀n≥0, V_n$ est récursivement énumérable, donc en particulier $𝒱\backslash V = \bigcup\limits_{n>0} V_n$ est récursivement énumérable (les $V_i$ croissent).

Or : \(\underbrace{\overline{V}}_{\text{non réc. énumérable par II.3)}} = \underbrace{(𝒱\backslash V)}_{\text{réc. énumérable}} \sqcup \overline{𝒱}\)

Donc comme les langages récursivement énumérables sont stables par union, il vient nécessairement que :

$\overline{𝒱}$ n’est pas récursivement énumérable, d’où 𝒱 n’est pas récursif.

EX 4

On réutilise les notations précédentes, et on utilise un astérisque pour les ensembles définis avec la nouvelle définition de virus.

1)

Montrons que $\overline{𝒱^\ast}$ n’est pas récursivement énumérable.

$\overline{V_0^\ast}$ est l’ensemble des codes de MT infectées par une machine $M$ comportant un ruban de sortie tel qu’il existe une donnée $x_M$ telle que le calcul de $M$ ne passe par une configuration dans laquelle le ruban de sortie contient $⟨M⟩$ : donc $\overline{V_0^\ast} \supset \overline{V_0}$, et par une récurrence immédiate : \(∀ n ∈ ℕ, \overline{V_n^\ast} \supset \overline{V_n}\) d’où \(\overline{𝒱^\ast} \supset \overline{𝒱}\)

Donc on réduit aisément le problème de la non semi-décidabilité de $\overline{𝒱}$ à $\overline{𝒱^\ast}$, et

$𝒱^\ast$ n’est pas co-récursivement énumérable

2)

De même, comme les $𝒱_i’$ croissent :

Problème $𝒫’$ $\succcurlyeq$ Problème $𝒫_0’$
Donnée : $⟨M’⟩ ∈ C$   Donnée : $⟨M’⟩ ∈ C$
Question : $⟨M’⟩∈ 𝒱’ = \bigcup\limits_{n ∈ ℕ} V’_n$ ?   Question : $⟨M’⟩∈ V’_0 = V’$ ?

On réduit le problème du non-arrêt à $𝒫_0’$.

Soit $g$ la fonction calculable \(g : \begin{cases} C \times \{données\} ⟶ V' \\ ⟨M⟩,⟨w⟩ \mapsto ⟨ℳ_{M,w}⟩ \end{cases}\)

où $ℳ_{M,w}$ prend en entrée une donnée $x$ et simule $M$ sur $w$ pendant $\vert x\vert $ étapes sur le premier ruban, puis :

  • si, avant la $\vert x\vert $-ième étape, $M$ s’arrête sur $w$ : $ℳ_{M,w}$ rejette.
  • sinon, si au bout de la $\vert x\vert $-ième étape, $M$ ne s’est toujours pas arrêtée sur $w$ : $ℳ_{M,w}$ écrit $⟨ℳ_{M,w}⟩$ sur le deuxième ruban, dans un état $q_{emit} ∉ Q_{M}$.

NB :

Une telle machine $ℳ_{M,w}$ existe, car en considérant la fonction calculable : \(f_{M,w} : C⟶C, ⟨M'⟩ \mapsto ⟨M''_{M',M,w}⟩\) où $M’‘_{M’,M,w}$ est la MT qui, pour tout entrée $x$ (sur le premier ruban) :

  • si, avant la $\vert x\vert $-ième étape, $M$ s’arrête sur $w$ : rejette.
  • sinon, si au bout de la $\vert x\vert $-ième étape, $M$ ne s’est toujours pas arrêtée sur $w$ : écrit $⟨M’⟩$ sur le deuxième ruban, dans un état $q_{emit} ∉ Q_{M}$.

$f_{M,w}$ admet un “point fixe” (au sens de l’exercice 1), qu’on note $ℳ_{M,w}$.

Il vient donc que :

  • pour toute donnée $x$, $ℳ_{M,w}$ passe par une configuration dans laquelle le ruban de sortie contient $⟨ℳ_{M,w}⟩$

si, et seulement si

  • pour toute donnée $x$, $M$ ne s’arrête pas sur $w$ en moins de $\vert x\vert $ étapes

si, et seulement si

  • $M$ ne s’arrête pas sur $w$

Donc \(\overline{𝒫_{arrêt}} ≼ 𝒫_0' ≼ 𝒫'\)

et

$𝒱’$ n’est pas récursivement énumérable.

Attention : \(V⊆V' ∧ V \text{ non réc.én } \lnot ⟹ V' \text{ non réc.én}\)

Contre-ex :

\[Arret ⊆ 𝛴^\ast\]

Leave a comment