TD2 : Ensembles récursifs/récursivement énumérables

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

TD 2

EX 1

On écrit le mot à l’envers sur le deuxième ruban, puis on compare lettre à lettre verticalement.

• Étape 1 : Aller jusqu’au bout du mot sur le premier ruban, à l’indice $k$.
• Étape 2 : écrire un caractère spécial en position $k$ sur le deuxième
• Étape 3 : revenir au début sur le premier ruban, copier le mot sur le deuxième à l’envers

• Étape 4 : comparer les deux.

  • $q_1$ : écrit le mot sur le deuxième ruban
  • $q_2$ : revient au début sur le premier ruban
  • $q_3$ : compare les deux mots lettre à lettre

$∀ a \neq b ∈ 𝛴$ :

	$(a,b)$	$(a,a)$	$(B,_)$	$($,_)$
$q_1$	$q_1(a,a)→→$	$q_1(a,a)→→$	$q_2(B,B)←←$
$q_2$	$q_2(a,b)←↓$	$q_1(a,a)←↓$		$q_2($,_)→→$
$q_1$	reject	$q_1(a,a)→←$	accept

EX 2

• Intersection : les deux MT sont sur un ruban chacune ⟶ le dernier état est le $∧$ des deux états finaux des deux MT.
• Union : idem, avec $∨$.
• Complémentaire : idem, avec $\lnot$ (“accept” devient “reject” et réciproquement).

EX 3

On veut savoir si $w ∈ f(L)$ : Sur le ruban, on note $w$, un caractère spécial, et tous les éléments de $L$ juxtaposés par des caractères spéciaux. Puis : on calcule $f(w’)$, pour tous les $w’$ écrits sur le ruban (sauf le premier, qui est $w$), et on la compare à $w$ (si $w ∈L$ : ça termine, sinon : ça ne termine pas).

Soit $M_f$ calculant $f$.

Mq \(L ≝ \{f(w) \vert w ∈ 𝛴^* \}\) est récursivement énumérable.

\[M_L :\] \[\begin{align*} \$x\#w'\#𝜀 \\ &\vdash^* \$x\#w'\#𝜀 \\ &\vdash^* \$x\#w'\#𝜀 \\ &\vdash^* \begin{cases} accept \, \, \, \, \text{ si } f(w') = x \\ \$x\#next(w')\#𝜀 \, \, \, \, \text{ sinon } \end{cases} \end{align*}\]

EX 4

On exécute $M_1, M_2$ sur $w$ sur deux bandes différentes.

Ne marche pas pour le complémentaire, car on ne peut pas détecter les mots tels que la machine ne termine pas pour les accepter dans $\lnot M$.

EX 5

On aimerait bien faire quelque chose de similaire à l’exo 3, tester tous les mots successifs du langage sur la première bande, puis le placer sur la deuxième bande ⟶ MAIS : ne marche pas, car on peut rester indéfiniment sur un mot n’appartenant pas au langage.

Le langage $L$ est récursivement én. ssi \(∃ M \text{ à deux rubans }; q_e ∈ Q_M ∧ \\ q_0,(𝜀, \$),(𝜀,\$)\vdash_M^* q_e, (𝜀,\$w'), (𝜀, \$w) ⟺ w ∈ L\)

• $⟹$ : On définit $M$ de la manière suivante :

À la $k$-ième grande étape, on a :

• Sur le premier ruban : les $k$ premiers mots de l’alphabet auxquels on appliqué $k$ étapes de la machine $M_L$ (on les stocke sous la forme $q_1\vert t_1\vert w_1#q_2\vert t_2\vert w_2⋯ #q_k\vert t_k\vert w_k)$
• Sur le deuxième ruban : on écrit tour à tour les $k$ mots du premier ruban en faisant progresser l’exécution de $M_L$ de 1 étape. Si $M_L$ accepte le mot, on l’écrit tout seul (sans $q_i\vert t_i\vert $) juste après (et on passe dans l’état $q_e$).

On passe d’un mot au suivant/ au précédent par la fonction $next()$/$prec()$.

• $⟸$ : À trois rubans : à chaque fois que $M$ est dans l’état $q_e$, on lit le mot sur le 3e ruban, et on le compare à $w$ sur le premier ruban.

EX 6

M1.

On procède de même qu’en EX3, en remplaçant $𝛴^*$ par $L$ ($L$ peut être énuméré, puisqu’il est récursivement énumérable (cf. EX5)).

M2. \(∃ M_L \text{ à deux rubans }; q_e ∈ Q_{M_L} ∧ \\ q_0,(𝜀, \$),(𝜀,\$)\vdash_M^* q_e, (𝜀,\$w'), (𝜀, \$w) ⟺ w ∈ L\)

\[M_{f(L)} :\] \[\begin{align*} q_0,(𝜀, \$),(𝜀,\$) &\vdash_{M_L}^* q_e, (𝜀,\$w'), (𝜀, \$w) ⟺ w ∈ L \\ &\vdash^* q_e, (𝜀,\$w'\#w), (𝜀, \$f(w)) ⟺ f(w) ∈ f(L)\\ \end{align*}\]

EX 7

Voici un langage récursivement énumérable mais non récursif : \(L = \{(⟨M⟩, w) \vert M(w) \text{ termine}\}\)

• $L$ est récursivement én., avec la MT Universelle : on peut simuler l’action de $M$ sur $w$ (qu’elle termine ou non).
• $L$ n’est pas récursif, car sinon on a une machine $L’$ qui résout le problème de l’arrêt.

M1. Si $L$ est réc.én., il existe une machine qui énumère ce langage, et en retourne le $n$-ième mot. La fonction qui à $n$ associe le $n$-ième mot est calculable, et l’image de cette fonction est $L$.

M2.

$f(⟨M⟩,w,n)$ simule $M$ sur $w$ pendant $n$ étapes, et si $M$ accepte, retourne $(⟨M⟩,w)$, sinon $𝜀$

$Im(f) = L$