Quelques problèmes particulièrement intéressants

Poser les bonnes questions a toujours été d'une importance capitale en sciences.

L'informatique, entre autres, est née – pourrait-on dire – d'une question particulièrement intéressante sur la calculabilité, à savoir quels sont les nombres qui sont calculables?

Historiquement, on considère que ce problème fut posé par David Hilbert lors d'une allocation publique à Paris portant sur les 23 problèmes les plus importants des mathématiques de son époque, en 1900.

Deux autres des grandes questions posées par David Hilbert, à savoir comment trouver si un système d'axiomatique formel est complet (s'il permet de prouver tout énoncé vrai) et si un système d'axiomatique formel est cohérent (s'il est impossible, avec ce système, de démontrer à la fois une proposition et sa négation), ont tous deux été résolus par Kurt Gödel, logicien de génie et contemporain et ami d'Albert Einstein (voir Les limites de ce qui est faisable, ci-dessous).

Le site http://www.claymath.org/prizeproblems/ répertorie quelques uns des problèmes les plus importants des mathématiques et de l'informatique aujourd'hui. Un prix de 1 million de dollars est offert à la résolution de chacun d'entre eux.

L'un d'entre eux, la conjecture de Poincaré, a été résolu par Grigori Perelman, un personnage très particulier. Un autre, associé à la quête d'une solution pour les équations de Navier-Stokes, a été résolu par Mukhtarbai Otelbayev.

Un autre site, http://www.eff.org/coop-awards/prime-release1.htm, offre des montants d'argent intéressants pour des efforts collaboratifs de résolution de problèmes de calcul difficiles. Un petit texte amusant mettant en relief l'intérêt de ces problèmes se trouve sur http://www.studyworksonline.com/cda/content/article/0,,NAV4-44_SAR193,00.shtml.

Entre autres, le problème $P=NP?$ y apparaît, lui qui a été présenté (à juste titre, sans doute) par Donald Knuth comme étant, sous sa forme du problème du commis voyageur (en anglais: TSP, pour Traveling Salesman Problem), le problème le plus important de toute la discipline informatique.

Les limites de ce qui est faisable

Il existe des limites à ce qui peut être algorithmiquement réalisé. Ceci est une affirmation qui fait réagir les scientifiques de manière souvent adverse, à plus forte partie les informaticiens qui ont l'impression (pas si folle) de pouvoir, à l'aide d'une stratégie assez astucieuse, résoudre tous les problèmes.

Or, répétons-le, il y a des limites à ce qui peut être fait. Tel que mentionné plus haut, Kurt Gödel a, avec son théorème d'incomplétude (Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme), montré que tout système axiomatique au moins aussi fort que celui de l'arithmétique des nombres entiers ne peut à la fois être complet et cohérent – ce qui signifie essentiellement, présumant la cohérence de la logique mathématique[1], qu'il existe une infinité d'énoncé qui sont vrais mais ne peuvent être démontrés à partir d'un ensemble d'axiomes, peu importe l'ensemble d'axiomes choisi.

Ce résultat a envoyé une onde de choc à travers le monde scientifique tout entier, et fait encore énormément parler aujourd'hui, chacun ayant sa propre vision et sa propre compréhension des conséquences réelles de ce résultat. Certains, dont Roger Penrose, pensent qu'il s'agit d'une preuve que l'esprit humain échappe à l'algorithmique, et dépasse les limites possibles de toute mécanique – Penrose pense donc que ce résultat stipule que l'intelligence artificielle est utopique. D'autres (dont moi-même) font une lecture différente du résultat, ou du moins y voient là une détermination qui affecte aussi les humains.

Certains problèmes sont très complexes. On peut évaluer la complexité relative de différentes problèmes, grâce en grande partie à Alan Turing (voir Introduction à la complexité algorithmique). Il se trouve que certains problèmes sont algorithmiquement indécidables – donc qu'il ne peut y avoir, pour ces problèmes, de solution à l'aide d'une méthode formelle de solution, quelle qu'elle soit. On peut introduire une gradation entre plusieurs problèmes indécidables: on peut donc affirmer, en souriant, que «certains problèmes insolubles sont plus insolubles que d'autres»!.

