Il y a beaucoup de gens en crypto qui s'excitent sur l'idée qu'on
puisse peut-être un jour avoir
des ordinateurs
quantiques qui permettraient de faire certains types de calculs
beaucoup plus efficacement qu'un ordinateur classique (il doit s'agir
de la classe de
complexité BQP,
mais je dois avouer que je m'y perds complètement dans le zoo de la
complexité, d'autant que le sujet ne m'intéresse pas du tout) : ceci
pose le problème — on parle de cryptographique « post-quantique » — de
trouver des algorithmes cryptographiques qui résistent aux attaques
par les ordinateurs quantiques (tout en étant quand même utilisables
sur des ordinateurs classiques !), ce qui n'est pas tout à fait
évident (au niveau de la cryptographie symétrique l'existence
d'ordinateurs quantiques a seulement plus ou moins l'effet
de diviser
les tailles de clé par deux, mais au niveau de la cryptographique
à clés publiques on doit vraiment chercher de nouvelles choses). Je
dois dire que j'ai une attitude vis-à-vis des ordinateurs quantiques à
semblable à celle du digne Lord Kelvin qui décrétait, dans une
interview donnée en 1902 : No balloon and no
aeroplane will ever be practically successful.
Autrement dit,
j'espère bien que l'avenir me donnera autant tort qu'à Kelvin.
J'ai aussi entendu parler d'un film, Travelling Salesman, dont la prémisse est qu'un mathématicien aurait résolu — par la positive et de façon constructive — au fameux problème P≟NP. Les conséquences d'une telle découverte, à savoir qu'on pourrait résoudre efficacement toute une classe de problèmes (PH) qui semblent a priori impossibles à mener « en pratique » (c'est-à-dire, en un temps raisonnable), valent évidemment de l'or (ne serait-ce que, de nouveau, pour son impact en cryptographie), je suppose que le mathématicien se retrouve avec beaucoup de gens qui veulent son algorithme ou qui veulent sa peau, et je ne sais pas comment le film se termine parce que je n'en ai vu que la bande-annonce. (Je ne sais d'ailleurs pas si le film est sorti en salles, encore moins s'il sortira en France.)
Notons au passage qu'il n'y a pas, à ma connaissance, de relation d'ordre évidente entre la réalisabilité pratique d'un ordinateur quantique et une preuve constructive de P=NP, parce qu'on pense qu'il n'y a pas d'inclusion dans un sens ou dans l'autre entre BQP et PH. Mais, de nouveau, je ne suis pas du tout expert en complexité et je n'ai regardé ça que de très loin (je préfère les classes de complexité nettement plus grosses). Sans compter que, de toute façon, c'est un domaine où on ne sait quasiment jamais prouver que deux choses sont différentes…
Mais bon, dépassons un peu ces hypothèses de petits joueurs et faisons carrément l'hypothèse que la thèse de Church-Turing soit fausse, et qu'on puisse réaliser des ordinateurs non seulement plus rapides mais qualitativement plus puissants qu'une machine de Turing (ou, de façon approximative, « infiniment rapides »). Mettons, pour fixer les idées, qu'on dispose d'une machine hyperarithmétique : je ne veux pas trop entrer dans les détails de ce qu'est une machine hyperarithmétique (je le ferai sans doute un jour dans une autre entrée ; ajout : c'est fait dans cette entrée ultérieure), mais disons — c'est là le point important — qu'elle est capable de faire (disons, en temps constant et négligeable) tout ce qu'une machine de Turing — et a fortiori n'importe quel ordinateur réel — est capable de faire en n'importe quel temps fini aussi long soit-il ou même de calculer toutes sortes de choses utiles sur ce qu'une machine de Turing va faire en un temps infini (par exemple, si elle passe jamais par tel ou tel état), et, mieux, une machine hyperarithmétique est même capable de calculer le même genre de choses sur une autre machine hyperarithmétique tant qu'on ne fait pas de boucle sur cette propriété. Même si une machine hyperarithmétique n'est évidemment pas capable de tout faire (ça ne voudrait rien dire car ce serait trivialement contradictoire), elle répond très bien à ce qu'on a envie d'appeler un ordinateur « infiniment rapide ».
Ceux qui veulent une définition mathématique formelle peuvent consulter le chapitre VI du livre Recursion-Theoretic Hierarchies de Hinman, où ce dont je parle est appelé une fonction récursive dans la fonctionnelle E (ça coïncide avec la notion de fonction Δ¹₁ de la hiérarchie analytique, mais la définition avec la fonctionnelle E est plus naturelle dans le contexte que je viens de poser et explique mieux comment on peut programmer une telle machine). Le lecteur vraiment attentif aura remarqué que ma définition définit certes ce qu'une machine hyperarithmétique est capable de faire mais pas le temps qu'elle prend à le faire, alors pour ce lecteur un peu maniaque, je complète : je considère une suite (non spécifiée) δn d'ordinaux qui a pour limite le ω₁ de Church-Kleene, vérifiant au moins, disons, δ0=0 et δn+1>φ(δn,0) où φ désigne les fonctions de Veblen, et si le programme calculé termine avec un arbre d'appels à E de rang inférieur à δn de la hiérarchie constructible alors la machine termine en moins de n millisecondes. Je dois sans doute aussi préciser qu'on dispose d'un lien de communication entre la machine hyperarithmétique et un ordinateur classique, et que ce lien est à débit fini (disons que la machine se connecte sur USB).
Voici que le père Noël vous a apporté une machine hyperarithmétique, bref, un ordinateur infiniment rapide. Peut-on s'en servir pour devenir facilement maître du monde, et si oui, comment ? Évidemment, toute la crypto du monde (excepté le masque jetable et plus généralement ce qui relève de la théorie de l'information) est complètement cassée pour une telle machine, mais après tout ce n'est pas forcément si évident que ça de mettre les mains sur des messages chiffrés intéressants à déchiffrer. Évidemment, une telle machine peut instantanément déterminer si un énoncé mathématique est un théorème ou non (et même, pour les énoncés arithmétiques, s'ils sont vrais), et le cas échéant en produire des démonstrations (mais elles ne seront pas forcément si évidentes à rendre lisibles pour un humain). Évidemment, on peut faire toutes les simulations numériques qu'on veut, mais si on veut simuler un cerveau humain encore faut-il avoir une description précise préalable de ce qu'est un cerveau humain. Bref, la machine peut faire beaucoup de choses, mais ce n'est pas forcément si évident de s'en servir.
Dans une variante un peu différente du problème, je suppose que le père Noël offre une telle machine à tout le monde (ainsi que les outils et plans nécessaires pour en fabriquer de nouvelles à bas prix), et je demande comment l'humanité en est affectée. Bon, là aussi, le fait que toute la crypto tombe à terre peut être ennuyeux, alors pour court-circuiter le problème je vais supposer que le père Noël est généreux et offre aussi, tant qu'à faire, entre chaque paire d'appareils (identifiée par leur numéro de série) un canal de communication à la vitesse de la lumière et à débit illimité, qui soit parfaitement fiable, non détectable et non interceptable (comme ça, la crypto est peut-être cassée, mais elle n'est plus très utile non plus — en tout cas, on n'a plus besoin de chiffrement ni d'authentification).
J'ai posé cette question à un certain nombre de personnes, et j'ai eu essentiellement deux sortes de réponses. La majorité semble penser que l'existence d'ordinateurs infiniment rapides ne changerait pas grand-chose : l'argument étant essentiellement que les facteurs limitants dans notre utilisation des ordinateurs actuels sont, souvent, non pas leur rapidité mais notre capacité à les programmer ou bien notre capacité à mesurer le monde extérieur ; pour dire les choses un peu trivialement, avoir une machine hyperarithmétique n'aidera pas à faire des tablettes avec une interface graphique plus conviviale ni à mesurer les données météo avec une plus grande précision pour faire de meilleures prévisions. D'autres sont d'avis, au contraire, que le changement que j'imagine serait tellement profond, tellement gigantesque, qu'il n'y aurait plus rien de commun entre l'humanité avant et après — c'est le concept de la singularité de Vinge. Il faut notamment souligner que si la machine hyperarithmétique anéantit certains des problèmes devant lesquels nous sommes (par exemple la partie des mathématiques consistant à trouver des démonstrations — par opposition à celle qui consiste à trouver des énoncés intéressants à démontrer) et n'aide peut-être pas à d'autres, il est aussi probable qu'elle ouvre de nouveaux problèmes que nous n'imaginons même pas.
Mais il est aussi possible que la machine change le monde d'une manière totalement imprévue, et peut-être un peu futile. Par exemple, j'imagine très bien une conversation avec quelqu'un vivant il y a 150 ans (Charles Babbage, peut-être ?) dans lequel je lui expliquerais que nous disposons de machines incroyablement rapides capables de mener toutes sortes de calculs, et aussi d'un réseau de communication reliant toute la Terre à la vitesse de la lumière, et que nous nous en servons pour… regarder des vidéos de chats qui jouent au piano.