Accueil🇫🇷Chercher

Problème de correspondance de Post

En mathématiques et en informatique théorique, et plus précisément en théorie de la calculabilité, le problème de correspondance de Post (PCP) est un problème de décision indécidable qui fut introduit par Emil Post en 1946[1]. Comme il est plus simple que le problème de l'arrêt et que le problème de la décision, il apparaît souvent dans des démonstrations d'indécidabilité, comme celle de l'ambiguïté d'une grammaire.

Définition du problème

Les données du problème sont deux listes de même longueur et de mots d'un alphabet ayant au moins deux symboles. Une solution du problème est une suite d'indices avec et pour tous les , telle que les concaténations et soient égales.

Le problème de correspondance de Post (PCP) consiste à déterminer si une solution existe ou non.

Exemples

Exemple 1

Soit les deux listes suivantes :

α1 α2 α3
a ab bba
β1 β2 β3
baa aa bb

Une solution à ce problème est la suite (3, 2, 3, 1), parce que

De plus, toutes les « répétitions » de cette solution, comme (3, 2, 3, 1, 3, 2, 3, 1), etc. sont également des solutions ; lorsqu'une solution existe, il y en a toujours une infinité de ce type.

En revanche, si les deux listes avaient été et , il n'y aurait aucune solution, parce qu'alors aucune paire se correspondant n'a la même dernière lettre, ce qui doit obligatoirement apparaître à la fin d'une solution.

On peut voir une instance du problème de Post comme une collection de blocs de la forme

αi
βi

(chaque type de bloc étant fourni en nombre illimité). Ainsi, l'exemple précédent correspond aux trois types de blocs

a
baa
ab
aa
bba
bb
i = 1 i = 2 i = 3

(fournis en quantité illimitée). Une solution correspond à un arrangement de blocs côte à côte tel que la chaîne de caractères du haut est identique à celle du bas. Ainsi, la solution donnée précédemment correspond à :

bba
bb
ab
aa
bba
bb
a
baa
i1 = 3 i2 = 2 i3 = 3 i4 = 1

Exemple 2

Utilisant cette représentation par des blocs, l'exemple suivant admet une infinité de solutions non répétitives.

bb
b
ab
ba
c
bc
1 2 3

Dans ce cas, toutes les séquences de la forme (1, 2, 2, . . ., 2, 3) sont des solutions :

bb
b
ab
ba
ab
ba
ab
ba
c
bc
1 2 2 2 3

Esquisse de démonstration de l'indécidabilité

La démonstration la plus fréquente de l'indécidabilité du problème de Post consiste à construire une instance du problème qui simule le calcul d'une machine de Turing sur une entrée particulière, une solution correspondant à l'acceptation de l'entrée par la machine. Comme décider si une machine de Turing accepte une entrée donnée est indécidable, le problème de Post l'est aussi. L'analyse qui suit est fondée sur le manuel de Michael Sipser, Introduction to the Theory of Computation[2].

