TD4 : Théorème de Rice, Réductions, Machines de Minsky
EX 1
P1
- Data : 3 TM $M_1, M_2, M_3$
- Question : $L(M_1)∪L(M_2) = L(M_3)$
Th de Rice : toute propriété non triviale des langages r.e est indécidable.
- propriété des langages r.e : si la propriété est “la machine a deux états”, ça ne marche pas (on s’intéresse au langage reconnu, et pas à l’implémentation de la machine).
- Si $P$ est tq $∀M_1, M_2$, si $P(⟨M_1⟩) ∧ L(M_1) = L(M_2)$ alors $P(M_2)$
- $P$ non triviale ⟺ $∃M_1; P(⟨M_1⟩)=true ∧ ∃M_2; P(⟨M_2⟩)=false$
Th de Rice, avec
- $P$ portant sur un seul langage.
M1 :
$P’_1$ :
Data : $⟨M_1⟩$
Question : $L(M_1)∪∅ = ∅$
Par Rice, $P’_1$ est indécidable.
\[f(⟨M_1⟩) ⟹ ⟨M_1⟩,⟨M_∅⟩,⟨M_∅⟩\]Donc $P’_1 ≼ P_1$
Donc $P_1$ est indécidable.
M2 :
On réduit le problème “accept” :
$f : ⟨M⟩, w \mapsto ⟨M_1⟩, ⟨M_2⟩, ⟨M_3⟩$, avec :
- $M_1$ :
- simule $M$ sur $w$ si $x=w$
- reject sinon
- $M_2$ reject tout le temps
- $M_3$ :
- accept si $x=w$
- reject sinon
$L(M_2) = ∅$
\[L(M_1)∪L(M_2) = L(M_3) ⟺ L(M_1) = \{w\} \\ ⟺ M \text{ accepte } w\]2)
Data : TM $M$, word $w$, non negative integer $n$
Question : $M$ accepts $w$ after at most $n$ computation steps.
Décidable : on simule $M$ sur $w$ avec un compteur.
3)
Data : $M$
Question : $∃M’; L(M’) = L(M)^c$
Indécidable : la propriété est : “$L(M)^c$ est r.e” + utiliser la CNS d’une feuille de TD précédente.
(OU : “$L(M)$ est récursif” : non trivial)
4)
Data : Unkown Data
Question : $∃ M$ on $𝛴={0,1,$,B}$ with $8$ states.
Décidable (cf. Wolfram TM)
OU : cf. Dieu existe (propriété soit tout le temps vraie, soit tout le temps fausse, mais comme elle est constante : calculable)
4’)
Data : No Data
Question : $∃ M$ on $𝛴={0,1,$,B}$ with $8$ states.
Décidable.
$P$ est décidable si ${x ∈ data \vert P(x)} = {x ∈ data \vert M(x) \text{ accept}}$ et $∀x∈data, M(x)$ termine.
(ici : $∅$)
5)
Data : $M$, a word $w$
Question : the computation of $M$ on $w$ goes inf. often through $q_0$
Réduction du pb de l’acceptance.
$f: M, w \mapsto M,w$
- on crée une machine $M’$ qui :
- écrit $$w$ est simule $M$ dessus.
- si $M$ reject : $M’$ reject
- si $M$ boucle sur $w$ : $M’$ boucle en n’utilisant pas les états de $M$ ⟶ ne passe par $q_0$ une inf. de fois
- si $M$ accepte $w$ : $M’$ boucle une infinité de fois sur $q_0$
- écrit $$w$ est simule $M$ dessus.
6)
Données : $M_1, M_2$ qui s’arrêtent sur toute entrée
Question : $∀x, M_2(M_1(x))=x$
On réduit le problème du non-arrêt à ce problème $P_6$
$f: M, w \mapsto M_1, Id$
où : $M_1$, prend en entrée $x$ et
- simule $\vert x\vert $ étapes de $M$ sur $w$
- si $M$ s’arrête, on renvoie $x.a$ (où $a$ est une autre lettre)
- si $M$ ne s’arrête pas en moins de $\vert x\vert $ étapes, on renvoie $x$
donc
\[∀x, Id(M_1(x)) = x ⟺ M(w)=\bot\]NB : donc ce problème est même pire que non récursif/décidable : il n’est pas r.én.
7)
Data : 2 lineary bounded MT $M_1, M_2$
Question : $L(M_1) = L(M_2)$
On réduit le problème du non-arrêt à $P_7$.
$f: M, w \mapsto M’, M_∅$ où
$M’$ pour une entrée $x$ :
- Simule $M$ sur $w$
- Si $M$ dépasse $\vert x\vert $ : s’arrête en en refusant
- Sinon, si $M$ s’arrête sans dépasser : accepte
TD 4
1)
On a $k+2$ états : $q_0, ⋯, q_{k-1}, q^r_1, ⋯, q^r_{k-1}$ : on commence dans l’état $q_0$
- Tant que la première pile est non vide :
- Si on est dans l’état $q_i$, pour $i<k-1$ : c’est que la deuxième pile contient un nombre congru à $i \mod k$ : on dépile un élément dans $P_1$, puis on passe à l’état $q_{i+1 \mod k}$
- Si on est dans l’état $q_{k-1}$, pour $i<k-1$ : on ajoute $1$ élément à $P2$, puis on procède de même que dans le cas précédent.
- Si $P1$ est vide :
- Si on est dans l’état $q_i$ ($i>0$), on passe dans l’état $q^r_i$
- Si on est dans $q^r_i$, on ajoute $1$ à $P1$ et on passe à $q^r_{i-1}$
- Si on est dans $q^r_0$, on accepte.
2)
Tentative infructueuse :
$L = f(𝛴^\ast)$, pour une fonction $f$ calculable.
On pose $g ≝ c_k \circ f$ : $g$ est calculable.
Pour tout entier
\[w = w_r w_{r-1} ⋯ w_0 \\ n_w ≝ \overline{w_r w_{r-1} ⋯ w_0} \\ = \sum_i \overline{w_i} (k+1)^i\]on procède en deux étapes :
On détermine si $w∈L$ ou non, en utilisant le fait que $g(𝛴^\ast)$ est réc. én.
Comme $g(𝛴^\ast)$ est récursivement énumérable, il existe une machine à deux rubans énumérant les mots de $g(𝛴^\ast)$ sur le deuxième ruban (en exécutant $n$ étapes de $M_g$ sur les $n$ premières lettres), donc une machine à 4 rubans déterminant si un mot $w’$ appartient à un $g(𝛴^\ast)$ ou non :
- le ruban d’entrée prend le mot $w’$
- les rubans 2 et 3 simulent $M_g$
- le ruban 4 sert à comparer $w’$ aux mots listés sur le ruban 3.
On se sert des registres comme des rubans, tout les représentations des mots étant en unaire.
PAS BON, car on ne peut pas réduire une MT à un machine de Minsky.
Solution :
On note avec un tilde les mots miroirs
| étape | registre 1 : $r_1$ | registre 2 : $r_2$ | registre 3 : $r_3$ | registre 4 : $r_4$ |
|---|---|---|---|---|
| écriture | $c_k(w_1)$ | $\widetilde{c_k(w_2)}$ | ||
| $c_k(w_2) \overset{DE}{=} (k+1)q + r$ | $c_k(w_1)$ | $q$ | $r$ | |
| en utilisant $r_4$ | $c_k(w_1)$ | $(k+1)q + r = r_2$ | $r = \overline{a_r}$ | |
| déplacement si $(q_0,a_r)\vdash (q_1,a_p, ←)$ : $c_k(w_1) \overset{DE}{=} (k+1)q’ + r’$ | $q’$ | $(k+1)r_2+r’$ | $r= \overline{a_r}$ | (utilisé pour $r_2$) |
3.
Montrons qu’une machine de Minsky à 4 rubans peut-être simulée par une machine à 2 rubans.
- Dans le registre 1 est stockée la valeur $2^{n_1} \cdot 3^{n_2} \cdot 5^{n_3} \cdot 7^{n_4}$
L’idée est de pouvoir récupérer la valuation $p$-adique d’un entier avec le registre 2, et en particulier :
- test à zéro : tester si $v_p(r_1)=0$ : faisant la division euclidienne par $p$, puis en vérifiant que le reste est non nul
- incrémenter de 1 $v_p(r_1)$ : en multipliant par $p$
- décrémenter $v_p(r_1)$ : en divisant par $p$
Le tout en utilisant le registre 2, en retenant l’information du reste dans les états.
Ex :
\[(-1, 1, 0, 0) \mapsto \frac w 2 × 3\]NB : s’il n’y a qu’un registre : c’est un automate à piles : strictement moins expressif (ex : “$L=∅$” est décidable pour les automates à pile, pas pour les MT/Machines de Minsky).
4.
$𝒫$
- Donnée : $ℳ$ machine de Minsky à deux registres, $n$ un entier.
- Problème : $ℳ$ accepte un entier ?
On considère
$\overline{𝒫}$
- Donnée : $ℳ$ machine de Minsky à deux registres, $n$ un entier.
- Problème : $ℳ$ n’accepte aucun entier ?
Déjà, remarquons que le problème du non-arrêt est indécidable pour les machines de Minsky (même argument diagonal que pour les machines de Turing), On réduit ce problème de l’arrêt à $𝒫$.
2.
Problèmes indécidables usuellement réduits :
- non-arrêt pour une MT
- non-arrêt pour une Minsky
- PCP
- Pavage
Ici : réduction du problème PCP modifié.
$𝒫$
-
Donnée : Un ensemble fini de fonctions affines de $ℝ^2$ dans $ℝ^2$, et deux vecteurs $A, B ∈ ℚ^2$.
-
Question : Existe-t-il une trajectoire de $A$ passant par $B$ ?
Soit $(u_i,v_i)_{1≤i≤n}$ une instance de PCP modifié.
\[f_i(X) = \begin{pmatrix} (|𝛴|+1)^{|u_i|} & 0 \\ 0 & (|𝛴|+1)^{|v_i|} \end{pmatrix} X + \begin{pmatrix} u_i \\ v_i \end{pmatrix}\] \[f_{sol}(X) = \begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix} X\] \[𝒮 = \Big\{f_i | 1≤i≤n \Big\}∪\{f_{sol}\}\]- \[A ≝ \begin{pmatrix} u_i \\ v_i \end{pmatrix}\]
- \[B ≝ \begin{pmatrix} 0 \\ 0 \end{pmatrix}\]
Alors :
⟹ :
Si $i_1, ⋯, i_k$ est solution de PCP, alors
\[f_{sol}\bigg(\prod\limits_{j=1}^k f_{i_j} \big(\begin{pmatrix} u_i \\ v_i \end{pmatrix}\big)\bigg) = \begin{pmatrix} 0 \\ 0 \end{pmatrix}\]⟸ :
Soit $(f_{i_j})_{1≤j≤k} ∈ S^k$ tq \(\prod\limits_{j=1}^k f_{i_j} \big(A\big) = B\)
Soit $i_l$ la première occurrence de $f_{sol}$.
-
Cas 1 : Si \(\prod\limits_{j=1}^{l-1} f_{i_j} \big(A\big) = \begin{pmatrix} w \\ w \end{pmatrix}\)
Alors on a une solution de PCP modifié
-
Cas 2 : Si \(\prod\limits_{j=1}^{l-1} f_{i_j} \big(A\big) = \begin{pmatrix} w \\ w' \end{pmatrix}\)
(avec $w≠w’$), alors :
- \(\prod\limits_{j=1}^{l} f_{i_j} \big(A\big) = \begin{pmatrix} w \\ w' \end{pmatrix}\) est dans l’ensemble des vecteurs dont les deux composantes sont de signe strictement opposé, lequel est stable par les éléments de $𝒮$ : donc, par une récurrence immédiate, $B$ appartient à cet ensemble, ce qui n’est pas. Absurde.
Leave a comment