Cours 4 : Indécidabilité : Problème de correspondance de Post, Pavages

Problème de Correspondance de Post

  • Donnée : 2 suites finies de mots de $𝛴^*$ : $u_1, ⋯, u_n$ et $v_1, ⋯, v_n$
  • Question : \(∃ k : ∃i_1, ⋯, i_k; \, \, \, u_{i_1} ⋯ u_{i_k} = v_{i_1} ⋯ v_{i_k}\)

Ex :

$i$ 1 2 3 4 —— —— —— —— —— $u_i$ a b ca abc

$v_i$ ab ca a c —— —— —— —— ——

$i_1 = 2, i_2 = 2, i_3 = 3, i_4 = 1, i_5 = 4$ est une solution de PCP.

PCP Modifié

  • Donnée : 2 suites finies de mots de $𝛴^*$ : $u_1, ⋯, u_n$ et $v_1, ⋯, v_n$
  • Question : \(∃ k : ∃i_1, ⋯, i_k; \, \, \, u_{i_1} ⋯ u_{i_k} = v_{i_1} ⋯ v_{i_k} ∧ (i_1 = 1)\)

PCP modifié est indécidable :

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

$M, w \mapsto^{f}$ séquences $u_i, v_i$

Sans perte de gén. :

  • $M$ a 1 unique état d’arrêt $q_f$
  • si elle s’arrête, son ruban est vide.

Heuristique :

On écrit une suite de configurations de la machine, se terminant par $q_f $ *$ : la première suite ayant un temps d’avance sur la deuxième.

Dans la colonne $v$, on regarde localement la configuration de la MT, et le mot $u$ courant est la configuration suivante de la MT

  • $𝛴_{PCP} = 𝛴 ∪ Q ∪ {◃, ▹, *}$
    • : sépare deux configurations successives
  • ◃, ▹ : marquent le début/fin de la démarche (symbole rajouté)
  • $q_e$ : état d’effacement

Table des $u_i, v_i$, calculée par $f$ :

  $u$                            ⟸ $v$ ---- --------------------------   -------------------------- 1     $◃q_0\$w*$                   $◃$

2 $a’q’$ $qa$ et $𝛿(q,a)=q’,a’,→$

3 $q’ab’$ $aqb$ et $𝛿(q,b)=q’,b’,←$

4 $a$ $a$ et $a∈𝛴$

5 $$ $$

6 $aq’$ $q$ et $𝛿(q,B)=q’,a,→$

7 $q’aa’$ $aq$ et $𝛿(q,B)=q’,a’,←$

8 $q_e$ $aq_e$

9 $𝜀$ $q_f$*$

10 $q_f$▹$ $$q_e$ —- ————————– ————————–

NB : Unique séquence possible

Preuve :

$f$ calculable, $M$ s’arrête sur $w$ ssi PCP modifié a une solution

⟹ si $M$ s’arrête sur $w$, alors PCP modifié a une solution :

$q_0$ \vdash 𝛾_1 ⋯ \vdash 𝛾_k = q_f$$

$∀l; q_0$ \vdash 𝛾_1 ⋯ \vdash 𝛾_l$

$∃ i_1 ⋯ i_n$ tq \(u_{i_1} ⋯ u_{i_n} = ◃ 𝛾_0 * ⋯ * 𝛾_l * \\ v_{i_1} ⋯ v_{i_n} = ◃ 𝛾_0 * ⋯ * 𝛾_{l-1} * \\\)

Par récurrence sur $l$ :

  • si $l=0$ : \(u_{i_1} = ◃ 𝛾_0 * \\ v_{i_1} = ◃\)

  • si \(u_{i_1} ⋯ u_{i_n} = ◃ 𝛾_0 * ⋯ * 𝛾_l * \\ v_{i_1} ⋯ v_{i_n} = ◃ 𝛾_0 * ⋯ * 𝛾_{l-1} * \\\) et $𝛾_l \vdash 𝛾_{l+1}$,

  • Cas Mvt gauche : \(𝛾_l = w_1aqbw_2 \\ 𝛾_{l+1} = w_1q'ab'w_2\) si $𝛿(q,b) = (q’,b’, ←)$

Cas où $b \neq *$ :

Alors $u_{i_{m+1}} ⋯ u_{i_p}$ est tq le mot formé par les indices $m+1, ⋯, p$ des indices vaut : \(4^{\vert w_1\vert }\cdot 3\cdot 4^{\vert w_2\vert } \cdot 5\)