De l'indécidabilité algorithmique

Pour comprendre qu'il existe au moins un problème qui soit algorithmiquement indécidable – il en existe en fait une infinité, mais commençons avec un seul pour digérer le concept – il nous faut d'abord quelques définitions.

• On dira d'un problème qu'il est décidable s'il existe un algorithme qui puisse le résoudre, peu importe le temps requis ou la mémoire utilisée pour y arriver. Décidable ne veut pas dire efficace. Seule restriction : l'algorithme ne doit pas itérer à l'infini – il peut être aussi gourmand qu'il le veut, en temps ou en espace, dans la mesure où ses besoins sont finis – dans la mesure où il y a une limite supérieure à ses besoins en temps et en espace, pour un échantillon à traiter donné.

On s'en doutera, s'ensuit la définition suivante :

• On dira d'un problème qu'il est indécidable si aucun algorithme n'existe (et, à plus forte raison, si aucun algorithme ne peut exister) pour le résoudre.

Comment démontrera-t-on qu'un problème donné est indécidable? Voici l'idée :

• On présentera un tel problème
• On présumera l'existence d'un algorithme capable de le résoudre (sans dire comment il y arrive), et
• On montrera que ceci nous mène à une contradiction

Exemple de problème décidable

Imaginons le problème COMPILE.

Son intrant sera le texte (le « listing ») d'une fonction F(X:chaîne):chaîne en langage PASCAL.

Son extrant sera booléen, soit VRAI si la fonction est légale selon les règles du langage PASCAL (donc si elle compile), et FAUX sinon.

On dira que COMPILE est un problème décidable. Non seulement COMPILE est soluble (on écrit, en informatique, des programmes validés par un compilateur sur une base quotidienne), mais on dispose d'un tas de solutions bien documentées à ce problème. Puisqu'il existe des tas de compilateurs commerciaux, on présumera ici que vosu acceptez le caractère soluble de COMPILE.

Exemple de problème indécidable

Imaginons le problème ARRÊT.

Ses intrants seront (a) le texte (le « listing ») d'une fonction F(X:chaîne):chaîne en langage PASCAL, et (b) une chaîne de caractères W.

Son extrant sera booléen, soit VRAI si l'exécution de F(W) arrête normalement (ou plante), et FAUX si l'exécution de F(W) boucle à l'infini.

