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 :
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
(chaque type de bloc étant fourni en nombre illimité). Ainsi, l'exemple précédent correspond aux trois types de blocs
(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 à :
|
|
|
|
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.
Dans ce cas, toutes les séquences de la forme (1, 2, 2, . . ., 2, 3) sont des solutions :
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
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 :
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 :
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 :
|
|
et |
|
|
, suivis d'un dernier bloc |
|
|
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.