⟹ si PCP modifié a une solution, alors $M$ s’arrête sur $w$ :

Par réc sur $k$ : \(u_{i_1} ⋯ u_{i_k} = ◃ 𝛾_0 * ⋯ * 𝛾_p * t \\ v_{i_1} ⋯ v_{i_k} = ◃ 𝛾_0 * ⋯ * 𝛾_{p-1} * t' \\\)

tq $𝛾_0 \vdash 𝛾_1 ⋯ \vdash 𝛾_p$

Deux cas possibles :

  • Cas 1 : $𝛾_p$ est une configuration “effacement”
  • Cas 2 : $𝛾_p \vdash 𝛾_{p+1}$, et
    • si $t’$ ne contient pas de symbole de $Q$ et ne se termine pas par $*$ : $t’=t$
    • sinon : $t’_ \vdash t _$

Pour $k=1$ : \(u_{i_1} ⋯ u_{i_k} = ◃ 𝛾_0 * \\ v_{i_1} ⋯ v_{i_k} = ◃ \\\)

Pour $k$ : \(u_{i_1} ⋯ u_{i_k} = ◃ 𝛾_0 * ⋯ * 𝛾_p * t \\ v_{i_1} ⋯ v_{i_k} = ◃ 𝛾_0 * ⋯ * 𝛾_{p-1} * t' \\\)

⟶

\[u_{i_1} ⋯ u_{i_{k+1}} = ◃ 𝛾_0 * ⋯ * 𝛾_p * t \\ v_{i_1} ⋯ v_{i_{k+1}} = ◃ 𝛾_0 * ⋯ * 𝛾_{p-1} * t' \\\]

Exs :

Si $t’ v_{i_{k+1}}$ préfixe de $𝛾_p$ :

  • Si $𝛾_p = t’qw$, $v_{i_{k+1}}$ commence par $q$ :
    • Cas 2 ou 6 : $t=t’$, $v_{i_{k+1}} = qa$, $u_{i_{k+1}} = a’q’$

Si $𝛾_p = t’ a w$, $b∈𝛴$ et $w$ ne commence pas par $q∈Q$ :

\[u_{i_1} ⋯ u_{i_k} = ⋯ t' a w * t \\ v_{i_1} ⋯ v_{i_{k+1}} = ⋯ t' \\\]

$v_{i_{k+1}}$ commence par $a$ : $v_{i_{k+1}} = a$ (car $w$ ne commence pas par $q$), $u_{i_{k+1}} = a$

\[u_{i_1} ⋯ u_{i_k} = ⋯ t' a w * t a \\ v_{i_1} ⋯ v_{i_{k+1}} = ⋯ t' a \\\]

Si $t=t’$, alors $t’a = ta$

Si $t’ \vdash t$, alors $t’a \vdash ta$

Théorème : PCP indécidable, par réduction de PCP modifié.

On construit une fonction calculable $f$ tq

\[f =\begin{cases} PCP modif ⟶ PCP \\ u_1, ⋯, u_n v_1, ⋯, v_n \mapsto u'_1, ⋯, u'_n, v'_1, ⋯, v'_n \end{cases}\]

Idée générale : faire commencer les $u’_i$, $v’_i$ par l’indice $1$

Les $u’_i$, $v’_i$ commencent par une lettre différente, sauf pour $i=1$.

$i≠1$ :

$u’_i = \overline{u_i}$, où $x \mapsto \overline{x}$ insère un caractère spécial $\bullet$ avant chaque lettre des $u_i$, après chaque lettre des $v_i$.

Pour $i=0$:

  • $u’_0 = \triangleleft \overline{u_1}$
  • $v’_0 = \triangleleft \bullet \overline{v_1}$

et

  • $u’_{n+1} = \bullet \triangleright$
  • $v’_{n+1} = \triangleright$

Mq

\[∃k; ∃i_1, ⋯, i_k; \begin{cases} u_{i_1} ⋯ u_{i_k} = v_{i_1} ⋯ v_{i_k} \\ i_1 = 1 \end{cases} ⟹ ∃k'; ∃i'_1, ⋯, i'_k; \begin{cases} u'_{i'_1} ⋯ u'_{i'_k} = v'_{i'_1} ⋯ v'_{i'_k} \\ i_1 = 1 \end{cases}\]

Par réc sur $j$ :

\[\begin{cases} u'_{i'_1} ⋯ u'_{i'_j} = \triangleleft \overline{u_1 ⋯ u_{i_j}} \\ v'_{i'_1} ⋯ v'_{i'_j} = \triangleleft \bullet \overline{v_1 ⋯ v_{i_j}} \end{cases}\]
  • j=1 :
    • $u’_0 = \triangleleft \overline{u_1}$
    • $v’_0 = \triangleleft \bullet \overline{v_1}$
  • $j>1$:
    • \[\begin{cases} u'_{i'_1} ⋯ u'_{i'_{j+1}} = \triangleleft \overline{u_1 ⋯ u_{i_j}} \cdot \overline{u_{i_{j+1}}} = \triangleleft \overline{u_1 ⋯ u_{i_{j+1}}}\\ \text{idem pour } v \end{cases}\]
\[\begin{cases} u'_{i'_1} ⋯ u'_{i'_{k+1}} = \triangleleft \overline{u_1 ⋯ u_{i_k}} \bullet \triangleright \\ v'_{i'_1} ⋯ v'_{i'_{k+1}} = \triangleleft \bullet \overline{v_1 ⋯ v_{i_k}} \triangleright \\ \end{cases}\]

