UN VIEUX RÊVE DEVIENT RÉALITÉ

1En 1936, le mathématicien britannique Alan Turing et le logicien américain Alonzo Church proposèrent, indépendamment l’un de l’autre, et presque simultanément, la définition mathématique de ce que l’on entend aujourd’hui par fonction numérique calculable. Bien que différentes dans leurs formes, ces deux définitions s’avérèrent identiques dans leur signification, exprimant un concept fondamental qui était dans l’air du temps. La percée de Turing et de Church ouvrit la voie à l’étude rigoureuse de la calculabilité, théorie qui est encore très vivante de nos jours.

2L’idée de construire une machine pour exécuter des opérations arithmétiques s’est présentée à l’esprit de nombreux scientifiques, ingénieurs et philosophes en des époques et des lieux différents au cours de l’histoire de l’humanité. Il semble que le premier à avoir mis cette idée en pratique fut l’astronome allemand Wilhem Schickard. Contemporain de Kepler, celui-ci construisit en 1623 ce qu’il appela « une pendule à calculer », capable d’effectuer des additions, des soustractions, des multiplications et des divisions par des moyens entièrement mécaniques. Mais l’invention de Schickard fut de courte durée : un an plus tard, un incendie la détruisit. Dans son Histoire universelle des chiffres, Georges Ifrah1 a émis l’hypothèse que l’incendie n’aurait pas été le résultat d’un accident, mais aurait été un geste délibéré pour empêcher la machine de calculer—faculté qui était alors considérée par les pouvoirs obscurantistes comme une prérogative exclusive de l’esprit humain. Peu de temps après, en 1642, Biaise Pascal, alors qu’il n’avait que dix-neuf ans, construisit une machine à additionner—la pascaline—pour aider son père dans sa comptabilité. Les automates à engrenages comme celui du savant français avaient pour objet principal de libérer l’astronome, le comptable ou l’ingénieur de la tâche fastidieuse (et toujours sujette à l’erreur) de faire à la main d’interminables manipulations numériques. Au cours des années, ces machines allaient aussi permettre aux gens ordinaires de pratiquer l’art de l’arithmétique sans avoir besoin d’apprendre des règles de calcul compliquées.

3Beaucoup d’autres essais pour réaliser le rêve du calcul mécanique suivirent. Mais le titre de père du calcul artificiel revient au mathématicien anglais Charles Babbage qui, au début du XIX^e siècle, conçut les principes théoriques et pratiques d’un mécanisme de calcul automatique, véritable précurseur des ordinateurs d’aujourd’hui. (Il passa ensuite les cinquante dernières années de sa vie à essayer, mais sans succès, d’en construire un.)

4Si les créations ingénieuses de Babbage ne furent jamais viables, d’aucuns en attribuent la cause aux limites techniques de l’ingénierie mécanique de l’ère victorienne, et tout particulièrement à un manque d’outillage suffisamment précis pour fabriquer les composantes de ses « engins » (comme il les appelait). L’Engin Différentiel de Babbage, par exemple, aurait pesé plusieurs tonnes, et ses quelque vingt-cinq mille pièces, une fois assemblées en un système précis d’engrenages, de crémaillères, de cames et de leviers, auraient fait 2,4 m de haut, 2,1 m de long et 1 m de large. À l’origine, le but de la machine, qui fut l’ancêtre de son Engin Analytique plus perfectionné, était de calculer les tables de navigation et d’autres tables arithmétiques. Ces machines étaient de plus en plus demandées par les ingénieurs, les banquiers et les marchands dans le monde en développement rapide du commerce et de l’industrie. En fait, si l’automatisation des calculs motiva Babbage, ce fut moins pour l’amélioration du procédé que pour sa garantie de précision. Sa machine était censée fournir un moule dans lequel les plaques des clichés des tables de calcul pouvaient être coulées en vue de prévenir les erreurs d’imprimerie si fréquentes dans les tables composées manuellement. Moins de vingt ans après la Révolution française, l’idée de la composition automatique était née.

5Avec le temps, d’un prototype inachevé à l’autre, Babbage combina dans ses inventions les principales idées à partir desquelles sont construits les ordinateurs numériques modernes, notamment les cinq unités de base : (a) la mémoire où sont stockées les données, les instructions et les calculs intermédiaires ; (b) le processeur (ou moulin) « dans lequel, selon ses propres mots, les quantités sur lesquelles se font les opérations sont toujours acheminées » ; (c) une unité qui contrôle l’opération d’ensemble (par le moyen d’un système de métier à tisser du type Jacquard) ; (d) l’entrée (par des cartes perforées) ; et (e) la sortie, qui automatiquement imprime les résultats. Ces principes fondamentaux furent oubliés par la suite, pour être redécouverts au milieu du XX^e siècle. En janvier 1943, soit plus de cent ans après que Babbage ait, le premier, imaginé un appareil à calculer automatique et multifonctionnel, une vraie machine présentant les mêmes caractéristiques fut finalement réalisée. Conçue par Howard Aiken, professeur de physique à l’Université Harvard, et construite avec l’aide des ingénieurs de IBM, cette machine, le Harvard Mark I, fonctionnait sur les principes inspirés de ceux de l’Engin Analytique de Babbage.

6« Charles Babbage a toujours adopté une approche mathématique pour chacun des nombreux problèmes auxquels il s’attaquait », écrit J. M. Dubbey dans The Mathematical Works of Charles Babbage. Et d’ajouter : « Il a toujours essayé de formuler un problème de façon aussi mathématique que possible, aussi bien pour discuter des miracles que de la fabrication des aiguilles, des services postaux, de la géologie, de l’économie, de la politique, ou de sa vie privée. »

7À la fois visionnaire et génie pratique, Babbage a prédit l’extraordinaire succès des machines à calculer—celles des autres, à défaut des siennes propres. « Si je vis encore quelques années, écrivait-il sept ans avant sa mort en 1871, l’Engin Analytique naîtra et ses avantages se répandront plus tard partout dans le monde. »

LES MACHINES PEUVENT-ELLES TOUT CALCULER ?

8Les ordinateurs peuvent faire des choses étonnantes, mais d’un point de vue mathématique nous ne nous intéressons qu’aux fonctions qu’ils calculent. Par une fonction/, nous entendons le fait d’associer à chaque nombre n un seul nombre f(n)—appelé la valeur de/en n—précisée en règle générale par une formule algébrique (pour plus de simplicité, tous nos nombres seront des nombres naturels). Par exemple, f(n) = n²+n+41 définit une fonction qui apparie 1 et 43 (=1²+1 + 41), 2 et 47 (=2²+2+41), et ainsi de suite. (En fait, les trente-neuf premières valeurs de cette fonction sont des nombres premiers, mais ceci n’a rien à voir.)

9Nous pouvons aussi définir une fonction en utilisant des mots et convenir par exemple que p(n) est le nombre de nombres premiers inférieurs ou égaux à n. Nous avons alors p(7) = 4—comme on peut facilement le constater—et p(4 x10¹⁶) = 1 075 292 778 753 150 —tel qu’on peut moins aisément le vérifier. Le calcul de f(n) et p(n) peut facilement se faire sur un ordinateur, et puisque ces machines furent inventées en vue d’aider les scientifiques dans leur traitement des nombres, il n’est pas surprenant qu’elles puissent aussi calculer des fonctions beaucoup plus complexes. Mais peuvent-elles calculer n’importe quelle fonction ? Cette question n’est pas seulement théorique, car la capacité des ordinateurs à résoudre des problèmes dépend de la classe des fonctions qu’ils peuvent effectivement calculer.

10C’est Alan Turing qui a répondu à la question soulevée ci-dessus en 1936, presque 10 ans avant la naissance du premier ordinateur—le Electronic Integrator and Calculator (ENIAC)—à la Moore School of Engineering de Philadelphie. À l’époque, Turing ne s’occupait pas des appareils pratiques tels que les machines à calculer, bien qu’il ait travaillé après la guerre à la mise au point d’un ordinateur électronique. Son article sur les « nombres calculables ^»2 se voulait une solution au problème mathématique qu’avait posé l’un des plus célèbres mathématiciens du siècle. Mais l’article de Turing montrait en même temps qu’il y a des limites au calcul automatique, à savoir une sorte de « loi naturelle » à laquelle ne peuvent échapper les ordinateurs numériques, même les plus puissants.