On prétend que ARRÊT est un problème indécidable (d'ailleurs, avez-vous déjà vu un compilateur capable de vous annoncer ce genre de chose?). Voici la démonstration.

Démonstration de l'indécidabilité de ARRÊT

Supposons que ARRÊT soit décidable (pour démarrer la démonstration par contradiction).

Puisque ARRÊT est possible (c'est notre hypothèse), on est en droit d'écrire la fonction suivante:

Function CANTOR(Z:chaîne):booléen;
   { définition de la fonction ARRÊT, qu'on présume exister
     pour les besoins de la cause }
   BEGIN
      while ARRÊT (Z,Z) do ;
      CANTOR := true;
   END

On peut voir que, tel qu'écrit ici, CANTOR(Z) arrêtera si et seulement si ARRÊT(Z,Z) est FAUX, sinon CANTOR(Z) bouclera à l'infini (à cause de la répétitive tant que à l'intérieur).

On se doute que, puisque ARRÊT prend deux morceaux de texte dont le premier doit être le texte d'une fonction et le second un paramètre textuel à cette fonction, le Z passé à la fonction CANTOR sera le texte d'une fonction.

Selon la définition de notre problème, d'ailleurs, pour que ARRÊT(Z,Z) soit FAUX, il faut que l'hypothétique exécution de Z(Z) boucle à l'infini (car ARRÊT(F,W) doit retourner FAUX si et seulement si F(W) boucle à l'infini).

On se souviendra que le Z ici nous appartient, puisque ARRÊT ne doit pas être dépendant d'un Z ou de l'autre – toute fonction bien écrite devrait faire l'affaire.

Posons maintenant ce Z comme étant le texte de CANTOR. On en a le droit, bien sûr – CANTOR est une fonction valide, après tout, et elle vaut bien n'importe quelle autre fonction!

Nous obtiendrons alors que CANTOR(texte de CANTOR) arrêtera si et seulement si ARRÊT(texte de CANTOR, texte de CANTOR) est FAUX.

Mais le sens de cet énoncé, on s'en souviendra, est que CANTOR(texte de CANTOR) boucle à l'infini!

Donc, si on présume la décidabilité de ARRÊT, on arrive ici à la situation où CANTOR(texte de CANTOR) arrête si et seulement si CANTOR(texte de CANTOR) boucle à l'infini.

Nous avons donc une sérieuse contradiction, ce qui invalide notre hypothèse de départ. ARRÊT est, clairement, un problème indécidable – il ne peut exister d'algorithme pour le résoudre.

Comparer la complexité de problèmes

Notation

La notation utilisée ci-dessus signifie « A se réduit au sens de Turing à B », ou encore « A est un problème plus facile ou égal à B ».

Cette notation s'applique si et seulement si on ne peut résoudre A que dans la mesure où on a à notre disposition une fonction « prédéfinie » qui résout B. On verra plus bas comment on l'applique dans le cas des problèmes indécidables.

Il n'y a aucune restriction de temps ou d'espace dans la complexité des soutions à l'un ou l'autre des problèmes, mais il est interdit qu'un des algorithmes boucle à l'infini.

La notation suivante :

signifie « A équivaut au sens de Turing à B », ou encore « A est un problème aussi facile (ou aussi difficile) que B », donc :

On comprend intuitivement que la réduction et l'équivalence au sens de Turing respectent tous deux les propriétés habituelles des opérateurs relationnels, incluant celles présentées à ci-dessous.

Un théorème amusant (et son corollaire)

Théorème : si $A \leq_T B$ et si $B$ est décidable, alors $A$ est décidable.

Démonstration :

• $A \leq_T B$ signifie qu'on a un algorithme $A'$ qui résout $A$ , et qui utilise pour ce faire une fonction « prédéfinie » $B'$ qui résout $B$ .
• Sachant que $B$ est décidable, on sait avoir un algorithme $B$ qui le résout;
• dans $A'$ , on remplace tous les appels à la fonction « prédéfinie » $B'$ par des appels à $B$ ;
• on obtient un algorithme pour $A$;
• ainsi, $A$ est décidable. C.Q.F.D.

Corollaire au théorème : si $A$ est indécidable et $A \leq_T B$ , alors $B$ est indécidable.

Autres exemples de problèmes indécidables

On sait que ARRET est indécidable (voir la démonstration, plus haut).

Imaginons maintenant le problème BOUCLE: écrire une fonction qui prend en paramètre le texte d'une fonction à un paramètre, et le texte décrivant ce paramètre, et qui retourne VRAI si cette combinaison fonction,paramètre mène à une boucle infinie, FAUX sinon.

Ses intrants seront (a) le texte (le listing) d'une fonction F(X:chaîne):chaîne en langage PASCAL, et (b) une chaîne de caractères W.

Son extrant sera booléen, soit VRAI si l'exécution de F(W) boucle à l'infini, et FAUX si l'exécution de F(W) arrête normalement (ou plante).

On prétend que BOUCLE est un problème indécidable. La démonstration, qui repose sur le principe de réductibilité au sens de Turing exposé ci-dessus, suit (plus bas).

Imaginons le problème PLANTE: écrire une fonction qui prend en paramètre le texte d'une fonction à un paramètre, et le texte décrivant ce paramètre, et qui retourne VRAI si cette combinaison fonction,paramètre plante à l'exécution, FAUX sinon.

Ses intrants seront (a) le texte (le listing) d'une fonction F(X:chaîne):chaîne en langage PASCAL, et (b) une chaîne de caractères W.

Son extrant sera booléen, soit VRAI si l'exécution de F(W) plante, et FAUX sinon.

On prétend que PLANTE est un problème indécidable. La démonstration, qui repose sur le principe de réductibilité au sens de Turing exposé ci-dessus, suit (plus bas).

Imaginons le problème PEUTPLANTER: écrire une fonction qui prend en paramètre le texte d'une fonction à un paramètre, et le texte décrivant ce paramètre, et qui retourne VRAI si cette combinaison fonction,paramètre peut planter à l'exécution, FAUX sinon.

Ses intrants seront (a) le texte (le listing) d'une fonction F(X:chaîne):chaîne en langage PASCAL, et (b) une chaîne de caractères W.

Son extrant sera booléen, soit VRAI s'il existe une chaîne w telle que l'exécution de F(w) plante, et FAUX sinon (donc si F(W) ne plante jamais, peu importe la chaîne W passée en paramètre).

On prétend que PEUTPLANTER est un problème indécidable. La démonstration, qui repose sur le principe de réductibilité au sens de Turing exposé ci-dessus, suit (plus bas).

Imaginons le problème PEUTBOUCLER: écrire une fonction qui prend en paramètre le texte d'une fonction à un paramètre, et le texte décrivant ce paramètre, et qui retourne VRAI si cette combinaison fonction,paramètre peut mener à une boucle infinie, FAUX sinon.

Ses intrants seront (a) le texte (le listing) d'une fonction F(X:chaîne):chaîne en langage PASCAL, et (b) une chaîne de caractères W.

Son extrant sera booléen, soit VRAI s'il existe une chaîne w telle que l'exécution de F(w) boucle à l'infini, et FAUX sinon (donc si F(W) ne boucle jamais à l'infini, peu importe la chaîne W passée en paramètre).

On prétend que PEUTBOUCLER est un problème indécidable. La démonstration, qui repose sur le principe de réductibilité au sens de Turing exposé ci-dessus, suit (plus bas).

Démonstration de l'indécidabilité de BOUCLE

On a démontré que ARRÊT est indécidable (plus haut). On veut prouver que ARRÊT $\leq_T$ BOUCLE, pour impliquer que BOUCLE est indécidable. La démonstration va de soi :

Function ARRET(F,W:chaîne):booléen;
   BEGIN
      SI BOUCLE(F,W)
         Alors ARRET := false;
         Sinon ARRET := true;
   END

En C++, à titre d'exemple, on écrirait simplement :

bool ARRET(const string &F, const string &W)
   { return !BOUCLE(F,W); }

Ceci correspond au sens intuitif de la définition: on sait que ARRÊT est indécidable, or on vient de démontrer que si BOUCLE était décidable, cela entraînerait que ARRÊT le soit aussi, clairement une contradiction.

D'ailleurs, il se trouve que BOUCLE $\leq_T$ ARRÊT, car :

Function BOUCLE(F,W:chaîne):booléen;
   BEGIN
      SI ARRET(F,W)
         Alors BOUCLE := false;
         Sinon BOUCLE := true;
   END

On vient donc de démontrer que ARRÊT $\equiv_T$ BOUCLE, donc que ces deux problèmes sont de difficulté équivalente.

Démonstration de l'indécidabilité de PLANTE

On a démontré que BOUCLE est indécidable (plus haut). On va démontrer que BOUCLE $\leq_T$ PLANTE,pour impliquer que PLANTE est indécidable.

Notre démonstration utilisera COMPILE, qui est décidable (on s'en souviendra) :

Function BOUCLE(F,W:chaîne):booléen;
   BEGIN
      SI NON (COMPILE (F)) Alors BOUCLE := false;
      Sinon
         BEGIN
            F2 := listing de la fonction suivante:
            F2 (X:chaîne):chaîne;
               { insérer le listing de F }
               BEGIN
                  Y := F(X);
                  Z := 1/0; { eh oui! }
               END
            Si PLANTE(F2,W)
               Alors BOUCLE := false;
               Sinon BOUCLE := true;
         END
   END

On comprendra la logique comme suit: on construit à l'interne une fonction qui plantera si elle se rend jusqu'à une instruction précise (la division par zéro). Si elle devait s'exécuter jusqu'à ce point, alors elle plante (et ne boucle donc pas à l'infini). Si elle ne plante pas, alors on sait que F(X), utilisée à l'intérieur, bouclera à l'infini.

Les cas possibles sont d'ailleurs exposés ici :

Cette fonction est une solution valide à BOUCLE utilisant PLANTE... mais nous savons que BOUCLE est indécidable; PLANTE est donc indécidable.

D'ailleurs, il est aussi vrai que PLANTE $\leq_T$ BOUCLE, donc qu'ils sont essentiellement de même complexité. On le voit ici :

Function PLANTE(F,W:chaîne):booléen;
   BEGIN
      SI NON (COMPILE (F)) Alors PLANTE := true;
      Sinon
         BEGIN
            F2 := listing de la fonction suivante:
            F2 (X:chaîne):chaîne;
               { insérer le listing de F }
               BEGIN
                  Y := F(X);
                  while TRUE do ; { eh oui! }
               END
            Si BOUCLE(F2,W)
               Alors PLANTE := false;
               Sinon PLANTE := true;
         END
   END

Le même principe s'applique que dans le cas précédent, à ceci près qu'on provoque ici volontairement une boucle infinie plutôt qu'un échec à l'exécution.

Les cas possibles sont d'ailleurs exposés ici :

Démonstration de l'indécidabilité de PEUTPLANTER

On a démontré que PLANTE est indécidable (plus haut). On va démontrer que PEUTPLANTER $\leq_T$ PLANTE, donc que PEUTPLANTER est indécidable.

On remarquera l'emploi d'une technique similaire à celles déjà utilisées ci-dessus :

Function PLANTE(F,W:chaîne):booléen;
   BEGIN
      SI NON (COMPILE (F)) Alors PLANTE := true;
      Sinon
         BEGIN
            F2 := listing de la fonction suivante:
            F2 (X:chaîne):chaîne;
               { insérer le listing de F }
               BEGIN
                  F2 := F(W)
               END
            Si PEUTPLANTER(F2)
               Alors PLANTE := true;
               Sinon PLANTE := false;
         END
   END

Les cas possibles sont d'ailleurs exposés ici :

Démontrer que PLANTE se réduit au sens de Turing à PEUTPLANTER est plus délicat. Il y a quelques stratégies qu'on ne peut se permettre d'employer.

Function PEUTPLANTER(F:chaîne):booléen;
   BEGIN
      SI NON (COMPILE (F)) Alors PEUTPLANTER := true;
      Sinon
         BEGIN
            Pour toutes des chaînes W possibles Faire
               Si PLANTE(F,W) Alors PEUTPLANTER := true;
            PEUTPLANTER := false;
         END
   END

De la même manière...

Function PEUTPLANTER(F:chaîne):booléen;
   BEGIN
      SI NON (COMPILE (F)) Alors PEUTPLANTER := true;
      Sinon
         BEGIN
            F2 := listing de la fonction suivante:
            F2 (X:chaîne):chaîne;
               { insérer le listing de F }
               BEGIN
                  Pour toutes des chaînes W possibles Faire
                     Y := F(W)
               END
            Si PLANTE(F,"n'importe quoi")
               Alors PEUTPLANTER := true;
               Sinon PEUTPLANTER := false;
         END
   END

Une démonstration qui, elle, est valide serait :

Function PEUTPLANTER(F:chaîne):booléen;
   BEGIN
      SI NON (COMPILE (F)) Alors PLANTE := true;
      Sinon
         BEGIN
            F2 := listing de la fonction suivante:
            F2 (W:chaîne; T:entier):booléen;
               { insérer le listing de F }
               BEGIN
                  Exécuter F(W), mais pas plus de T instructions
                  F2 := true;
               END
            H := listing de la fonction suivante:
            H(X:chaîne):chaîne;
               { insérer le listing de F2 }
               Pour T allant de 0 à «l'infini positif»
                  Pour toutes les chaînes W de longueurs <= T faire
                     C := F2(W,T);
            Si PLANTE(H,"n'importe quoi")
               Alors PEUTPLANTER := true;
               Sinon PEUTPLANTER := false;
         END
   END

Les cas possibles sont d'ailleurs exposés ici :

Lectures complémentaires

Quelques liens pour enrichir le propos.

• Pour des défis d'ordre informatique, voir ../Orthogonal/Petits-defis.html
• Pour les intéressé(e)s, la revue PhysicsWeb a tenu en 2004 un concours pour répertorier des plus importantes équations de l'histoire. Vous pouvez, si vous en avez envie, consulter un résumé du vote des gens, ou encore un article plus complet sur le sujet.
• Je vous invite aussi à lire l'essai de Paul Graham sur la bonne et la moins bonne procrastination. Il y a là de quoi réfléchir si oeuvrer sur des problèmes fondamentaux vous intéresse ou si, au contraire, cela vous intimide.
• Plus récemment, un Wiki portant sur les problèmes du millénaire (autre source ici) a été mis en place pour encourager un effort collaboratif de solution. Voir http://www.qeden.com/wiki/Main_Page pour plus de détails
• Pour en savoir plus sur les gens qui ont solutionné certains problèmes de Hilbert, sur les problèmes eux-mêmes (du moins en surface) et sur ceux qui restent à résoudre aujourd'hui, je vous suggère le fort intéressant livre The Honors Class: Hilbert's Problems and Their Solvers (et, pour un regard plus spécifique sur le problème de la fonction Zeta de Riemann, je vous recommande le volume Prime Obsession).
• Le site http://mathworld.wolfram.com/ a mis en ligne une liste de problèmes importants et non résolus en mathématiques, qui donnent souvent sur la ligne entre l'informatique et les mathématiques.
• Un problème ouvert de taille moyenne (de ce qu'on en sait, du moins; des fois, avec ces problèmes, on a des surprises!) sur les fondements de l'informatique est proposé sur http://www.wolframscience.com/prizes/tm23/
• Autre site sur les problèmes intéressants : http://projecteuler.net/
  • à ce sujet, Brian Danger Graham, en 2012, explique comment il a décidé d'affronter ces problèmes : http://cowbelljs.blogspot.com/2011/12/projecteuler-001.html
• Un petit (!) défi : http://bit-player.org/2009/the-17x17-challenge
• Une preuve de l'impossibilité d'analyser Perl étant donné sa structure, analogue aux preuves d'indécidabilité proposées plus bas : http://www.perlmonks.org/?node_id=663393
• Un regard historique sur la résolution du théorème de Fermat, un article de Marianne Freiberger en 2013 : http://plus.maths.org/content/very-old-problem-turns-20
• En 2015, texte de Nicholas Chapman montrant qu'écrire une fonction capable d'optimiser la longueur d'un programme entre dans la même catégorie de problèmes indécidables : http://www.forwardscattering.org/post/20
• Texte de 2016 par Richard Lipton et Ken Regan, portant sur des problèmes non-résolus en philosophie qui recoupent des préoccupations mathématiques : https://rjlipton.wordpress.com/2016/01/07/you-think-we-have-problems/

[1] Qui, elle, a été démontrée.