d’où

\[u'_{i'_1} ⋯ u'_{i'_{k+1}} = v'_{i'_1} ⋯ v'_{i'_{k+1}}\]

Réciproquement :

Si \(u'_{i'_1} ⋯ u'_{i'_k} = v'_{i'_1} ⋯ v'_{i'_k}\)

Sans perte de généralité, on peut supposer que : $∀j, (u_j ≠ 𝜀 ∨ v_j ≠ 𝜀)$ (quitte à enlever les paires de mots vides).

  • Si $u’_{i’_1} = 𝜀$: soit $j$ le premier indice tq $u’_j ≠ 𝜀$ : alors nécessairement $u’_j ∈ {\bullet, \triangleleft}$
    • Donc : $v’_{i’_1} ∈ 𝛴$ : absurde

Donc

  • $u’_{i’_1} ≠ 𝜀$
  • $v’_{i’_1} ≠ 𝜀$

1ère lettre de $u’{i’_1}$ = 1ère lettre de $v’{i’_1}$ ⟹ $i’_1 = 0$

$i_1 = 1$, $i’_2, ⋯, i’_k = i_2, ⋯, i_k$

Pavages

  • Donnée : $T$ = ensemble fini de tuiles.
    • $H⊆T^2$ : compatibilité horizontale
    • $V⊆T^2$ : compatibilité verticale
    • $t_0 ∈ T$
  • Question : Peut-on paver $ℕ^2$ avec ces tuiles ?

Pavage de $ℕ^2$ :

$f: ℕ^2 ⟶ T$ tq

  • $f(0,0)=t_0$
  • $∀i, j, (f(i,j), f(i+1,j)) ∈ H$
  • $∀i, j, (f(i,j), f(i,j+1)) ∈ V$

Théorème : Le problème de pavage est indécidable : réduction du problème de l’arrêt sur $𝜀$, et $M$ n’écrit jamais $B$.

Étape Configuration
$n$ $𝛾_n$
$1$ $$q_0 B⋯B$
$0$ $q_0$B⋯B$

Ex :

Étape Configuration
$n+1$ $abc’qde$
$n$ $abqcde$

$T = (𝛴∪Q)^3∩(𝛴^Q𝛴^∪𝛴^*)$ et tq

  • $Bba ∈ T ⟹ b=B ∧ a=B$
  • $aBb∈T ⟹ b=B$

$H={(abc,bcd)}$

$V$ contient :

  • $(abc,abc)$, $a,b,c∈𝛴$
  • $(bqc,bc’q)$ si $𝛿(q,c)=q’,c’,→$
  • …

Reltions de compatibilité :

  • Verticale :

Ex : si $𝛿(q,c)=q’,c’,→$

Étape Configuration
$n+1$ $faq’bc’de$
$n$ $fabqcde$

⟶ $(fab,faq’)$, $(cde,c’de)$

$t_0 = q_0 $ B$

Mq : $M$ ne s’arrête pas sur $𝛴$ ssi $∃$ pavage

NB : indécidabilité de l’arrêt ⟹ indécidabilité du non-arrêt (langages récursifs = clos par complémentarité)

