Grâce aux technologies d’intelligence artificielle, les ordinateurs d’aujourd’hui peuvent engager des conversations convaincantes avec des gens, composer des chansons, peindre des peinturesjouer échecs et alleret diagnostiquer des maladiespour ne citer que quelques exemples de leurs prouesses technologiques.
Ces succès pourraient être pris pour indiquer 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.
Il y a deux aspects à la puissance d’un ordinateur : 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. Algorithmes – essentiellement 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 peut atteindre la limite physique, des obstacles de calcul subsistent en raison des limites des algorithmes.
Ces obstacles comprennent des problèmes qui sont impossibles à résoudre pour les ordinateurs et des problèmes qui sont théoriquement solubles mais qui, en pratique, dépassent les capacités des versions les plus puissantes des ordinateurs d’aujourd’hui imaginables. Les mathématiciens et les informaticiens tentent de déterminer si un problème est résoluble en les essayant sur une machine imaginaire.
G/O Media peut toucher une commission
Conseil en toxicomanie
Refuge Santé
Accessible à tous
Safe Haven donne la priorité à vos besoins avec un traitement de la toxicomanie flexible et individualisé, en particulier la dépendance aux opioïdes et à l’alcool.
Une machine informatique imaginaire
La notion moderne d’algorithme, connue sous le nom de machine de Turing, a été formulée en 1936 par un mathématicien britannique Alan Turing. C’est un appareil 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 sont basés aujourd’hui.
Pour tenir compte des calculs qui nécessiteraient plus de papier s’ils étaient effectués manuellement, la fourniture de papier imaginaire dans un Machine de Turing est supposé illimité. Cela équivaut à un ruban imaginaire illimité, ou « bande », de carrés, dont chacun est vide ou 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 la bande. 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 vierge. 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 sont la sortie ou le résultat.
Qu’est-ce qu’une machine de Turing ?
L’informatique consiste souvent à prendre des décisions avec des réponses oui ou non. Par analogie, un test médical (type de problème) vérifie si l’échantillon d’un patient (un exemple du problème) présente un certain indicateur de maladie (réponse oui ou 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 « résoluble » si une machine de Turing peut être conçue qui s’arrête pour chaque instance, qu’elle soit positive ou négative, et détermine correctement la réponse donnée par l’instance.
Tous les problèmes ne peuvent pas être résolus
De nombreux problèmes peuvent être résolus à 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 du pavage formulé par le mathématicien sino-américain Hao Wang en 1961, n’est pas résoluble.
La tâche consiste à utiliser un ensemble de dominos pour couvrir une grille entière et, en suivant les règles de la plupart des jeux de dominos, en faisant correspondre le nombre de pépins aux extrémités des dominos attenants. Il s’avère qu’il n’y a pas d’algorithme qui peut commencer avec un ensemble de dominos et déterminer si oui ou non l’ensemble couvrira complètement la grille.
Rester raisonnable
Un certain nombre de problèmes solubles peuvent être résolus par des algorithmes qui s’arrêtent dans un laps de temps raisonnable. Ces « algorithmes en temps polynomial” sont des algorithmes efficaces, ce qui signifie qu’il est pratique d’utiliser des ordinateurs pour en résoudre des instances.
Des milliers d’autres problèmes solubles ne sont pas connus pour avoir des algorithmes en temps polynomial, malgré des efforts intensifs continus pour trouver de tels algorithmes. Ceux-ci incluent le problème du voyageur de commerce.
Le problème du voyageur de commerce demande si un ensemble de points avec certains points directement connectés, appelé graphe, a un chemin qui part de n’importe quel point et passe par tous les autres points exactement une fois, et revient au point d’origine. Imaginez qu’un vendeur veuille trouver un itinéraire qui passe exactement une fois par tous les ménages d’un quartier et revient au point de départ.
Le problème du voyageur de commerce devient rapidement incontrôlable lorsque vous dépassez quelques destinations.
Ces problèmes, appelés NP-completont été formulés indépendamment et dont l’existence a été démontrée au début des années 1970 par deux informaticiens, un Canadien américain Stephen Cook et américain d’origine ukrainienne Léonid Levin. Cook, dont le travail est arrivé en tête, a reçu le prix Turing 1982, le plus élevé en informatique, pour ce travail.
Le coût de savoir exactement
Les algorithmes les plus connus pour les problèmes NP-complets recherchent essentiellement une solution parmi toutes les réponses possibles. Le problème du voyageur de commerce sur un graphique de quelques centaines de points prendrait des années à s’exécuter sur un supercalculateur. De tels algorithmes sont inefficaces, ce qui signifie qu’il n’y a pas de raccourcis mathématiques.
Les algorithmes pratiques qui traitent ces problèmes dans le monde réel ne peuvent offrir que des approximations, bien que les approximations s’améliorent. S’il existe des algorithmes efficaces en temps polynomial qui peuvent résoudre des problèmes NP-complets est parmi les sept problèmes ouverts du millénaire posté par le Clay Mathematics Institute au tournant du 21e siècle, chacun portant un prix de 1 million de dollars américains.
Au-delà de Turing
Pourrait-il y avoir une nouvelle forme de calcul au-delà du cadre de Turing ? En 1982, le physicien américain Richard Feynmannlauréat du prix Nobel, a proposé l’idée d’un calcul basé sur la mécanique quantique.
Qu’est-ce qu’un ordinateur quantique ?
En 1995, Peter Shor, un mathématicien appliqué américain, a présenté un algorithme quantique pour factoriser des entiers en temps polynomial. Les mathématiciens pensent que cela est insoluble par les algorithmes en temps polynomial dans le cadre de Turing. Factoriser un entier signifie trouver un plus petit entier supérieur à 1 qui peut diviser l’entier. Par exemple, l’entier 688 826 081 est divisible par un entier plus petit 25 253, car 688 826 081 = 25 253 x 27 277.
Un algorithme majeur appelé le Algorithme RSA, largement utilisé dans la sécurisation des communications réseau, est basé sur la difficulté de calcul de la factorisation de grands nombres entiers. Le résultat de Shor suggère que l’informatique quantique, si elle devenait une réalité, changer le paysage de la cybersécurité.
Un ordinateur quantique à part entière peut-il être construit pour factoriser des nombres entiers et résoudre d’autres problèmes ? Certains scientifiques pensent que cela peut être le cas. Plusieurs groupes de scientifiques du monde entier travaillent à en construire un, 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 des problèmes avec le calcul quantique surgiront qui imposeraient de nouvelles limites.
Jie Wang est un pprofesseur d’informatique à UMass Lowell.
Cet article est republié de La conversation sous licence Creative Commons. Lis le article original.
Vous pouvez lire l’article original (en Angais) sur le sitegizmodo.com