Problèmes de correspondance de Post

Jusqu'à maintenant, tous les problèmes que nous avons montrés indécidables concernaient des questions portant sur les machines de Turing, comme par exemple de savoir si une machine accepte ou non une entrée donnée. Nous allons voir un problème apparemment très simple et sans rapport a priori avec les machines de Turing qui est pourtant indécidable.

Problème de Post standard

Une instance du problème de correspondance de Post (PCP en abrégé) est la donnée d'un entier m ≥ 1 et de deux suites u1, …, um et v1, …, vm de chacune m mots sur un alphabet A. On dit qu'une instance du problème de Post a une solution s'il existe une suite finie i1, …, in d'entiers dans l'intervalle [1,m] telle que

ui1ui2 … uin = vi1vi2 … vin

où ui1ui2 … uin et vi1vi2 … vin désignent respectivement la concaténation des n mots ui1, ui2, …, uin et la concaténation des n mots vi1, vi2, …, vin.

Soit par exemple l'instance du problème de Post donné par m = 4 et par u1 = aba, u2 = b, u3 = a, u4 = ab, v1 = a, v2 = b, v3 = ababa et v4 = b. Cette instance du problème de Post admet la solution n = 5, i1 = 1, i2 = 2, i3 = 3, i4 = 2 et i5 = 1. En effet, on a l'égalité u1u2u3u2u1 = v1v2v3v2v1 = ababababa. Dans cette solution, on remarque que dans cette solution on i1 = i5 = 1. De manière générale, deux entiers ik et il de la suite pour k ≠ l peuvent être égaux.

Il faut voir une instance de PCP comme la donnée de m dominos ou chaque domino porte un mot ui en haut et le mot correspondant vi en bas. L'exemple précédent correspond donc à la donnée des quatre dominos suivants.

u
v
aba
a
b
b
a
ababa
ab
b
Numéro1234

Une solution i1, …, in est alors une façon de choisir des dominos de telle sorte qu'en mettant bout à bout les dominos choisis, le même mot peut être lu en haut et en bas. Le fait que deux entiers ik et il peuvent être égaux pour k ≠ l signifie que le même domino peut être utilisé plusieurs fois. Par contre, rien n'impose d'utiliser tous les dominos. Par exemple, la solution qui a été donnée à l'instance précédente n'utilise pas le dernier domino.

ababababa =
ababababa =
aba
a
b
b
a
ababa
b
b
aba
a
Solution i1 = 1 i2 = 2 i3 = 3 i4 = 2 i5 = 1

Problème de Post modifié

Le problème de correspondance de Post modifié (PCPM en abrégé) est une variante du problème de Post. Une instance du PCPM est identique à une instance de PCP. Il s'agit de la donnée d'un entier m et de deux suites u1, …, um et v1, …, vm de chacune m mots sur un alphabet A. Par contre la question posée est différente. On dit qu'une instance du problème de Post modifié a une solution s'il existe une suite finie i1, …, in d'entiers dans l'intervalle [1,m] telle que i1 = 1 et

ui1ui2 … uin = vi1vi2 … vin

La seule différence entre PCP et PCPM est que dans PCPM, le premier entier de la solution doit être égal à 1. Cela signifie qu'on impose à la solution de commencer par le premier couple ou domino (u1, v1). Nous allons voir que les deux problèmes sont en fait équivalents dans le sens où ces deux problèmes se ramènent l'un à l'autre.

Équivalence entre PCP et PCPM

Nous allons montrer que PCP se ramène à PCPM et inversement. Plus précisément, nous allons montrer que la recherche d'une solution pour une instance de PCP se ramène à la recherche de solution pour plusieurs instances de PCPM et qu'inversement la recherche d'une solution pour une instance de PCPM se ramène à la recherche de solution pour une instance de PCP.

Réduction de PCP à PCPM

Résoudre une instance de PCPM consiste à trouver une solution, au problème de PCP de même instance, qui commence par le premier couple. Dans PCP, l'ordre des couples (uk, vk) dans l'instance n'a pas d'importance. N'importe quel couple peut être mis comme premier. S'il existe une solution à une instance de PCP, celle-ci commence par un couple (uk, vk) pour un entier k entre 1 et n. Si ce couple est placé en premier, l'instance de PCPM correspondant a aussi une solution. Pour résoudre une instance de PCP avec m couples de mots, il suffit de résoudre les m instances de PCPM où chacun des m couples est placé en premier.

Réduction de PCPM à PCP

Afin de montrer comment ramener PCPM à PCP, nous introduisons deux fonctions p et s de A* dans (A ∪ {$})* où $ est un nouveau symbole qui n'appartient pas l'alphabet A. Pour un mot w = a1a2 … ak, on pose

