Cours 3 : Machine Universelle, Problème de l’arrêt, Théorème de Rice, Réduction

Machine Universelle

$M_U$ : simule une MT.

$⟨M⟩$ : code de $M$ (en base 2)

On code en base 2 les symboles de $𝛴$ :

  • $⟨𝛴⟩ = \underbrace{0 ⋯ 0}_{\lfloor \log_2 \vert 𝛴\vert \rfloor + 1}$
  • $B : 0^1$, $$ : 0^10$
  • $c : 𝛴 ⟶ {0,1}^{\vert 𝛴\vert }$

Et :

  • $⟨Q⟩ = \underbrace{0 ⋯ 0}_{\lfloor \log_2 \vert Q\vert + 2 \rfloor + 1}$
  • $B : 0^1$, $$ : 0^10$
  • $c : Q ⟶ {0,1}^{\vert Q\vert }$

$c(q_0) = 1, c(accept)=10, c(reject)=11$

$⟨M⟩_{MT} = ⟨Q⟩ d_𝛴 ⟨𝛴⟩ d_𝛿 ⟨𝛿⟩$

Codage de la liste $𝛿$ :

  • $⟨𝜀⟩_{MT} = f_𝛿$

  • $⟨(q,a,q’,a’,d), ⟩ = c(q), c(q’) \mapsto c(q’), c(a’), d; ⟨⟩$

\[𝛴_U = \{0,1,d_𝛴, d_𝛿, f_𝛿, ",", \mapsto, ⟶, ⟵, \downarrow, ";", \$, B\}\]

Théorème : il existe une machine $M_U$ tq :

\[L(M_U) = \{⟨M;w⟩ \vert w ∈ L(M)\}\]

$M_U$ a trois rubans :

  1. 1er ruban : $$⟨M;w⟩$
  2. 2e ruban : $c(𝛾)$ (où $𝛾$ est une config de $M$)
  3. 3e ruban : ?

$c((q, w_1,w_2)) = ⟨w_1⟩, c(q), ⟨w_2⟩$

Opérations :

1) $M_U$ copie $c(𝛾)$ sur le 2e ruban :

$000⋯0 d_𝛴 0⋯0 d_𝛿 ⋯ f_𝛿 ⟨w⟩$
$, 000⋯1, ⟨w⟩ B$

2) Cherche la transition applicable dans $d_𝛿 ⋯ f_𝛿$, sur le premier ruban, en comparant avec le \(c(q), c(\underbrace{a}_{\text{1ere lettre de $⟨w⟩$}})\) courant (sur le deuxième ruban).

3) Appliquer la transition :

  • Récupérer le déplacement dans 1 état.
  • Transition droite :

| Ruban 2 | $c(q), c(a), c(b), ⋯$ ⟶ $c(a’), c(q’), c(b), ⋯$ | |-|-|

On utilise le fait que $longueur(c(q), c(a)) = longueur(c(q’), c(a’))$

4) Transition gauche : idem, $c(b), c(q), c(a), ⋯$ ⟶ $c(q’), c(b), c(a’), ⋯$

Le troisième ruban sert à :

  • sauvegarder $c(q)$ qd transition droite
  • sauvegarder $c(b)$ qd transition gauche

Corollaire : \(L_U = \{⟨M,w⟩ \vert w∈L(M) \}\) est r.é

Th : $L_u^c$ n’est pas r.é

Dém :

Argument diagnonal :

ABS : Si $L_u^c = {⟨M,w⟩ \vert w \not∈L(M) }$ est accepté par $M_u^c$

On observe quand $w = ⟨M⟩$ : \(\{⟨M,⟨M⟩⟩ \vert ⟨M⟩ \not∈L(M) \}\)

\[D≝ \{⟨M⟩ \vert ⟨M⟩ \not∈ L(M)\}\]

$M_D : ⟨M⟩ \mapsto ⟨M,⟨M⟩⟩$ : PUIS , simule $M_u^c$.

\[⟨M⟩ ∈ L(M_D) ⟺ ⟨M⟩ \not∈ L(M)\] \[⟨M_D⟩ ∈ D=L(M_D) ⟺ ⟨M_D⟩ \not∈ L(M_D) =D\]

$L_{arrêt} = {⟨M,w⟩ \vert M \text{ s’arrête sur } w}$

Th : $L_{arrêt}$ est r.é/décidable, pas co-r.é

$M_{arrêt}$ simule $M_U$ en remplaçant “reject” par “accept” dans $M$ (donc ne reject jamais).

Si $L_{arrêt}^c$ était r.é : \(L(M_{arrêt}^c) = L_{arrêt}^c = \{⟨M,w⟩ \vert M(w) = \bot \}\)

\[D ≝ \{⟨M⟩ \vert M(⟨M⟩) = \bot \}\]

