Les limites de l’informatique : même à l’ère de l’intelligence artificielle, certains problèmes sont tout simplement trop difficiles à résoudre
par Jie Wang, Professor of Computer Science, University of Massachusetts Lowell, États-Unis
Grâce aux technologies d’intelligence artificielle, les ordinateurs peuvent aujourd’hui engager des conversations convaincantes avec des personnes, composer des chansons, peindre des tableaux, jouer aux échecs et au go, et diagnostiquer des maladies, pour ne citer que quelques exemples de leurs prouesses technologiques.
Ces succès pourraient être considérés comme une indication que le calcul n’a pas de limites. Pour voir si c’est le cas, il est important de comprendre ce qui rend un ordinateur puissant.
La puissance d’un ordinateur comporte deux aspects : le nombre d’opérations que son matériel peut exécuter par seconde et l’efficacité des algorithmes qu’il exécute. La vitesse du matériel est limitée par les lois de la physique. Les algorithmes – essentiellement des ensembles d’instructions – sont écrits par des humains et traduits en une séquence d’opérations que le matériel informatique peut exécuter. Même si la vitesse d’un ordinateur pouvait atteindre la limite physique, des obstacles informatiques subsistent en raison des limites des algorithmes.
Ces obstacles comprennent des problèmes impossibles à résoudre par les ordinateurs et des problèmes théoriquement solubles mais qui, en pratique, dépassent les capacités des ordinateurs actuels, et même les plus puissants que l’on puisse imaginer. Les mathématiciens et les informaticiens tentent de déterminer si un problème est soluble en l’essayant sur une machine imaginaire.
Machine informatique imaginaire
La notion moderne d’algorithme, connue sous le nom de machine de Turing, a été formulée en 1936 par le mathématicien britannique Alan Turing. Il s’agit d’un dispositif imaginaire qui imite la façon dont les calculs arithmétiques sont effectués avec un crayon sur du papier. La machine de Turing est le modèle sur lequel tous les ordinateurs actuels sont basés.
Pour permettre des calculs qui nécessiteraient plus de papier s’ils étaient effectués manuellement, la réserve de papier imaginaire dans une machine de Turing est supposée être illimitée. Cela équivaut à un ruban imaginaire illimité, ou « ruban », de carrés, dont chacun est soit vierge, soit contient un symbole.
La machine est contrôlée par un ensemble fini de règles et démarre sur une séquence initiale de symboles sur le ruban. Les opérations que la machine peut effectuer sont le déplacement vers une case voisine, l’effacement d’un symbole et l’écriture d’un symbole sur une case vide. La machine calcule en effectuant une séquence de ces opérations. Lorsque la machine termine, ou « s’arrête », les symboles restant sur la bande constituent la sortie ou le résultat.
L’informatique concerne souvent des décisions dont la réponse est oui ou non. Par analogie, une analyse médical (type de problème) vérifie si l’échantillon d’un patient (une instance du problème) présente un certain indicateur de maladie (réponse par oui ou par non). L’instance, représentée dans une machine de Turing sous forme numérique est la séquence initiale de symboles.
Un problème est considéré comme « soluble » si l’on peut concevoir une machine de Turing qui s’arrête pour chaque instance, qu’elle soit positive ou négative, et qui détermine correctement la réponse que l’instance donne.
Tous les problèmes ne peuvent pas être résolus
De nombreux problèmes sont solubles à l’aide d’une machine de Turing et peuvent donc être résolus sur un ordinateur, tandis que beaucoup d’autres ne le sont pas. Par exemple, le problème des dominos, une variante du problème des tuiles formulé par le mathématicien américain d’origine chinoise Hao Wang en 1961, n’est pas soluble.
La tâche consiste à utiliser un ensemble de dominos pour couvrir une grille entière et, selon les règles de la plupart des jeux de dominos, à faire correspondre le nombre de points sur les extrémités des dominos adjacents. Il s’avère qu’il n’existe aucun algorithme capable de partir d’un ensemble de dominos et de déterminer si cet ensemble couvrira complètement la grille ou non.
Rester raisonnable
Un certain nombre de problèmes solubles peuvent être résolus par des algorithmes qui s’arrêtent en un temps raisonnable. Ces « algorithmes en temps polynomial » sont des algorithmes efficaces, ce qui signifie qu’il est pratique d’utiliser des ordinateurs pour résoudre leurs instances.
Des milliers d’autres problèmes solubles ne sont pas connus pour avoir des algorithmes en temps polynomial, malgré des efforts intensifs pour trouver de tels algorithmes. Parmi ces problèmes figure le problème du voyageur de commerce.
Le problème du représentant de commerce consiste à savoir si un ensemble de points dont certains sont directement reliés, appelé graphe, possède un chemin qui part de n’importe quel point, passe par tous les autres points exactement une fois et revient au point d’origine. Imaginons qu’un vendeur veuille trouver un itinéraire qui passe par tous les foyers d’un quartier exactement une fois et revient au point de départ.
Ces problèmes, appelés NP-complets [ou problème NPC = problème complet pour la classe NP de déterminisme Non Polynomial, ndlr], ont été formulés indépendamment et leur existence a été démontrée au début des années 1970 par deux informaticiens, le Canadien américain Stephen Cook et l’Américain ukrainien Leonid Levin. Stephen Cook, dont les travaux sont arrivés en premier, s’est vu décerner le prix Turing 1982, le plus élevé en informatique, pour ces travaux.
Le coût de savoir exactement
Les algorithmes les plus connus pour les problèmes NP-complets consistent essentiellement à rechercher une solution parmi toutes les réponses possibles. Le problème du voyageur de commerce sur un graphe de quelques centaines de points prendrait des années à exécuter sur un superordinateur. De tels algorithmes sont inefficaces, ce qui signifie qu’il n’existe aucun raccourci mathématique.
Les algorithmes pratiques qui traitent ces problèmes dans le monde réel ne peuvent offrir que des approximations, bien que ces approximations s’améliorent. L’existence d’algorithmes efficaces en temps polynomial capables de résoudre des problèmes NP-complets figure parmi les sept problèmes ouverts du millénaire affichés par le Clay Mathematics Institute au début du 21e siècle, chacun étant assorti d’un prix d’un million de dollars américains.
Au-delà de Turing
Existe-t-il une nouvelle forme de calcul dépassant le cadre de Turing ? En 1982, le physicien américain Richard Feynman, lauréat du prix Nobel {avec notamment Alain Expert, ndlr], a avancé l’idée d’une informatique basée sur la mécanique quantique.
En 1995, Peter Shor, un mathématicien appliqué américain, a présenté un algorithme quantique permettant de factoriser des entiers en temps polynomial. Les mathématiciens estiment que cette question est insoluble par les algorithmes en temps polynomial dans le cadre de Turing. La factorisation d’un nombre entier consiste à trouver un plus petit nombre entier supérieur à 1 qui peut diviser le nombre entier. Par exemple, le nombre entier 688 826 081 est divisible par un plus petit nombre entier 25 253, car 688 826 081 = 25 253 x 27 277.
Un algorithme majeur, l’algorithme RSA, largement utilisé pour sécuriser les communications en réseau, est basé sur la difficulté de factorisation des grands nombres entiers. Le résultat de Peter Shor suggère que l’informatique quantique, si elle devient une réalité, changera le paysage de la cybersécurité.
Est-il possible de construire un ordinateur quantique à part entière pour factoriser des entiers et résoudre d’autres problèmes ? Certains scientifiques pensent que c’est possible. Plusieurs groupes de scientifiques dans le monde travaillent à la construction d’un tel ordinateur, et certains ont déjà construit des ordinateurs quantiques à petite échelle.
Néanmoins, comme toutes les nouvelles technologies inventées auparavant, il est presque certain que le calcul quantique posera des problèmes qui imposeront de nouvelles limites.
Pour aller plus loin
Texte paru initialement en anglais dans The Conversation, traduit par la Rédaction. La traduction étant protégée par les droits d’auteur, cet article traduit n’est pas libre de droits. Nous autorisons la reproduction avec les crédits appropriés : « Citizen4Science/Science infuse » pour la version française avec un lien vers la présente page.
Cet article GRATUIT de journalisme indépendant à but non lucratif vous a intéressé ? Il a pour autant un coût ! Celui de journalistes professionnels rémunérés, celui de notre site internet et d’autres coût nécessaire au fonctionnement de la structure. Qui paie ? nos lecteurs uniquement pour garantir notre ultra-indépendance. Votre soutien est indispensable.
Science infuse est un service de presse en ligne agréé (n° 0324 x 94873) piloté par Citizen4Science, association à but non lucratif d’information et de médiation scientifique.
Notre média dépend entièrement de ses lecteur pour continuer à informer, analyser, avec un angle souvent différent car farouchement indépendant. Pour nous soutenir, et soutenir la presse indépendante et sa pluralité, faites un don pour que notre section presse reste d’accès gratuit, et abonnez-vous à la newsletter gratuite également !
Science infuse est un service de presse en ligne agréé (n° 0324 x 94873) piloté par Citizen4Science, association à but non lucratif d’information et de médiation scientifique doté d’une Rédaction avec journalistes professionnels. Nous défendons farouchement notre indépendance. Nous existons grâce à vous, lecteurs. Pour nous soutenir, faites un don ponctuel ou mensuel.