L'idée est de faire coder l'historique du calcul (en) de la machine de Turing par la chaîne de caractères à faire correspondre en haut et en bas des blocs, cette chaîne commençant par des caractères décrivant l'état initial, puis l'état suivant, etc. (ces états étant séparés par un caractère spécial, noté ici #). Par définition d'une machine de Turing, un état est formé de trois données :

  • l'Ă©tat de la machine proprement dite, c'est-Ă -dire le contenu du registre d'Ă©tat ;
  • le contenu actuel du ruban ;
  • la position actuelle de la tĂŞte de lecture/Ă©criture.

Le codage d'un état est la liste des symboles écrits sur le ruban, plus un symbole spécial pris parmi les q1 à qk, représentant chacun des k états possibles du registre, ce symbole étant écrit à la position correspondant à celle de la tête de lecture/écriture sur le ruban. Ainsi, pour l'alphabet {0,1}, un état typique pourra être codé par : 101101110q700110, et un historique de calcul par : q0101#1q401#11q21#1q810.

Les blocs correspondants sont construits de telle sorte que les seuls assemblages possibles simulent le fonctionnement de la machine. Le premier bloc est ainsi

q0x#

où x est l'état initial du ruban et q0 l'état de départ du registre. À partir de ce point, la ligne du haut est toujours en retard d'un état sur celle du bas, et ne la rattrape qu'en atteignant l'état final.

Pour chaque symbole a de l'alphabet du ruban (et pour #), un bloc de copie le transfère d'un état au suivant :

a
a

Pour chaque transition possible, un bloc simule le déplacement de la tête, le changement du registre d'état, et le nouveau caractère écrit. Dans l'exemple suivant, la machine est dans l'état 4, la tête de lecture/écriture, située sur un 0, le change en 1 et se déplace vers la droite, puis le registre passe dans l'état 7 :

q40
1q7

Enfin, lorsque la ligne du bas atteint un état final (correspondant à l'acceptation de l'entrée par la machine), les blocs suivants ont pour fonction de faire « disparaitre » les symboles voisins de la tête de lecture/écriture de la ligne du bas, permettant à celle du haut de la rattraper : si qf est un état final, et a un symbole du ruban, cela correspond aux blocs :

qfa
qf
et
aqf
qf
, suivis d'un dernier bloc
qf

Certains détails n'ont pas été mentionnés (comme la gestion des frontières entre états, ou la garantie que le bloc initial est effectivement le premier utilisé), mais cette description montre en gros comment un puzzle statique peut simuler le fonctionnement dynamique d'une machine de Turing.

Variantes

De nombreuses variantes du PCP ont été envisagées ; cela vient entre autres de ce que, lorsqu'on essaie de démontrer l'indécidabilité d'un problème en le ramenant au PCP, on n'arrive souvent qu'à le réduire à une version apparemment plus faible de ce problème.

  • Si on fixe N, le nombre de types de blocs utilisables, le problème devient dĂ©cidable pour N ≤ 2, et reste indĂ©cidable pour N ≥ 7. Le statut du problème est inconnu pour 3 ≤ N ≤ 6.
  • Le problème de correspondance de Post circulaire pose la mĂŞme question pour des indices tels que les mots et sont conjuguĂ©s, c'est-Ă -dire Ă©gaux Ă  une rotation des indices près. Cette variante est Ă©galement indĂ©cidable[3].
  • Une des plus importantes variantes du PCP est le problème de correspondance de Post bornĂ©, consistant Ă  dĂ©terminer s'il existe un couple de mots correspondants n'utilisant que k blocs (se rĂ©pĂ©tant ou non). Une recherche par force brute rĂ©sout le problème en un temps O(2k)[4], mais, le problème Ă©tant NP-complet, cette borne semble difficilement amĂ©liorable[5]. Contrairement Ă  d'autres problèmes NP-complets tels que le problème SAT, le problème de correspondance bornĂ© reste difficile mĂŞme en moyenne sur des entrĂ©es choisies au hasard[6].
  • Une autre variante est le problème de correspondance de Post marquĂ©, pour lequel chaque ui et chaque vi doivent commencer avec des symboles distincts. Halava, Hirvensalo, et de Wolf ont montrĂ© que cette variante est dĂ©cidable en temps exponentiel. Ils montrèrent de plus qu'un lĂ©ger affaiblissement de cette contrainte (en exigeant seulement que les deux premiers caractères diffèrent) rend Ă  nouveau le problème indĂ©cidable[7].
  • Le problème de plongement de Post demande que le mot soit une sous-chaĂ®ne (non nĂ©cessairement d'un seul tenant) de la chaĂ®ne . Sous cette forme, il est Ă©videmment dĂ©cidable, et ce en temps très rapide, mais si l'on exige de plus que les solutions appartiennent Ă  un langage rĂ©gulier donnĂ© (obtenant le problème de plongement rĂ©gulier de Post), sa complexitĂ© augmente Ă©normĂ©ment, dominant toutes les fonctions rĂ©cursives primitives[8].
  • Le problème de correspondance avec l'identitĂ© consiste Ă  dĂ©terminer si un ensemble fini de paires de mots (sur un alphabet formĂ© de lettres et de leurs inverses, autrement dit d'Ă©lĂ©ments du groupe libre Ă  n gĂ©nĂ©rateurs) peut engendrer la paire identitĂ© par concatĂ©nations, autrement dit si le monoĂŻde engendrĂ© par un ensemble fini de couples de mots est un groupe ; ce problème est indĂ©cidable[9].

Références

  1. (en) E. L. Post, « A variant of a recursively unsolvable problem », Bull. Amer. Math. Soc, vol. 52,‎ (lire en ligne)
  2. (en) Michael Sipser, Introduction to the Theory of Computation, Thomson Course Technology, , 2e éd., 199–205 p. (ISBN 0-534-95097-3), « A Simple Undecidable Problem ».
  3. (en) K. Ruohonen, « On some variants of Post's correspondence problem », Acta Informatica, Springer, vol. 19, no 4,‎ , p. 357–367 (DOI 10.1007/BF00290732)
  4. Voir pour cette notation l'article Comparaison asymptotique
  5. (en) Michael R. Garey, David S. Johnson, Computers and intractability : a guide to the theory of NP-completeness, New York, W.H. Freeman, , 338 p. (ISBN 0-7167-1045-5), p. 228
  6. (en) Y. Gurevich, « Average case completeness », J. Comp. Sys. Sci., Elsevier Science, vol. 42, no 3,‎ , p. 346–398 (DOI 10.1016/0022-0000(91)90007-R)
  7. (en) V. Halava, « Marked PCP is decidable », Theor. Comp. Sci., Elsevier Science, vol. 255,‎ , p. 193–204 (DOI 10.1016/S0304-3975(99)00163-2)
  8. (en) P. Chambart, « Post embedding problem is not primitive recursive, with applications to channel systems », Lecture Notes in Computer Science, Springer, vol. 4855,‎ , p. 265–276 (ISBN 978-3-540-77049-7, DOI 10.1007/978-3-540-77050-3_22)
  9. (en) Paul C. Bell, « On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups », International Journal of Foundations of Computer Science, World Scientific, vol. 21.6,‎ , p. 963-978 (DOI 10.1142/S0129054110007660)

Liens externes


Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.