1) $M$ ne s’arrête pas sur $𝛴$ $⟹$ $∃$ pavage :

$𝛾_0 \vdash_M ⋯ \vdash_M 𝛾_n \vdash ⋯$

$𝛾_i = 𝛼_{i,0} ⋯ 𝛼_{i,m_i} B^𝜔$

\[\begin{cases} f(i,j) = 𝛼_{j,i} 𝛼_{j,{i+1}} 𝛼_{j,{i+2}} \\ f(0,0)=q_0 \$ B \end{cases}\]

1ère ligne pavable.

$(f(i,0),f(i+1,0))∈H$

  • $f(i,0) = $BB$ pour $i=1$
  • $f(i,0) = B^3$ pour $i≥2$

Si les $n$ premières lignes vérifient les relations de compatibilité : on passe de la $n$ à $n+1$-ème ligne de même qu’avant.

$w$ $q_{n+1}$ $w’$
$w$ $q_n$ $w’$

2) $∃$ pavage $⟹$ $M$ ne s’arrête pas sur $𝛴$ :

  • $𝛼_{i,j}$ : 1ere lettre de $f(i,j)$
  • Pa compat. sur $H$ : \(f(i,j) = 𝛼_{i,j} 𝛼_{i+1,j}𝛼_{j+2,j}\)

Par réc sur $n$:

\[𝛼_{0,n}⋯𝛼_{m,n} = 𝛾_n; 𝛾_0 \vdash ⋯ \vdash 𝛾_n\]
  • Pour $n=0$ :
    • $f(0,0)= q_0$B$
    • $H$ :
      • $f(1,0)= $BB$
      • $f(2,0)= B^3$
      • $∀i≥2, f(i,0)=B^3$
  • Pour $n>0$ :

Lemme : Si $𝛼_{i,n}, ⋯, 𝛼_{i+2,n} ∈ 𝛴$, alors \(𝛼_{i+1,n+1}= 𝛼_{i+1,n}\)

Soit $q_n = 𝛼_{n,m_n} ∈Q$

$(𝛼_{n,m_n-1} q_n 𝛼_{n,m_n+1}, 𝛼_{n+1,m_n-1} 𝛼_{n+1,m_n} 𝛼_{n+1,m_n+1} )$

  • Si $𝛿(q_n, 𝛼_{n, m_n+1}) = q’, a, →$ :
    • $𝛼_{n+1,m_n-1} = 𝛼_{n, m_n-1}$
    • $𝛼_{n+1,m_n} = a$
    • $𝛼_{n+1,m_n+1} = q’$
  $𝛼_{n,m_n-1}$ $a$ $q’$ $b$ $c$ ?
d $𝛼_{n,m_n-1}$ $q_n$ $𝛼_{n,m_n+1}$ $b$ $c$ $e$

Pourquoi “?” ne peut pas être un état ?

⟶ car, nécessairement

  $𝛼_{n,m_n-1}$ $a$ $q’$ $b$ $c$ ?  
d $𝛼_{n,m_n-1}$ $q_n$ $𝛼_{n,m_n+1}$ $b$ $c$ $e$ $f$

et, par le lemme :

  $𝛼_{n,m_n-1}$ $a$ $q’$ $b$ $c$ $e$  
d $𝛼_{n,m_n-1}$ $q_n$ $𝛼_{n,m_n+1}$ $b$ $c$ $e$ $f$

Formellement :

$∀j>m_{n+1}, 𝛼_{n,j}𝛼_{n,j+1}𝛼_{n,j+2}∈𝛴$

Lemme : $𝛼_{n+1, j+1} = 𝛼_{n,j+1}$

  $c$ $b$ $𝛼_{n,m-1}$ $a$ $q’$    
$h$ $c$ $b$ $𝛼_{n,m-1}$ $q_n$ $𝛼_{n,m+1}$    

Si $f$ est un pavage, mq $M$ ne s’arrête pas sur $𝜀$

On suppose sans perte de généralité que $M$ ne revient jamais au début du ruban et jamais dans l’état $q_0$

NB : à droite, le problème est résolu car $M$ n’écrit pas de blancs : on peut faire pareil à gauche, avec une bordure immuable de $\bullet$.

Problème bien plus difficile : 10ème problème de Hilbert (équations diophantiennes).

Leave a comment