Est-ce que tous les problèmes ont une résolution par programme ?
Une illustration par les holorimes

Pierre Lescanne est chercheur en informatique au Laboratoire de l'informatique du parallélisme (CNRS, INRIA, Ecole normale supérieure de Lyon)

Quoi de plus naturel pour un scientifique que d'espérer une réponse par calcul à une question qu'il se pose? Nous entendons par là une réponse obtenue mécaniquement en temps fini à l'issue d'un processus calculatoire rigoureux. L'homme de la rue dirait simplement que la réponse est "donnée par un ordinateur". Hélas, l'espoir de résoudre "in silico" tous les problèmes qui nous paraissent un peu fastidieux n'est pas fondé; car il y a des problèmes qui résistent à l'ordinateur. Certains peuvent être programmés, mais ensuite ils requièrent tant de puissance de calculs en temps (des millions de siècles peut-être!) et en matériel (un ordinateur plus grand que dix univers!) que l'on peut les considérer comme infaisables. D'autres sont rebelles à toute programmation; c'est le cas des problèmes de correspondance que nous allons examiner, mais il n'y en a des milliers d'autres.

Les problèmes de correspondance

Leur étude est due à Emil Post l'un des fondateurs de la théorie de la calculabilité. Dans un problème de correspondance, on se donne deux listes de mots que l'on essaie de mettre en "vers holorimes". Rappelons que deux vers holorimes sont deux vers qui riment entièrement, le second reproduisant phonétiquement le premier. On dit aussi parfois tout simplement une holorime. Alphonse Allais a certainement été le grand maître de l'holorime française et nous allons nous inspirer de son "art" en imaginant une réflexion qu'il aurait pu faire à un ami musicien :

L'art efface. Olé l'ami!
La Ré Fa Sol et La Mi.

Replaçons nous au niveau strictement phonétique; les vers ci-dessus peuvent être issus du problème de correspondance suivant:

(ar, ami, é, fas, l, olé)
(ré, mi, fa, sol, la, é)

Pour que les résultats de leur concaténation correspondent: le premier mot du premier vers est pris dans la première liste à un certain rang et le premier mot du second vers est pris dans la deuxième liste au même rang. Dans notre cas, le premier mot du premier vers est le cinquième mot de la première liste soit l, ce qui signifie que le premier mot du deuxième vers doit être la. Ensuite le deuxième mot est pris au premier rang ce qui donne lar et laré, puis le mot suivant au troisième rang ce qui donne laré et laréfa, puis au quatrième rang (laréfas et laréfasol) puis au sixième rang (laréfasolé et laréfasolé). On a une première correspondance, mais on peut continuer jusqu'à laréfasolélami. Les deux correspondances que nous obtenons proviennent des listes de rang (5, 1, 3, 4, 6) et (5, 1, 3, 4, 6, 5, 2). Quand on formalise le problème on perd en poésie ce que l'on gagne en généralité. Les lettres des mots deviennent des chiffres, ici 0 et 1. Voici quelques problèmes.

Problème 1

010 00 101
101 000 01

Problème 2

101 11 011
10 011 101

Problème 3

011 1 0 10
1 0 011 001

Problème 4

000 0 11 10
0 111 0 100

Le problème 1 a pour holorime (2, 1, 3). Le problème 2 n'a pas d'holorime. On le voit en cherchant la solution à partir de la fin. Une holorime doit se terminer par 11, car seuls les deuxièmes mots du problème qui sont 11 et 011 se terminent par le même sous-mot à savoir 11. Mais alors le vers se termine par 011, il faut donc chercher un avant-dernier mot dans la première suite qui se termine par 0 et il n'y en a pas. Le problème 3 a une holorime de taille 11

011000101101101110011
qui correspond à la suite de rangs (3, 2, 4, 3, 3, 2, 1, 1, 1, 4, 1). Le problème 4 a une holorime de longueur 204. Si vous aimez ces problèmes, l'équipe PCP at home de l'université de Leipzig vous invite à vous attaquer à des problèmes vraiment difficiles et ouverts (www.informatik.uni-leipzig.de/~pcp/pcpcontest_en.html). Comme le problème 4 le suggère, il faut s'aider d'un ordinateur et d'un programme spécifique pour trouver des holorimes très longues. Si l'on cherche une réponse par programme au problème général de trouver une holorime, il faut concevoir un programme qui prend comme donnée un problème de correspondance et retourne une solution holorime s'il en existe ou réponde qu'il n'y en a pas. Quelle devra être la stratégie de ce programme? Devra-t-il commencer par le début et/ou par la fin et pourquoi pas par le milieu? Comment et quand devra-t-il s'arrêter de chercher des solutions? En fait la recherche d'un tel programme est sans espoir puisque Emil Post a démontré en 1947 qu'un tel programme ne peut pas exister. On dit que le problème de correspondance est indécidable ou incalculable.
P.L.

Pour en savoir plus sur Emile Post :
www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Post.html

A propos de mots et d'holorimes, quelques commentaires sur Mc Solaar sur le site de la Sacem :
www.sacem.fr/kiosque/notes/jmots/solaar.html