11Chaque fois que nous résolvons un problème sur un ordinateur, la machine transforme en solution les données du problème par l’exécution d’un ensemble d’instructions, c’est-à-dire d’un programme. En dernière analyse, les données et la solution sont constituées de chaînes de 0 et de 1 que nous pouvons interpréter comme étant l’encodage de nombres naturels— qui peuvent être très grands. Ainsi, d’un point de vue conceptuel, les programmes d’ordinateurs sont des recettes pour calculer des fonctions, puisque leur exécution transforme les nombres naturels (données d’entrée) en d’autres nombres naturels (données de sortie). C’est en ce sens que la classe des problèmes que les ordinateurs peuvent résoudre dépend en fin de compte de la nature des fonctions qu’ils peuvent calculer.

TURING ET SES MACHINES

Imaginons que les opérations accomplies par un ordinateur soient divisées en des « opérations simples » qui sont tellement élémentaires qu’il n’est pas facile d’imaginer qu’elles puissent être simplifiées davantage.
(Alan Turing analysant la manière dont un ordinateur humain effectue un calcul)3.

12Durant l’été 1935, Alan Turing, alors jeune diplômé de Cambridge, se mit à réfléchir sur une question concernant les fondements des mathématiques qu’avait soulevée, quelques années auparavant, l’éminent mathématicien allemand David Hilbert. Y a-t-il un test ou un processus mécanique qui, appliqué à un énoncé mathématique arbitraire, permet de découvrir si l’énoncé est vrai ou faux ? Celui qui essaie de répondre à cette question doit d’abord élucider la notion vague mais fondamentale de « processus mécanique ». Cela amena Turing à se demander quel était le genre de « machine » capable de traiter les symboles utilisés par quelqu’un en n’ayant pour calculer qu’un crayon et un papier, mais sans posséder les facultés spécifiquement humaines comme l’intelligence, l’intuition et l’imagination, et sans les non moins humaines faiblesses que sont la fatigue, la faim ou l’ennui.

13Calculer se fait normalement en écrivant certains symboles sur une feuille de papier, disait Turing4. « Supposons que cette feuille soit divisée en carrés comme dans un cahier d’arithmétique pour enfants. En arithmétique élémentaire, on utlise parfois le caractère bidimensionnel de la feuille, mais ce n’est pas essentiel au calcul. Dès lors, je présume que le calcul est exécuté sur une feuille unidimensionnelle, plus précisément sur un ruban divisé en carrés. Je suppose aussi que le nombre de symboles qui peuvent être imprimés est fini. »

14Turing avait à l’esprit un dispositif idéal pour manipuler certains symboles (les reconnaître, les noter, les effacer, etc.), dont le fonctionnement était automatique, c’est-à-dire complètement déterminé à l’avance. Quelques mois plus tard, il suggéra l’idée d’un modèle théorique simple d’ordinateur, qu’on appelle aujourd’hui la machine de Turing. Il avait aussi trouvé la réponse à la question de Hilbert (mais cela fait partie d’une autre histoire, sur laquelle nous reviendrons plus tard).

15Contrairement aux ordinateurs réels, les machines idéales de Turing peuvent fonctionner sans être entravées par des limites de temps ou d’espace de mémoire. Elles fournissent un test standard (et précis) à la notion intuitive de « calculabilité » : une fonction/sera appelée calculable si chacune de ses valeurs f(n) peut être produite par les opérations « mécaniquesniques » d’une machine de Turing.

FIGURE 2.1

16Nous pouvons imaginer une machine de Turing composée d’une tête de lecture/d’écriture et d’un ruban bidimensionnel quelle utilise comme bloc-notes (figure 2.1). Le ruban s’étend indéfiniment dans les deux directions et se divise en cellules qui peuvent contenir un des deux symboles 0 ou 1 (il serait commode de penser 0 comme représentant une cellule vierge ou vide). À n’importe quel stade du calcul, la tête scrute l’une des cellules et n’est en mesure d’accomplir qu’une des quatre choses suivantes : écrire un 1 (ou un 0) sur la cellule (effaçant ainsi le contenu précédent de la cellule) ; se déplacer vers la cellule suivante à droite ; ou se déplacer vers la cellule suivante à gauche. Celle de ces actions qui aura lieu va dépendre du « programme » de la machine—à savoir l’ensemble des instructions dont la machine de Turing est pourvue. Ces instructions doivent être écrites dans un format standard. Ce qui suit en est un exemple :

17# 788 : « Si le symbole repéré est 1, alors déplacez (une cellule) vers la gauche et ensuite exécutez l’instruction #559. »