\(M_D : ⟨M⟩ \mapsto ⟨M, ⟨M⟩⟩\) PUIS : simule $M_{arrêt}^c$

$L(M_D) = D$

\[⟨M_D⟩ ∈ D ⟺ M_D(⟨M_D⟩) = \bot ⟹ ⟨M_D⟩ \not∈ L(M_D)\]

On a la réciproque, car on peut supposer sans perte de généralité que $M_{arrêt}^c$ ne rejette jamais.

Réductions

$P$ :

  • Donnée : $D ⊆ 𝛴^*$
  • Question : $Q$ dans l’ens. des données

Ex :

$P$ :

  • Donnée : $⟨M,w⟩$
  • Question : $M$ s’arrête sur $w$.

$P_1$ : on sait qu’il est indécidable

Mq $P_2$ est indécidable en réduisant $P_1$ à $P_2$.

$f$ calculable tq $f(d_1) ∈ D_2$, $D_1 ⟶ D_2$

et $d_1 ∈ Q_1$ ssi $f(d_1) ∈ Q_2$

ABS :

Si on savait résoudre $P_2$ : $f(d_1) ∈ Q_2$ est décidable

on sait alors résoudre $d_1 ∈ Q_1$

Ex de réduction :

  • Donnée : $⟨M⟩$ code de MT
  • Question : $M(𝜀) \neq \bot$ ?

Est indécidable.

Réduction du problème de l’arrêt :

  • Donnée : $⟨M_1, w_1⟩$
  • Q : $M_1$ s’arrête sur $w_1$ ?

$M_2$ écrit $w_1$ et simule $M_1$

$f : ⟨M, w_1⟩ \mapsto ⟨M_2⟩$

$M_1$ s’arrête sur $w_1$ ssi $M_2$ s’arrête sur $𝜀$.

$P$

  • Donnée : $⟨M⟩$ code de MT
  • Question : $M$ s’arrête sur toute donnée ?

n’est pas réc. én. et pas co-réc.

⟶ Réduction du complémentaire du pb de l’arrêt :

1) $P^c$ pas réc.én. :

  • Donnée : $⟨M’⟩$ code de MT
  • Question : $∃x$ tq $M’$ ne s’arrête pas sur $x$

$⟨M,w⟩ \mapsto ⟨M’⟩$

$M’$ : teste si son entrée est $w$ :

M1 :

  • si c’est w : simuler $M$ sur $w$
  • sinon, s’arrête

M2:

  • pour toute entrée : simuler $M$ sur $w$

$M$ ne s’arrête pas sur $w$ SSI $∃x$ tq $M’$ ne s’arrête pas sur $x$

1) $P$ :

$⟨M,w⟩ \mapsto ⟨M’⟩$

$M’$ : entrée $x$

  • Simule $\vert x\vert $ étapes de $M$ sur $w$ :
    • Si $M$ s’est arrêtée en moins de $\vert x\vert $ étapes, $M’$ boucle
    • Sinon $M’$ s’arrête

Si $M(w)=\bot$, alors $∀x$, $M’$ s’arrête sur $x$

Si $M(w)\neq \bot$, alors $∃x$ tq $M’$ ne s’arrête pas $x$

$M’$ s’arrête sur tout $x$ SSI $M(w)=\bot$

Th de Rice : Toute propriété non triviale des langages r.én. est indécidable.

  • Donnée : $⟨M⟩$
  • Question : $𝒫$, ensemble de MT clos par relation d’équivalence (cf. suite).

tq :

  • $L(M) = L(M’) ⟹ (⟨M⟩ ∈ 𝒫 ⟺ ⟨M’⟩ ∈ 𝒫)$
  • $𝒫 \neq ∅ ∩ \overline{𝒫} \neq ∅$

Dém :

NB : être indécidable = être non récursif ⟺ $𝒫$ OU $\overline{𝒫}$ est indécidable.

Sans perte de généralité (quitte à considérer $\overline{𝒫}$) : $∅ \not ∈ 𝒫$

$𝒫$ non triviale : $𝒫 \neq ∅$

Soit $L_0 ∈ 𝒫$ et $L(M_0) = L_0$

Réduction du pb de l’arrêt :

  • Donnée : $⟨M, w⟩$
  • Question : $M$ s’arrête sur $w$

réduit à :

  • Donnée : $⟨M’⟩$
  • Question : $M’∈𝒫$

$⟨M,w⟩ \mapsto ⟨M’⟩$

$M’$ sur $x$ :

  • Simule $M$ sur $w$
  • Si $M$ s’arrête sur $w$, simule $M_0$ sur $x$

Alors :

\[L(M') = \begin{cases} ∅ \text{ si } M(w) = \bot \\ L_0 \text{ sinon } \end{cases}\]

$L(M’) ∈ 𝒫 ⟺ M(w) \neq \bot$

Leave a comment