Le problème de Post

Projet proposé par Gilles Dowek1

Prélude



On considère un jeu de dominos. Sur chacun des dominos se trouvent inscrits deux mots (un en haut et un en bas). Ces dominos sont de trois types : sur les dominos du premier type sont inscrits les mots BB et BBBA, sur ceux du deuxième type sont inscrits les mots AA et A, sur ceux du troisième type les mots BB et AB. Il y a une infinité de dominos de chaque type.

Si on assemble deux dominos du troisième type, puis un domino du premier type
on forme les mots BBBBBB et ABABBBBA qui sont différents. Pour ouvrir la porte magique, il faut trouver un assemblage non vide de dominos, tel que les deux mots formés soient identiques. Est-ce possible ?

Le problème de Post

Une instance E du problème de Post est un ensemble fini de types de dominos, c'est-à-dire une partie finie de {A,B}* 2.

Une solution d'une telle instance E est une suite finie non vide de dominos de E qui forme deux mots identiques, c'est-à-dire une suite finie d'éléments de E telle que le mot obtenu en concaténant parties gauches des couples de cette suite soit identique à celui obtenus en concaténant leurs parties droites.

Emil Post (1897-1954) a démontré en 1946 que ce problème était indécidable : on ne peut pas écrire de programme qui indique si une instance du problème de Post a une solution ou non. En revanche, on peut écrire un programme qui cherche une solution, en trouve toujours une si l'instance testée a une solution, mais peut boucler si ce n'est pas le cas. On appelle un tel programme un programme de semi-décision.

Un programme de semi-décision

Le projet consiste à écrire un tel programme, puis à l'améliorer.

Soit une instance E du problème de Post, on considère le graphe infini suivant : ses sommets sont tous les couples de mots et il y a un arc allant du sommet (m,n) à tous les sommets de la forme (ma,nb) où (a,b) est un couple de E. Ce graphe est à branchement fini. L'instance E a une solution s'il y a un chemin non trivial dans ce graphe allant du sommet (e,e) à un sommet de succès de la forme (p,p).

Dans un graphe infini le parcours en profondeur d'abord n'est pas complet, en effet dans l'exemple de la page précédente, il amènerait à suivre la branche infinie ((BB)n,(BBBA)n) sans jamais revenir en arrière. En revanche un parcours en largueur d'abord est complet, dans le sens que chaque sommet accessible depuis (e,e) sera visité à un certain moment (même s'il est faux qu'à un certain moment tous ces sommets auront été visités).

Écrire un programme de semi-décision pour le problème de Post en utilisant en parcours de graphe en largeur d'abord. On pourra essayer ce programme avec l'exemple ci-dessus ainsi qu'avec les exemples suivants.





Élaguer pour échouer

Le programme auquel on a abouti trouve toujours une solution si l'instance testée en a une, mais il n'échoue jamais. On peut l'améliorer de manière à ce qu'il échoue dans un certain nombre de cas où l'instance testée n'a pas de solution (même s'il est impossible qu'il échoue toujours dans ce cas, puisque le problème est indécidable).

Une première manière de le faire échouer est d'exploiter le fait que dans un sommet de la forme (m,n) si m n'est pas un préfixe de n et n n'est pas un préfixe de m, alors le sommet est sans espoir : aucun sommet accessible depuis ce sommet ne sera un sommet de succès de la forme (p,p). Par exemple dans tous les sommets accessibles depuis (A,B) le premier mot commence par la lettre A et le second par la lettre B. Il n'est donc pas utile de poursuivre l'exploration à partir d'un tel sommet.

Écrire un programme de semi-décision pour le problème de Post qui utilise cette amélioration. On pourra l'essayer sur les quatre instances ci-dessus.

La simplification des équations

Une deuxième amélioration utilise le fait que l'équation
ABBAA x = ABBA y
a les mêmes solutions que l'équation
Ax = y
De ce fait, une suite de dominos mène du sommet (ABBAA, ABBA) à un sommet de succès si et seulement si elle mène du sommet (A, e) à un sommet de succès.

De ce fait, on peut modifier la définition du graphe ci-dessus en posant un arc allant du sommet (m,n) à tous les sommets de la forme simple(ma,nb) où (a,b) est un couple de E, simple(ma,nb) ¹ Fail et simple est la fonction de {A,B}*2 dans {A,B}*2 È {Fail} définie par
simple(e, y) = (e, y)
simple(x, e) = (x, e)
simple(A x, A y) = simple(x, y)
simple(B x, B y) = simple(x, y)
simple(A x, B y) = Fail
simple(B x, A y) = Fail

Écrire un programme de semi-décision pour le problème de Post qui utilise cette amélioration. On pourra l'essayer sur les quatre instances ci-dessus.

Travail demandé

Écrire un programme qui prend en argument une liste de couples de mots et qui recherche une solution de l'instance du problème de Post définie par cette liste. Le programme utilisera les deux optimisations ci-dessus de manière à échouer pour certains problèmes qui n'ont pas de solution.

Est-il possible d'améliorer encore ce programme de manière à ce qu'il échoue plus souvent ?
1
Gilles.Dowek@polytechnique.fr

Ce document a été traduit de LATEX par HEVEA.