p(w) = $a1$a2$ … $ak et
s(w) = a1$a2$ … $ak$.

On remarque que les fonctions p et s vérifient les propriétés suivantes. Pour deux mots v et w, on a p(vw) = p(v)p(w) et s(vw) = s(v)s(w). Plus généralement pour toute suite w1, …, wr de mots, on a p(w1 … wr) = p(w1) … p(wr) et s(w1 … wr) = s(w1) … s(wr). On a aussi l'égalité p(w)$ = $s(w) pour tout mot w.

Nous expliquons maintenant comment passer d'une instance de PCPM à une instance de PCP qui admet une solution si et seulement si l'instance de départ admet aussi une solution. Soit l'instance de PCPM donnée par m ≥ 1 et par les deux suites u1, …, um et v1, …, vm de chacune m mots sur A. On définit deux suites de mots (u'k)1 ≤ k ≤ 2m+1 et (v'k)1 ≤ k ≤ 2m+1 de longueur 2m+1 par

On considère alors l'instance de PCP donnée par m'= 2m+1 et par les deux suites de mots u'1, …, u'2m+1 et v'1, …, v'2m+1 de longueur m'. Nous allons que cette instance de PCP admet une solution si et seulement si la solution originale de PCPM a une solution.

Supposons d'abord que la solution originale de PCPM a une solution i1, …, in telle que i1 = 1 et w = ui1 … uin = vi1 … vin. On a p(w)$ = p(ui1)p(ui2) … p(uin-1)p(uin)$ = $s(w) = $s(vi1)s(vi2) … s(vin-1)s(vin). Par définition des suites u' et v' et puisque i1 = 1, cette égalité s'écrit u'2m+1u'i2 … u'in-1u'm+in = v'2m+1v'i2 … v'in-1v'm+in. Ceci montre que la suite 2m+1,i2, …, in-1, m+in est une solution de l'instance du problème de PCP.

Réciproquement, il faut remarquer que le couple (u'2m+1, v'2m+1) est le seul couple de mots qui commence par la même lettre. Toute solution au problème de PCP doit donc commencer par i'1 = 2m+1. Il faut aussi remarquer que les couples (u'm+k, v'm+k) pour 1 ≤ k ≤ m sont les seuls couples à se terminer par la même lettre. Toute solution au problème de PCP doit donc se terminer par un entier i'n de la forme m+k pour 1 ≤ k ≤ m. Il est alors facile de vérifier que toute solution du problème de PCP correspond à une solution du problème de PCPM original.

Indécidabilité du problème de Post

Nous allons maintenant montrer que le problème de correspondance de Post est indécidable. Pour cela, nous allons montrer que le problème d'acceptation d'une machine de Turing se réduit au problème de Post modifié. Plus précisément, nous montrons que le langage

L = { ⟨M, w⟩ | M accepte w }

se réduit au problème de correspondance de Post modifié. Pour chaque ⟨M, w⟩ nous construisons une instance du problème de Post modifié qui admet une solution si et seulement si la machine M accepte le mot w. On peut supposer que la machine M est normalisée. Sinon, on la remplace par une machine M' équivalente et normalisée. La machine M' peut être calculée à partir de la machine M. On suppose donc que la machine M s'arrête uniquement dans deux états q+ et q- où q+ est final et où q- n'est pas final.

Soit M = (Q, Σ, Γ, E, q0, F, #) une machine de Turing normalisée. On suppose que les ensembles Q et Γ sont disjoints. Soit $ un symbole qui n'appartient pas à son alphabet de bande Γ. On construit alors un problème de Post modifié sur l'alphabet A = Q ∪ Γ ∪ {$}. Le premier domino est le suivant.

$
$q0w$

On ajoute ensuite un domino pour chacune des transitions possibles. Pour chaque transition p, a → q, b, R de M, on ajoute le domino suivant.

pa
bq

Pour chaque transition p, a → q, b, L de M et chaque symbole c ∈ Γ, on ajoute le domino suivant.

cpa
qcb

Pour tout symbole a ∈ Γ, on ajoute le domino suivant. Ces dominos permettent de recopier les symboles inchangés d'une configuration à la configuration suivante.

a
a

On ajoute aussi les domino suivants qui permettent de passer d'une configuration à une autre. Le second permet en outre d'ajouter un symbole blanc implicite à la fin d'une configuration.

$
$
$
#$

Pour terminer le calcul, on ajoute finalement les dominos,

aq+
q+
q+a
q+
q+$$
$