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. 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 $\alpha _{1},\ldots ,\alpha _{N}$ et $\beta _{1},\ldots ,\beta _{N}$ de mots d'un alphabet $A$ ayant au moins deux symboles. Une solution du problème est une suite d'indices $(i_{k})_{1\leq k\leq K}$ avec $K\geq 1$ et $1\leq i_{k}\leq N$ pour tous les $k$, telle que les concaténations $\alpha _{i_{1}}\ldots \alpha _{i_{K}}$ et $\beta _{i_{1}}\ldots \beta _{i_{K}}$ 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

$\alpha _{3}\alpha _{2}\alpha _{3}\alpha _{1}=bba+ab+bba+a=bbaabbbaa=bb+aa+bb+baa=\beta _{3}\beta _{2}\beta _{3}\beta _{1}.$

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é $\alpha _{2},\alpha _{3}$ et $\beta _{2},\beta _{3}$, 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.

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 q₁ à q_k, 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 : 101101110q₇00110, et un historique de calcul par : q₀101#1q₄01#11q₂1#1q₈10.

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 q₀ 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 q_f 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 ≥ 5. Le statut du problème est inconnu pour 3 ≤ N ≤ 4.

• Le problème de correspondance de Post circulaire pose la même question pour des indices $i_{1},i_{2},\ldots$ tels que les mots $\alpha _{i_{1}}\cdots \alpha _{i_{k}}$ et $\beta _{i_{1}}\cdots \beta _{i_{k}}$ sont conjugués, c'est-à-dire égaux à une rotation des indices près. Cette variante est également indécidable.

• 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(2^k), mais, le problème étant NP-complet, cette borne semble difficilement améliorable. 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.

• Une autre variante est le problème de correspondance de Post marqué, pour lequel chaque u_i et chaque v_i 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.

• Le problème de plongement de Post demande que le mot $\alpha _{i_{1}}\cdots \alpha _{i_{k}}$ soit une sous-chaîne (non nécessairement d'un seul tenant) de la chaîne $\beta _{i_{1}}\cdots \beta _{i_{k}}$. 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.

• 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.

Liens externes

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Post correspondence problem » (voir la liste des auteurs).

• (en) Eitan M. Gurari, An Introduction to the Theory of Computation, chapitre 4, Post's Correspondence Problem. Une preuve de l'indécidabilité du problème de Post fondée sur une généralisation des grammaires non contextuelles.
• (en) Solveur de PCP en ligne
• (en) « PCP@HOME » (version du 13 février 2012 sur Internet Archive)