18On peut coder succinctement la consigne ci-dessus sous (# 788, 1, L, # 559). Plus généralement, le format d’une instruction codée est :

19(n^o de l’instruction, symbole [repéré], action, n^o de l’instruction [suivante])

20Un programme pour une machine de Turing est n’importe quel ensemble d’instructions codées de cette manière (l’ordre dans lequel les instructions sont listées n’étant pas pris en considération). Comme exemple simple, supposons que le programme est constitué des cinq instructions suivantes :

(# 1,1, R, # 2)
(# 2, 0,1, # 2)
(# 2,1, L, # 3)
(# 3, 0,1, # l)
(# 1, 0,1, # 3)

21Lorsque la machine est mise en marche, il y a une certaine chaîne binaire (les données) écrite sur le ruban, la tête scrutant une des cellules. Supposons que la tête soit en train de lire un 1, tandis que le reste du ruban est vierge. Dès lors, on obtient la séquence d’opérations suivante. La première instruction à exécuter est l’instruction # 1. Il est à remarquer qu’il y a deux instructions # 1, mais une seule d’entre elles correspond au cas où le symbole repéré est 1. Ainsi cette instruction—(# 1,1, R, # 2) —est exécutée en faisant en sorte que la tête se déplace d’une cellule vers la droite, puis « aille au # 2 », c’est-à-dire exécute (# 2,0,1, # 2), puisque le symbole qui est maintenant en train de lire est 0. L’exécution de cette instruction fait que 0 est remplacé par 1 et puis—encore—« va au # 2 ». L’instruction correspondant à la présente situation est maintenant (# 2,1, L, # 3), de telle sorte que la tête se déplace en direction de la cellule suivante vers la gauche (qui contient le 1 de départ) et ensuite cherche l’instruction # 3. Mais aucune instruction ne commence par (# 3, x,...) ; donc, le calcul s’arrête.

22Bien entendu, toute cette activité n’a lieu que de façon figurative. Tout le processus aurait pu être formulé en langage mathématique, mais il est plus facile de le concevoir comme une machine exécutant des instructions. Le ruban de sortie contient maintenant deux 1 consécutifs—le reste étant demeuré vierge. Différentes configurations du ruban d’entrée au début du calcul vont généralement entraîner différents rubans de sortie. Par exemple, si le ruban initial avait été totalement vierge, la tête aurait écrit un seul 1 et se serait alors arrêtée.

23En cours de calcul, la machine de Turing a une quantité illimitée de cellules pour lire, écrire et stocker l’information. Les ordinateurs numériques, d’autre part, n’ont qu’un nombre fixe de bits de mémoire. Et tandis que les ordinateurs réels doivent livrer des données de sortie en un délai raisonnable, une machine de Turing n’a pas une telle limite de temps pour donner sa réponse. Il est à noter, cependant, que cette réponse—si réponse il y a—arrivera après un intervalle de temps fini (T unités de temps, si l’unité est choisie comme le temps requis pour exécuter une instruction), intervalle pendant lequel la tête aura lu (ou écrit sur) un nombre fini (N) de cellules. T et N peuvent être des nombres arbitrairement grands, mais non l’infini. Même si des machines idéales comme celles de Turing ne pourront jamais être construites, leur étude est importante parce qu’elles fournissent une limite supérieure à la puissance de calcul des ordinateurs réels.

LES FONCTIONS CALCULABLES

24L’exemple élémentaire que nous venons de présenter n’est pas très révélateur de ce que les machines de Turing sont capables d’accomplir. Par comparaison avec les ordinateurs d’aujourd’hui, les machines de Turing peuvent paraître primitives, à tel point que le plus modeste PC semble considérablement plus puissant. Toutefois, comme nous le verrons bientôt, il y a beaucoup plus de choses dans ces machines que ce qui peut apparaître à première vue. En particulier, elles sont étonnamment efficaces pour calculer des fonctions. Les paragraphes qui suivent vont expliquer de quelle manière elles y parviennent.

25Supposons que, chaque fois que nous démarrons une certaine machine de Turing avec un nombre n écrit (dans un quelconque format standard) sur son ruban, la machine finisse par s’arrêter, et que, quand cela arrive, le ruban contient le nombre f(n) (encodé dans le format standard). Dans ce cas, nous disons que ladite machine de Turing calcule la fonction f(n). Par exemple, si une machine de Turing prend comme données d’entrée un bloc de n 1 consécutifs et le double—ce qui fait que la bande de sortie contient un bloc de 2n 1 consécutifs,—nous dirons que la machine calcule la fonction f(n) = 2n. Toute fonction qui peut être calculée par une machine de Turing sera considérée comme calculable. Cette définition est tellement importante qu’il vaut la peine de l’énoncer :

26Une fonction de nombres naturels est dite calculable si elle peut être calculée par une machine de Turing.

27Afin que cette définition soit totalement non équivoque, nous devons préciser certaines choses : comment encoder les données d’entrée sur la bande ? quelle cellule la tête doit-elle scruter lorsque débute le calcul ? et ainsi de suite. Il y a plusieurs moyens de faire tout ceci, mais le choix concret d’un protocole de calcul est sans importance, parce qu’il s’avère que ce sont exactement les mêmes fonctions qui sont calculables, quelles que soient les conventions (raisonnables) adoptées. Ce qui importe, c’est de se rendre compte que, dès qu’un protocole particulier est choisi, chaque machine de Turing calcule une fonction unique.

28Il se peut que, pour certaines données d’entrée, une machine de Turing ne puisse jamais terminer son calcul, et que, même si elle le faisait, il y ait une chaîne de symboles dénuée de sens écrite sur son ruban final. Dans l’un et l’autre cas, nous dirons que la fonction calculée par la machine n’est pas définie pour ces données d’entrée. Pour cette raison, les fonctions calculées par les machines de Turing sont, en général, des fonctions partielles—des fonctions/qui n’attribuent aucune valeur f(n) à certains nombres n.

29On peut prétendre, comme Turing lui-même l’a fait, que la notion de machine de Turing renferme les caractéristiques essentielles correspondant à notre idée intuitive de « processus mécanique » ou d’« algorithme ». Si nous acceptons ce fait, alors pour montrer qu’une fonction/est calculable, il suffit de décrire une manière de calculer f(n) qui est « mécanique » dans un sens intuitif -puisqu’une telle méthode pourrait alors être codée comme un ensemble d’instructions pour une machine de Turing. Voici un exemple. Dans tout cercle, le rapport de la circonférence au diamètre est le fameux nombre  (= pi =3,14159...). Soit f(n) la nième décimale de , à savoir f(1) = 1, f(2) = 4, f(5) = 9, et ainsi de suite. Or  est un nombre irrationnel, ce qui veut dire que ses décimales ne suivent aucun modèle prévisible. Il y a, cependant, plusieurs algorithmes qui calculent systématiquement les décimales de  l’une après l’autre. Dès lors, pour calculer, disons f(1 000 000), nous pouvons faire marcher l’un des ces algorithmes jusqu’à ce qu’il imprime la millionième décimale. Puisqu’une telle méthode calcule « mécaniquement » f(n) pour un « arbitraire, f est calculable.

30Considérons maintenant une autre fonction, g, qui est une fonction partielle parce qu’elle n’est définie que pour » allant de 1 à 9. Par définition, g(n) = 1, s’il y a un bloc de » chiffres consécutifs « « » dans la partie décimale de  ; par contre, s’il n’existe aucun bloc semblable, alors g(n) = 0. Par exemple, il est évident que g(1) = 1—il y a un « 1 » (en fait, la première décimale) ; g(2) est soit 1 ou 0 ; c’est 1 si quelque part dans la partie décimale de  il y a un bloc de deux « 2 » consécutifs, c’est-à-dire, si  = 3,14159...22... Mais s’il n’existe pas de bloc « 22 », alors g(2) = 0.

31La fonction g est-elle oui ou non calculable ? Nous pouvons essayer de la calculer en faisant tourner l’algorithme qui calcule/, mais il y a un problème. Pour calculer, disons, g(4), nous devons découvrir si oui ou non le bloc « 4444 » apparaît dans la partie décimale de Π Si un tel bloc existe, nous finirons par l’apprendre, car l’algorithme l’imprimera tôt ou tard ; mais si aucun bloc « 4444 » n’existe, l’algorithme le cherchera en vain et le calcul de g(4) ne s’achèvera jamais. Par conséquent, nous ne pouvons pas garantir à priori que notre méthode calculera g(n) pour chaque n dans un délai fini ; nous sommes donc incapables de régler la question de la calculabilité de g par l’approche ci-dessus. Et pourtant g est calculable ; mais nous mettons le lecteur au défi de le prouver. Quant au lecteur impatient... il ou elle peut se rendre immédiatement à la section « Solution de l’énigme ».

LES FONCTIONS NON CALCULABLES

32Toutes les fonctions définies par une formule explicite impliquant les opérations d’addition, de multiplication et d’élévation à une puissance sont calculables, par exemple f(n) = n³+4n²+1 et g(n) = (n+10)ⁿ. (Il y a des problèmes techniques avec la soustraction et la division, puisque nous nous limitons aux nombres naturels, mais ces problèmes peuvent être surmontés.) Les fonctions spécifiées par des procédés de récurrence, lesquels utilisent des valeurs précédemment calculées pour établir les nouvelles valeurs f(n), s’avèrent également calculables. Un exemple célèbre est la séquence 1, 1, 2, 3, 5, 8, 13,... que Leonardo Fibonacci, mathématicien italien du XIII^e siècle, a introduite en étudiant la façon dont les lapins se reproduisent. La séquence de Fibonacci commence par deux 1 consécutifs, chaque entrée successive étant la somme des deux précédentes. En symboles :

f(1) = 1 ; f(2) = 1 et f(n) = f(n-1) +f(n-2), pour n3

33Ainsi, f(3) =f(2)+f(1) = 2 ; f(4) =f(3) + f(2) = 3, et ainsi de suite.

34En fait, toute fonction qu’un non-mathématicien peut rencontrer au cours de sa vie est assurément calculable. Mais toutes les fonctions sont-elles calculables ? L’expression fonction calculable est-elle un pléonasme ? Un simple argument montrera que la réponse à ces questions est négative.

35Rappelons-nous que chaque machine de Turing est accompagnée de son propre programme, autrement dit elle est conçue de façon à obéir à un certain ensemble d’instructions. Si nous voulons exécuter un autre programme, il nous faudra une autre machine (ceci n’est rien de plus qu’une convention et ne constitue certainement pas un gaspillage de « machines »). Une conséquence de cette convention est que chaque machine de Turing calcule une seule fonction. Mais est-ce que chaque fonction est calculée par une quelconque machine de Turing ?

36Bien qu’il y ait un nombre infini de machines de Turing, nous pouvons toutes les ranger dans une liste (virtuelle). Par exemple, puisqu’une machine de Turing est totalement caractérisée par une chaîne finie de symboles—son programme-, nous pouvons (tout au moins en principe) énumérer toutes les machines de Turing en inventoriant systématiquement tous les programmes possibles P₁, P₂, P₃,... dans une sorte d’ordre alphabétique. (Si A est un ensemble fini de symboles, disons A = {a, b, c}, alors les chaînes finies de symboles de A peuvent être disposées « alphabétiquement » sur une liste infinie : a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab,... etc.)

37D’autre part, les fonctions des nombres naturels ne peuvent pas être toutes inscrites sur une liste, même pas en principe. Un ingénieux argument mathématique peut prouver cette impossibilité. L’essentiel de cet argument se présente comme suit : vous me donnez une liste de fonctions, et je vous montre une fonction qui ne figure pas sur votre liste ; donc votre liste est incomplète (pour le développement de cet argument, voir l’appendice 2). Le résultat est qu’il y a plus de fonctions que de machines de Turing pour calculer celles-ci. Bref, il existe des fonctions non calculables.

38Que nous ayons eu recours à une preuve indirecte pour établir l’existence de fonctions non calculables a peut-être laissé le lecteur perplexe. N’aurait-il pas été plus facile—et certainement plus éclairant—de montrer une telle fonction ? Le problème est qu’il n’est facile ni de définir ni de découvrir des fonctions non calculables. Et même s’il nous arrivait d’en trouver une, il pourrait être difficile de prouver que la fonction n’est pas calculable, aussi difficile que de prouver que certains problèmes n’ont pas de solution. En fait, les deux questions sont étroitement liées.

UN PROBLÈME INSOLUBLE

39Puisqu’il existe des fonctions non calculables, nous devons nous attendre à ce que les machines de Turing soient incapables de résoudre certains problèmes. Il est bien entendu possible que tous ces problèmes insolubles soient tout simplement des curiosités théoriques, dépourvues du moindre intérêt pratique. En réalité, l’une des questions auxquelles les machines de Turing ne peuvent répondre est d’ordre très pratique, étant donné qu’elle concerne la vérification automatique d’un logiciel. Il s’agit de décider si l’exécution d’un programme d’ordinateur arbitraire doit finalement s’arrêter ou s’il est condamné à toujours tourner.

40Comme nous l’avons déjà indiqué, certaines machines de Turing peuvent ne jamais s’arrêter de tourner. Pour prendre un exemple banal, considérons la machine de Turing dont la seule instruction est (# 1, 0, R, # 1). Si le ruban initial est vierge, la machine continuera d’obéir indéfiniment à sa seule instruction, déplaçant perpétuellement sa tête vers la prochaine cellule sur la droite le long de son ruban infini (quelqu’un a appelé cette machine la « touring machine »). Imaginons maintenant une machine de Turing arbitraire contrôlée par des milliers d’instructions. Sera-t-il possible de prédire si oui ou non ses calculs s’arrêteront jamais ? Ce casse-tête s’appelle le problème de l’arrêt. Il consiste à trouver le moyen de répondre (correctement) par oui ou par non à la question suivante : si une machine de Turing T démarre sur un ruban d’entrée donné, va-t-elle finalement terminer ses calculs ?

41En termes concrets, supposons que nous cherchions un dispositif (une machine, une boule de cristal, un oracle...) capable de donner la bonne réponse à la question ci-dessus pour toutes les machines de Turing T. Si une telle chose peut exister, ce ne peut être une machine de Turing. Autrement dit, il est impossible d’écrire un programme pour une machine de Turing —disons H—qui puisse fonctionner comme suit : H accepte comme donnée d’entrée l’ensemble des instructions d’une machine de Turing arbitraire T en même temps que le contenu de sa bande initiale (toutes ces données encodées de manière appropriée) et produit comme donnée de sortie « oui », si T finit par s’arrêter, et « non », si T continue sa marche indéfiniment. En d’autres termes, cela signifie que H est capable de prédire si oui ou non une machine de Turing donnée s’arrêtera un jour de fonctionner.

42Hélas ! H ne peut pas exister. Car, si cette machine existait, elle entraînerait une contradiction logique (voir l’appendice 3 pour plus de détails). Et donc, quel que soit le moyen de distinguer les machines de Turing qui mettent fin à leurs calculs de celles qui ne le font pas, cette opération ne pourrait se faire sur une machine de Turing. En un mot : le problème de l’arrêt n’est résoluble sur aucune machine de Turing.

LA FOURMI, LE BULLDOZER ET LES LIMITES DE LA CALCULABILITÉ

43Les ordinateurs sont de formidables machines à calculer, avec leurs processeurs ultra-rapides en parallèle, leurs mémoires vives, etc. Par comparaison, les machines de Turing, qui se traînent en avançant une cellule à la fois, semblent être des modèles d’inefficacité (elles peuvent se permettre d’être inefficaces, puisqu’elles disposent de ressources inépuisables—temps, papier, encre, etc.). C’est pourquoi le fait que certaines fonctions ne peuvent être calculées par les machines de Turing ne semble pas constituer une limite sérieuse, car il est concevable que ces fonctions puissent être calculées par d’autres appareils plus puissants.

44Peut-être bien. Mais, quels qu’ils puissent être, ces « appareils » ne peuvent ressembler à nos ordinateurs familiers. Malgré toute leur puissance et leur rapidité impressionnantes, les ordinateurs numériques ne sont en fait que de vulgaires machines de Turing—avec l’inconvénient supplémentaire des contraintes de temps et d’espace. Cette faiblesse des ordinateurs numériques s’explique assez simplement : puisque leur fonctionnement cadre avec la description d’un « processus mécanique », il peut être reproduit par une machine de Turing. Bien sûr, la modeste machine de Turing peut avoir à exécuter des milliers d’opérations très élémentaires dans le but d’accomplir ne serait-ce qu’une simple multiplication. À la fin, cependant, le résultat sera le même, qu’il ait été obtenu efficacement par une vraie machine ou calculé laborieusement par une machine idéale. C’est comme déplacer un tas de sable d’un endroit à un autre. Une simple fourmi transportant un grain à la fois peut en principe accomplir la même tâche aussi sûrement que ne peut le faire un bulldozer. Ainsi, tout ce qu’un ordinateur peut faire peut être fait également par une machine de Turing. Ce qui nous conduit à une conclusion inévitable : ces fonctions qu’aucune machine de Turing ne peut calculer demeurent non calculables par n’importe quel ordinateur numérique—actuel ou futur.

45Outre celle de Turing, d’autres définitions ont été proposées pour rendre mathématiquement précise l’idée intuitive de calculabilité. Il s’avère, cependant, qu’elles sont toutes équivalentes, c’est-à-dire qu’indépendamment de celle que nous adoptons, l’ensemble des fonctions calculables sera toujours le même. Cet état de choses a poussé le logicien américain Alonzo Church à énoncer ce qu’on appelle la thèse de Church : toutes les fonctions calculables dans un sens intuitif sont calculables sur une machine de Turing.

46Professeur à l’Université Princeton, Church avait travaillé sur la question de Hilbert à peu près au même moment que Turing. Recourant à des méthodes passablement différentes, et chacun ignorant les efforts de l’autre, les deux mathématiciens parvinrent à la réponse presque simultanément, des deux côtés de l’Atlantique. Ce que Church appelait « effectivement calculable » [calculable] correspondait à la notion de « calculable » [computable] chez Turing—c’est-à-dire à tout ce qui peut être calculé [computed] par une machine de Turing. Quelques années plus tard, les anciens « rivaux » travaillèrent ensemble à Princeton.

47La thèse de Church est toujours valable, car personne n’a encore trouvé une fonction qu’on pourrait raisonnablement appeler « calculable » qui ne pourrait pas être calculée par une machine de Turing. Si la conjecture de Church est exacte—et les faits jusqu’à maintenant semblent le démontrer—alors les fonctions qu’aucune machine de Turing ne peut calculer sont également non calculables dans un sens absolu.

LEVER LE VOILE SUR LES FONCTIONS NON CALCULABLES

48Les fonctions non calculables ne constituent pas quelque chose d’occulte, de trop mystérieux pour être envisagées par un profane. La question est plutôt de savoir où les trouver. Un moyen sûr de tomber sur l’une d’elles est d’essayer de « calculer » la solution d’un problème qu’aucune machine de Turing ne pourra résoudre. Nous connaissons déjà un puzzle de ce genre, celui qui consiste à vérifier si oui ou non une machine de Turing arbitraire s’arrêtera jamais de calculer. Tout ce qui nous reste à faire maintenant est de traduire ce problème de l’arrêt dans le langage des fonctions.

49La technologie de la communication d’aujourd’hui se fonde sur la numérisation de l’information, l’encodage des textes, des images et des sons en chaînes de o et de 1 sur un support approprié (disquette, disque compact, etc.). Le processus est, bien sûr, réversible, car nous pouvons retrouver le texte ou le son à partir de sa forme codée (en lisant la disquette ou en faisant jouer le disque compact). En plus, l’encodage/décodage est totalement automatique, puisqu’il est fait par des machines.

50De la même manière, il est en principe possible d’encoder automatiquement le programme de n’importe quelle machine de Turing comme un seul nombre naturel. Ceci peut se faire, par exemple, en convertissant d’abord chacun des symboles nécessaires pour écrire les programmes d’une machine de Turing en un code à deux chiffres. Voici une table de conversion possible :

51Ensuite, étant donné un programme P pour une machine de Turing, nous pouvons obtenir un nombre naturel en remplaçant les symboles (dans l’ordre où ils apparaissent dans P) par leurs codes à deux chiffres et en lisant finalement la chaîne qui en résulte comme un nombre décimal. Ainsi, le programme à une seule instruction (# 1, 0, R, # 1) devient le nombre 1 214 011 500 151 115 140 113. (Nous ne prétendons pas que le système d’encodage ci-dessus soit le plus efficace qui existe.)

52Il est clair que le programme original peut être restitué à partir de son chiffre codé par un décodage (automatique) approprié. Il est à noter que, tandis que chaque machine de Turing a un chiffre correspondant (le chiffre codé de son programme), certains nombres naturels k peuvent n’encoder aucun programme—ce qui veut dire que le décodage de k ou bien produira une chaîne de symboles dépourvue de sens ou bien rien ; en d’autres mots, tout sauf le programme d’une machine de Turing. Par exemple, 1 110 071 212 se décode comme RL7 (((dépourvu de sens), tandis que 789 999 555 333 ne se décode pas du tout. S’il arrive qu’un chiffre m est le chiffre codé d’une machine de Turing, nous désignerons cette machine par T(m).

53Nous définissons maintenant la fonction h à deux variables comme suit : pour une paire donnée (m, n) de nombres naturels, h(m, n) = 1, si m est le code d’une machine de Turing et si cette machine—T(m)— finit par s’arrêter après avoir été démarrée avec le nombre n sur sa bande d’entrée. Dans tous les autres cas—c’est-à-dire si m n’est pas le code d’une machine de Turing ou si T (m) existe mais ne cessera jamais de calculer sur l’entrée n -, nous posons h(m, n) = 0. Encore une fois : h(m, n) = 1, si T(m) existe et finit par s’arrêter lorsque celle-ci est démarrée sur l’entrée n ; et h(m, n) = o, dans les autres cas.

54Comment pouvons-nous être sûrs qu’aucune machine de Turing ne calcule h ? Parce que, comme nous le montrons dans l’appendice 3, l’hypothèse qu’une machine de Turing calcule effectivement h mène tout droit à une contradiction logique. Cette méthode de preuve par l’absurde (reductio ad absurdum) est une des meilleures alliées du mathématicien.

COMPLEXITÉ

55Les résultats obtenus par Turing imposent une limite théorique à ce que ses machines idéales—et, à fortiori, les ordinateurs réels—peuvent calculer. Mais, comme on a pu le constater dans la pratique, il y a largement place, à l’intérieur de ces limites, pour le calcul de solutions à toutes sortes de problèmes. La vraie question est plutôt de savoir comment effectuer, par un moyen efficace, les nombreuses tâches que peuvent accomplir les ordinateurs numériques. Contrairement aux vrais ordinateurs, les machines de Turing n’ont aucune limite de temps ou d’espace de mémoire pour calculer leurs réponses. Par conséquent, même si un problème est résoluble sur une machine de Turing, il n’est pas certain qu’il puisse l’être, en fait, sur un ordinateur (dans le cas, par exemple, où la réponse prendrait des milliers d’années).

56Les mathématiciens et les informaticiens qui étudient les aspects pratiques de l’informatique ont accumulé un riche bagage de résultats théoriques et empiriques, lequel est appelé théorie de la complexité calculatoire. Plus particulièrement, ils ont essayé d’élucider ce qui rend certains problèmes plus difficiles à résoudre que d’autres. Pour illustrer les principaux concepts dans ce domaine, nous emploierons un célèbre problème que l’on a appelé—sans doute, avec exagération—la mère de tous les problèmes d’optimisation.

LES PROBLÈMES D’OPTIMISATION

57Quiconque désire trouver le meilleur moyen de faire quelque chose peut se trouver devant ce que les mathématiciens appellent un problème d’optimisation. Souvent, cela signifie avoir à déterminer quelle est la meilleure stratégie face à un grand nombre de possibilités. Par exemple, dans une situation commerciale ou industrielle typique, la « meilleure » option, en règle générale, est l’option la plus économique. Pour chaque possibilité x, il y a un coût associé c(x) ; le problème consiste alors à trouver un x pour lequel c(x) est aussi petit que possible, c’est-à-dire une solution optimale. L’établissement des itinéraires pour la livraison des marchandises et la planification de la production d’une usine constituent des exemples d’optimisation sur une grande échelle. Dans de tels cas, une mauvaise optimisation peut entraîner des effets économiques désastreux, d’où l’intérêt pratique que présente la mise au point de méthodes de résolution efficaces. Certaines de ces techniques procèdent au calcul de la solution optimale directement à partir des données (en faisant usage, par exemple, du calcul différentiel) ; d’autres méthodes essaient d’y parvenir étape par étape, en commençant par une solution approchante qu’on améliorera progressivement.

58Les techniques de résolution fondées sur les nouveaux paradigmes informatiques offrent des possibilités prometteuses. Par exemple, les algorithmes génétiques, que nous aborderons au chapitre 6, fonctionnent avec un réservoir de solutions potentielles dont la composition est périodiquement mise à jour par un mécanisme comportant un élément de hasard. À long terme, le but de ce processus « évolutif », qui ressemble à la sélection naturelle, est d’améliorer la qualité moyenne des futures « générations » de solutions. Si les opérations de mise à jour sont choisies judicieusement, la probabilité est grande pour qu’un « individu » exceptionnel—en tant que solution optimale ou quasi optimale—finisse par apparaître.

59Un problème particulier d’optimisation a rendu perplexes quelques-uns des meilleurs mathématiciens et informaticiens pendant longtemps ; c’est une preuve supplémentaire qu’une question apparemment innocente peut susciter un problème très ardu ! Dans sa version originale, ce problème concerne un commis voyageur qui doit se rendre dans plusieurs villes. En partant d’une certaine ville, il doit aller une fois dans chaque ville avant de retourner à son point de départ. Dans quel ordre le vendeur devra-t-il passer par les différentes villes pour que le tour soit le plus court possible ? Tel est le défi connu sous le nom de problème du commis voyageur.

60Cela a l’air très simple. Tout ce que le représentant doit faire, c’est additionner les distances entre les villes pour chaque tour possible et ensuite choisir le circuit le plus court. Par exemple, un tour comprenant six villes peut être planifié de 120 façons (5 x 4 x 3 x 2 x 1) correspondant aux différents arrangements, ou permutations, d’un ensemble de cinq objets. (Pourquoi 5 objets et non pas 6 ? Parce que tous les itinéraires doivent commencer par la ville où demeure le représentant.) Un ordinateur ne mettra qu’une fraction de seconde pour calculer les longueurs des différents parcours et retenir le plus court. Mais cette méthode de résolution devient inapplicable si le nombre de villes est, disons, cinquante. Car alors un calcul exhaustif cas par cas de la longueur de chaque parcours comportera un si grand nombre d’opérations que même le superordinateur le plus rapide du monde mettra des milliards d’années pour parvenir à la réponse.

61Il n’y a pas beaucoup de commis voyageurs qui doivent se rendre dans cinquante villes ; mais on retrouve le même genre de problème dans l’industrie et l’administration où de bonnes solutions peuvent se traduire par des économies considérables. Dans la fabrication des circuits imprimés, par exemple, des lasers doivent percer des dizaines de milliers de trous. Le circuit « voyage » autour d’un rayon laser fixe, et la recherche de la séquence qui prend le moins de temps pour percer les trous nécessaires est assimilable au problème du commis voyageur. D’autres applications industrielles—la fabrication des puces d’intégration à très grande échelle, par exemple—peuvent comporter des millions de « villes ».

62Manfred Padberg, de la Leonard N. Stern School of Business de l’Université de New York, est un expert du problème du commis voyageur. Il a constaté que la plupart des techniques pour résoudre des problèmes combinatoires difficiles ont été pensées, mises au point et testées sur le modèle du problème du commis voyageur. D’après David Johnson des laboratoires AT & T, un autre mordu du problème du commis voyageur, l’intérêt de cette question peut s’expliquer par sa simplicité et son applicabilité, ou peut-être tout simplement par... son nom énigmatique.

63Mais la fascination qu’exerce le cas du commis voyageur peut aussi provenir du fait qu’il est typique d’une grande catégorie de problèmes ardus, équivalents sur le plan calculatoire. Ce qui signifie que n’importe quelle méthode de résolution efficace d’un problème particulier dans cette catégorie peut être employée à l’élaboration d’algorithmes efficaces pour chacun des autres. Ici, « efficace » a un sens précis, qui sera expliqué bientôt.

LA TAILLE DU PROBLÈME

64Il y a une distinction à faire entre le problème général et les exemples ou cas particuliers du problème. Chaque fois que nous précisons un ensemble de villes et les distances entre elles, nous avons un exemple du problème du commis voyageur. Nous pouvons réussir à trouver le tour le plus court pour tel exemple particulier, mais, pour parvenir à résoudre le problème, nous avons besoin d’une méthode qui conduise à la solution de chaque exemple, et ce dans un délai raisonnable. Le facteur temps est crucial pour d’évidentes raisons pratiques (qui, en effet, peut se permettre d’attendre une réponse durant des milliers d’années ?). Naturellement, nous ne devrions pas être surpris que le temps de calcul augmente avec le nombre de villes concernées, c’est-à-dire avec la « taille » de l’exemple. Les notions de taille du problème et de durée raisonnable doivent donc être clarifiées.

65La taille (dans un exemple quelconque de problème) est la quantité de mémoire informatique nécessaire pour préciser les données (mesurées en unités appropriées telles que les octets). Dans le cas du problème du commis voyageur, les données sont les distances entre chaque paire de villes ; toutefois, pour simplifier, nous prendrons le nombre n de villes comme taille. Ainsi, un problème comprenant 48 villes aura la taille 48. En général, plus la taille est grande, plus long sera le temps de réponse de tout algorithme de solution—bien que le temps de calcul puisse aussi dépendre d’autres facteurs, comme par exemple la distribution géographique des villes.

66Un simple exemple peut faire comprendre pourquoi l’approche directe (calculer les longueurs de tous les parcours possibles) est irréalisable. Pour n = 5 villes, il y a 24 parcours possibles ; si le nombre de villes est augmenté 10 fois à n = 50, le nombre de parcours explose pour atteindre approximativement 6x10⁶², ce qui est une augmentation par un facteur dépassant le quintillion de quintillions (= 1 suivi de 60 zéros) ! Puisque le nombre de possibilités croît extrêmement vite par rapport à la taille du problème, la vérification systématique de tous les parcours pour trouver le parcours optimal devient vite impossible. Pour qu’une méthode de solution soit praticable, les exigences du calcul ne devraient pas augmenter trop rapidement avec la taille de l’exemple. Les experts qui ont étudié la performance des algorithmes ont imaginé une classification des problèmes fondée sur la relation mathématique entre, d’une part, la taille du problème et, d’autre part, le nombre d’opérations nécessaires (à l’ordinateur) pour trouver une solution. La catégorie la plus populaire est connue sous le symbole P, ou, plus familièrement, comme la catégorie des problèmes faciles.

LE TEMPS POLYNOMIAL

67Pour évaluer l’efficacité d’un algorithme, on prend en considération d’habitude soit la durée de déroulement de cet algorithme sur un ordinateur soit le nombre d’opérations élémentaires nécessaires à son exécution. Mais une mesure d’efficacité satisfaisante ne doit pas dépendre d’un ordinateur particulier choisi pour faire tourner l’algorithme. Un moyen d’obtenir une mesure uniforme est d’exiger que l’algorithme soit écrit comme un programme d’une machine de Turing. La notion d’« opération » sera donc parfaitement claire (rappelons-nous qu’une machine de Turing n’accomplit que trois types d’opérations : un mouvement vers la droite, un mouvement vers la gauche et l’écriture d’un symbole). De plus, en stipulant que l’exécution d’une opération doit prendre une unité de temps, le même nombre évaluera la quantité d’opérations et la durée du déroulement. Même si tel détour théorique par les machines de Turing peut rendre nos définitions tout à fait précises, il serait extrêmement difficile de lui donner suite. Heureusement, il existe certains raccourcis pratiques. Mais nous devons d’abord fait un détour par l’algèbre élémentaire.

68Les polynômes (d’une variable x) sont les fonctions obtenues par les opérations d’addition et de multiplication sur x et sur certains nombres (constants) a_n, a_n-1, ... a₀. Considérons, par exemple, la séquence d’opérations suivante : multiplication de x par lui-même (ce qui donne x²), puis multiplication par 3 (nous avons maintenant 3x²), addition de x, ce qui donne [3x²+x], multiplication par 2, ce qui donne [(3x²+x)²], multiplication par x, ce qui donne [(3x²+x)2x], et finalement addition de -5. Nous obtenons de cette façon la fonction polynomiale p(x) =(3x²+x)2x-5. Les polynômes constituent le type le plus simple de fonction, parce que leur calcul ne comporte que les opérations les plus simples : l’addition et la multiplication. En utilisant les propriétés de ces deux opérations, on peut alors montrer qu’une fonction polynomiale peut toujours s’écrire dans la forme standard p(x) = a_nxⁿ+a_n-l x^n-l +...+a₁ x+a₀, avec a_n différent de zéro. Le nombre entier positif n est appelé le degré du polynôme. La forme standard du polynôme dans notre exemple est p(x) = 6x³+2x 2+0x-5, qui est un polynôme du troisième degré. La classe des fonctions polynomiales présente beaucoup de propriétés algébriques désirables. La moindre n’étant pas qu’un autre polynôme résulte de l’addition ou de la multiplication de deux polynômes, ou par le remplacement de tous les x dans p(x) par un autre polynôme q(x) (la composition de deux polynômes, en langage technique).

69En général, il n’est pas possible de calculer exactement combien d’opérations nécessite un algorithme pour résoudre un problème donné de la taille n. Le mieux que nous puissions faire habituellement est d’estimer une limite supérieure u(n) au nombre d’opérations requises pour résoudre un exemple quelconque de taille n, autrement dit garantir que le nombre d’opérations ne dépassera pas u(n). La fonction u(n), qui normalement augmente avec n, devient ainsi une mesure approximative de la vitesse à laquelle la durée du déroulement croît en fonction de la taille du problème. Si u(n) est une fonction polynomiale, nous disons que l’algorithme donné résout le problème en « temps polynomial » (on appelle familièrement l’algorithme lui-même « algorithme de temps polynomial »). Dans la hiérarchie des taux de croissance, les polynômes occupent le niveau le plus bas, juste en dessous des exponentielles, qui constituent le taux de croissance caractéristique des cultures bactériennes et des créances à recouvrer.

70Un problème appartient à la classe P (P comme polynôme), s’il existe un algorithme qui peut résoudre celui-ci dans un délai polynomial ou, plus explicitement, s’il y a un polynôme p(x) et un algorithme qui peut résoudre n’importe quel exemple de taille n en moins de p(n) opérations. Un exemple nous est fourni par le problème du chemin d’Euler, baptisé ainsi d’après Leonhard Euler, génie mathématique suisse du XVIII^e siècle. Dans la version populaire de ce problème, on met une personne au défi de dessiner une certaine figure sans lever son crayon ni tracer deux fois la même ligne. Pour l’image de la figure 2.2, la séquence suivante de segments constitue une solution au problème : EA, AB, BC, CD, DE, EC, CA, AD. Mais si la figure ne satisfait pas à une certaine condition (qui sera expliquée ci-après), la personne peut prendre des heures à essayer en vain de relever le défi. La morale de l’histoire : devant un problème à résoudre, il est prudent de ne pas oublier qu’il peut très bien ne pas y avoir de solution.

FIGURE 2.2

71Mathématiquement, le problème du chemin d’Euler consiste à décider si oui ou non un graphe donné a un chemin qui parcourt chaque « côté » exactement une fois (un chemin eulérien). Un graphe à m « sommets » peut être représenté comme une matrice binaire m x m, ou tableau dont les éléments sont des o et des 1. Si nous numérotons les sommets de 1 à m, alors l’élément dans la i^ième ligne et la j^ième colonne sera 1 dans le cas où les sommets i et j sont reliés par un côté, et o s’ils ne le sont pas. L’étiquetage des sommets du graphe dans la figure 2.2. par les chiffres 1, 2,..., 5, au lieu des lettres A, B,..., E, aboutit à la matrice suivante :

72Dans cette représentation, la taille du problème est m² (le nombre d’éléments dans la matrice). Comment pouvons-nous décider, sur la seule base de la matrice binaire ci-dessus, si oui ou non il y a un chemin eulérien ? Les mathématiques viennent à notre secours. Appelons « degré » d’un sommet le nombre de côtés qui se rencontrent à ce sommet. Par exemple, dans le graphe ci-dessus, A a le degré 4 et E a le degré 3. Remarquons que le degré du sommet i est égal au nombre de 1 dans la iième ligne de la matrice. Maintenant, comme Euler l’a montré, un graphe G a un chemin eulérien si et seulement si le nombre de ses sommets de degré impair est soit 0 soit 2. Dans le premier cas, G a un chemin eulérien fermé (qui commence et se termine au même sommet) ; dans le second, le chemin eulérien commence à un sommet de degré impair et se termine à l’autre. La preuve du théorème d’Euler n’est pas vraiment difficile, mais elle n’est pas nécessaire à notre propos.

73Un algorithme pour décider de la question du chemin d’Euler vérifie la parité de chaque ligne de la matrice—c’est-à-dire si le nombre de 1 est pair ou impair—et retient le nombre de lignes avec parité impaire. Si le décompte final est soit 0 soit 2, alors la réponse (à la question) sera affirmative, sinon elle sera négative. Une estimation approximative révèle que le procédé qu’on vient d’exposer comporte moins de 2m²+3 étapes de calcul. Par conséquent, le polynôme p(n) = 2n+3 dans la taille n(= m²⁾ de l’exemple est une limite supérieure par rapport au nombre d’opérations requises pour résoudre le problème. Le problème d’Euler se situe donc dans la classe P, autrement dit est de temps polynomial.

74Un autre problème de classe P consiste à trouver le chemin le plus court d’une ville donnée à chacune de n autres villes, puisqu’on peut démontrer qu’un algorithme particulier pour résoudre ce problème requiert moins de p(n) = n³ opérations. Si on suppose une vitesse de calcul modeste de 1024 (= 2¹⁰⁾ opérations par seconde, cet algorithme prendra moins d’une demi-heure pour résoudre tout problème comportant 128 villes (n = 128). Comparons cette performance avec celle d’un algorithme de temps exponentiel qui fournit une solution au problème des itinéraires les plus courts après 2" (au lieu de n³) opérations. Pour le même nombre (128) de villes, un tel algorithme requerra le chiffre ahurissant de 10¹⁹ milliards d’années pour parvenir à la réponse. Même avec une vitesse de calcul un milliard de fois plus rapide, la solution prendra encore 10¹⁰ milliards d’années.

75L’exemple ci-dessus peut aider à expliquer pourquoi les algorithmes de temps exponentiel, sauf exceptions remarquables, sont, à toutes fins pratiques, inutiles. Et aussi pourquoi les problèmes dont les solutions dépendent de tels algorithmes sont généralement considérés comme insolubles, et le demeureront dans un avenir prévisible—même en tenant compte du développement (réaliste) d’ordinateurs plus rapides. En revanche, les problèmes de la catégorie P peuvent, en règle générale, être résolus ; c’est pourquoi leurs algorithmes de temps polynomial (dont le degré du polynome est normalement peu élevé) ont été surnommés algorithmes « efficaces ». Le problème du commis voyageur est-il un problème de classe P ? À la vérité, nous ne le savons pas. Personne n’a encore trouvé de solution « efficace », c’est-à-dire un algorithme qui calcule le plus court trajet de n villes en un temps polynomial—mais personne non plus n’a démontré qu’un tel algorithme n’existe pas.

LA CLASSE NP

76Une deuxième classe de problèmes est connue sous le nom peu élégant de problèmes non déterministes vérifiables en temps polynomial, en abrégé NP (nondeterministic polynomial). À proprement parler, l’étiquette NP ne s’applique qu’aux problèmes de décision, c’est-à-dire aux problèmes qui requièrent une réponse par oui ou par non. Mais, la plupart du temps, cette distinction est ambiguë, car presque n’importe quel problème peut être formulé comme un problème de décision quasi équivalent au problème original. Dans le cas du commis voyageur, au lieu de chercher le circuit le plus court, nous pourrions voir s’il y a un tour dont la longueur est K ou moins (où K est un nombre positif). En fait, il n’existe pas plus d’algorithme de temps polynomial connu pour résoudre ce problème qu’il n’en existe pour résoudre la version originale. Cependant, sa formulation en tant que problème de décision nous permet de diviser la recherche d’une solution en deux étapes. Dans la première, une solution possible (une liste S de villes) est « devinée », tandis que, dans la seconde, on « vérifie » si oui ou non S est effectivement une solution—un itinéraire de longueur K ou moins.

77On peut décrire approximativement les problèmes (de décision) dans la classe NP comme étant ceux dont les solutions peuvent être difficiles à trouver mais sont faciles à vérifier. Plus précisément, un problème figure dans la classe NP si la vérification de n’importe quelle solution potentielle peut se faire en temps polynomial (par rapport à la taille du problème). C’est précisément cette idée de la vérifiabilité en temps polynomial qui est visée par la classe NP.

78Qu’en est-il de l’aspect « non déterministe », à savoir le N dans NP ? Une définition précise de la classe NP fait intervenir la notion de machine de Turing non déterministe (MTND), dont le rôle est de « deviner » des solutions potentielles. Nous pouvons imaginer une MTND comme composée d’une tête à écriture seulement. Lorsqu’elle est mise en marche, la tête écrit une chaîne binaire arbitraire sur son ruban. À chaque étape de l’opération, le machine « choisit », de manière non déterministe (c’est-à-dire au hasard), d’écrire un o, un 1 ou de cesser d’écrire complètement. Quand—et si—la tête choisit d’arrêter, la chaîne binaire qui se trouve sur son ruban est transmise à une machine de Turing ordinaire (MT), laquelle commence ensuite le processus de vérification de la manière habituelle (déterministe). Cette machine de Turing ordinaire a été munie à l’avance des données concernant l’exemple particulier du problème de décision que l’on veut résoudre (soit les distances entre les villes, dans le cas du problème du commis voyageur). Ainsi, au lieu d’exécuter un seul calcul, le tandem MTNDMT effectue un nombre infini de calculs, un pour chaque solution potentielle (un pour chaque tour, dans le cas du PCV). Si pour chaque exemple du problème dont la réponse est affirmative, il y a une solution et un calcul qui vérifie celle-ci en temps polynomial, nous disons alors que le problème appartient à la classe NP. Les problèmes de décision dans la classe NP peuvent donc être définis informellement comme ceux qu’une machine de Turing non déterministe peut résoudre en temps polynomial.

79Comme Michael Garey et David Johnson le font remarquer dans Computers and Intractability5 l’emploi du terme « résoudre » dans cette définition ne doit pas être pris au pied de la lettre, puisqu’un « “algorithme non déterministe de temps polynomial” est essentiellement un artifice pour saisir la notion de vérifiabilité en temps polynomial, plutôt qu’une méthode réaliste pour résoudre les problèmes de décision ».

80Pour un problème de type « commis voyageur », la vérification d’une solution potentielle G commence en examinant si G encode bien une permutation, c’est-à-dire un tour T, des villes, puis se poursuit (au cas où G encode un tel tour) par le calcul de la longueur L de T, pour finalement se terminer par la comparaison de L avec la limite K. Il est entendu que cette étape de « vérification » pourrait être spécifiée sous forme d’algorithme de temps polynomial, et que par conséquent le problème du commis voyageur (dans sa version décisionnelle) fait partie de NP.

Y A-T-IL VRAIMENT DES PROBLÈMES DIFFICILES ?

81Chaque problème de décision dans la classe P se retrouve automatiquement dans la classe NP. La raison en est simplement que tout algorithme déterministe de temps polynomial (ou machine de Turing) est aussi un algorithme non déterministe : il peut, en effet, se permettre de contourner l’étape de la « devination » et se diriger tout droit vers la réponse (oui ou non) à la question de la décision. Il semble raisonnable de s’attendre à ce que la classe NP, ayant un nom différent et une définition plus compliquée, soit distincte de (et donc plus grande que) la classe P. Autrement dit, qu’il y ait des problèmes dans NP qui ne soient pas déjà dans P. Mais, dans les faits, est-ce que P est vraiment différent de NP ?

82Cela réconfortera peut-être le lecteur d’apprendre qu’il n’est pas plus ignorant sur ce sujet que l’armée des experts qui ont réfléchi sur la question depuis des décennies. Tous les efforts pour prouver que P # NP ont jusqu’à présent échoué, mais personne n’a montré non plus que P = NP. Des informaticiens passablement réputés ont pensé avoir réglé la question ; cependant, ils ont dû se rétracter devant la découverte d’erreurs dans les preuves qu’ils avaient proposées. Il y a parmi les spécialistes de la complexité une croyance très répandue que P est plus petit que NP. C’est pourquoi ces chercheurs ont longtemps travaillé avec l’hypothèse qu’il existe des problèmes dans la classe NP qui ne sont pas dans la classe P—problèmes que l’on qualifie de « difficiles ». On ne peut pas reprocher à ceux qui travaillent dans la théorie de la complexité d’être, à l’instar des théologiens, animés d’une grande foi dans l’existence de leur premier objet d’étude !

83Pour rendre la situation encore plus énigmatique, les preuves empiriques pour et contre P # NP semblent se neutraliser. D’une part, les échecs répétés en vue de prouver que P # NP laissent fortement supposer que le résultat est faux. Mais alors, comment se fait-il que personne n’ait encore trouvé une solution en temps polynomial (très recherchée, pour des raisons pratiques) à aucun des fameux problèmes dans la classe NP, y compris celui du commis voyageur ? Il faut croire que la vie n’est pas simple dans l’univers de la complexité. Mais les théoriciens de l’informatique sont ingénieux et, faute d’avoir montré l’existence des problèmes difficiles dans NP, ils ont conçu un test pour établir que certains problèmes de cette catégorie sont les plus « difficiles » à résoudre.

LES PROBLÈMES NP-COMPLETS

Le terme « NP-complet » en est venu à symboliser l’abîme d’insolubilité intrinsèque avec lequel sont aux prises les concepteurs d’algorithmes qui cherchent à résoudre des problèmes toujours plus grands et plus complexes.
(Michael R. Garey et David S. Johnson)6.

84En 1971, Stephen Cook, professeur à l’Université de Toronto, a démontré qu’un problème de décision particulier dans la logique formelle peut être qualifié du plus « difficile » des NP. Cook a aussi défini pour la première fois les classes P et NP, bien que l’idée d’un algorithme de temps polynomial puisse remonter à Edmonds au milieu des années 60, lequel les appela familièrement « bons algorithmes ». Edmonds7 a, lui aussi, introduit une notion analogue à NP : celle de problèmes dont les solutions admettent des « preuves » vérifiables en temps polynomial.

85Le problème de Cook est connu comme étant le problème de la satisfiabilité, ou sat. Un exemple de sat est une formule logique, ou expression booléenne, telle que

[x₁ ou x₃ ou x₅] et [x₄ ou x₁ ou (non x₅)]
ou [(non x₄) ou (non x₂) ou (non x₃)]

où x₁, x₂,..., x₅ représentent des variables booléennes qui peuvent prendre une des deux valeurs de vérité : 0 (= faux) ou 1 (= vrai). La question (de la décision) à laquelle on doit répondre est de savoir s’il existe une assignation possible de valeurs de vérité aux variables, qui fasse de l’expression une expression vraie (la « satisfasse »). Nous rappelons au lecteur que l’expression « x ou y » est vraie si au moins un élément x ou y est vrai ; que « x et y » est vraie si les deux x, y sont vrais ; et que « non x » est vraie si x est faux. Par exemple, pour x₁ = x₃ = x₄ = x₅ = 1 et x₂ = 0, l’expression ci-dessus est vraie. Ainsi donc, dans ce cas particulier, nous pouvons facilement trouver une réponse à la question—des exemples simples de problèmes difficiles donnant toujours l’illusion que le problème général est facile à résoudre.

86Un exemple général de sat consiste en un ensemble fini D de disjonctions, chacune de celles-ci comprenant trois variables et/ou leurs négations. Un tel ensemble D avec quatre disjonctions est :

[x, ou (non x₃) ou x₅], [x₄ ou x, ou x₅], [(non x₄)
ou (non x₂) ou (non x₃)], [x₂ ou x₅ ou (non x,)]

87La question est ensuite de savoir si oui ou non il y a une assignation de valeurs de vérité aux variables apparaissant dans D (il peut y en avoir des milliers) qui satisfasse simultanément (c’est-à-dire rende vraies) toutes les disjonctions de l’ensemble.

88Vérifier si une assignation des valeurs de vérité satisfait un ensemble fini de disjonctions est, de toute évidence, une tâche qui peut s’accomplir en temps polynomial. Par conséquent, sat est un problème appartenant à la classe NP. Ce que Cook a montré dans un théorème8 qui fit école (dont la preuve est assez compliquée), c’est que sat a la propriété de complétude additionnelle suivante : tout exemple d’un problème dans la classe NP peut être transformé en temps polynomial, en un exemple de sat ; de plus, la réponse à la question de la décision est la même pour les deux exemples. L’essentiel est que si (un gros si) sat peut d’une façon ou d’une autre être résolu efficacement (c’est-à-dire en temps polynomial), alors il en va de même pour chaque problème dans NP, la distinction entre « difficiles » et « faciles »—entre les problèmes dans NP et ceux dans P—s’effondrant, du fait que NP serait identique à P !

89Les problèmes qui présentent cette propriété de « complétude » telle que précisée ci-dessus forment une sous-classe de NP connue comme étant la classe des problèmes NP-complets. Ils comprennent une grande variété de problèmes qui apparaissent fréquemment en mathématiques et en recherche opérationnelle, notamment notre célèbre problème du commis voyageur. La détermination de l’arrangement le plus probable de fragments clonés d’une séquence d’ADN constitue un problème NP-complet en biologie moléculaire. Il y a aussi des problèmes NP-complets dans pratiquement chaque domaine de l’informatique, depuis le tri et la recherche jusqu’à la programmation des multiprocesseurs.

90Tous les problèmes NP-complets partagent la propriété d’être « les problèmes les plus difficiles de la classe NP ». Ceci n’est peut-être qu’une illusion : si P=NP, alors tous les problèmes NP que l’on croyait « difficiles » peuvent se résoudre en temps polynomial et ne méritent pas cette appellation. Mais, d’un point de vue pratique, le fait de savoir qu’un problème est NP-complet est un précieux renseignement, car cela signifie que les chances de mettre au point un algorithme de solution efficace sont presque nulles. À moins, bien entendu, que deux générations d’informaticiens aient été dupées par un mirage.

LA SOLUTION DE L’ÉNIGME

91Nous avons déjà rencontré, dans la section « Les fonctions calculables », la fonction g, laquelle fut définie comme étant g(n) = 1, s’il y a un bloc de n chiffres « n » consécutifs dans la partie décimale de , et g(n) =0, s’il n’existe pas un tel bloc. Nous avons alors mis le lecteur ou la lectrice au défi de prouver que g est calculable par une machine de Turing. Voici la solution— ou plutôt une solution—de l’énigme.

92À ce propos, il faut faire remarquer que g prend soit la valeur o soit la valeur 1 pour n=1, 2,..., 9 et qu’elle n’est pas définie pour tous les autres nombres naturels. Il y a exactement 512(=2⁹) fonctions avec ces propriétés, et, pour chacune d’elles, nous pourrions facilement écrire le programme d’une machine de Turing qui la calcule. Puisque g est calculée par l’une de ces 512 machines de Turing, elle est donc calculable. Ce qu’il y a de singulier au sujet de g, c’est que nous ne pouvons pas dire quelle machine de Turing la calcule—pour ma part, je ne le puis certainement pas. Tout ce que nous savons avec certitude, c’est qu’il existe une machine de Turing capable de calculer g, qui est tout ce que requiert la définition d’une fonction calculable.