En décembre, le New Scientist a sorti un numéro spécial consacré aux idées scientifiques les plus importantes : au menu, entre autres, le nombre de dimensions, la mécanique quantique, l’infini… et un article nous proposant de réfléchir à la manière de penser la computation. Un texte court et peu détaillé, mais qui a le mérite de pointer dans des directions qui méritent d’être explorées.

En effet, qu’est-ce que la computation ? On ne saurait la limiter aux ordinateurs tels qu’on les connaît. Comme le souligne le New Scientist, on peut calculer avec plein de choses et de beaucoup de manières différentes : avec une abaque on fait déjà de l’informatique. Dans nos colonnes, nous avons plusieurs fois mentionné ces différents modes de calcul, qui ne recourent en rien aux machines telles que nous les connaissons : on peut calculer avec des systèmes collectifs, de l’ADN, et mêmes des animaux comme des crabes. Et ne parlons pas de l’ordinateur quantique…

Dans la question annuelle de The Edge 2014, rappelons que Neil Gershenfeld allait encore plus loin, en affirmant que non seulement les ordinateurs traditionnels ne calculaient pas de la seule manière possible, mais que celle qu’ils employaient constituait un mauvais exemple. Précisons que Neil Gershenfeld, très connu pour avoir formalisé le concept de Fablab, est avant tout un scientifique qui s’est fait remarquer pour son intérêt pour les formes non conventionnelles de computation, tels les ordinateurs à bulle, purement liquides, implémentés dans un milieu microfluidique (vidéo).

Le New Scientist pointe deux aspects de la théorie de la science informatique. L’une concerne les limites des « machines de Turing » et l’autre, l’hypercomputation, traite d’un moyen possible de déplacer ces limites.

Les limites de la computation

Le problème de l’arrêt est une de ces limites fondamentales. Il démontre qu’il est impossible à un programme de prédire avec certitude quand (et même si) un autre programme va s’arrêter, ayant terminé sa tâche. Cela a l’air très abstrait comme ça, mais ce problème peut avoir des conséquences pratiques et même… fatales, selon l’étude (.pdf) menée par l’éthiciste Matthias Englert, comme nous le rapporte Motherboard. En effet, les dilemmes moraux sont précisément de la classe des problèmes qui restent « indécidables » et où le « calcul ne s’arrête jamais ». Cela pose la question de savoir comment des machines susceptibles de sauver des vies, ou pire, d’en prendre (comme les robots soldats) réagiront face à ces derniers…

L’autre grande limite sur laquelle bute notre théorie de la computation est la fameuse question du P = NP . Pour résumer très brièvement, il existe une classe de programmes informatiques assez simples, parce qu’il leur est possible de mener à bien leur travail en un temps relativement court. Toute augmentation de la difficulté de la tâche est linéairement proportionnelle au temps mis par le programme pour l’accomplir. Par exemple, si vous demandez à un programme d’additionner les nombres de 1 à 10, puis d’additionner ceux de 1 à 20, il doublera la durée requise. On peut donc savoir à l’avance si la computation sera résolue « dans un temps raisonnable ». Ce sont les problèmes de classe « P ».

Au contraire, on rencontre une autre classe de programmes pour lesquels la durée de temps d’exécution du code s’accroît de façon exponentielle à mesure que la tâche s’allonge. C’est le cas du problème du voyageur de commerce. Ce voyageur doit passer par un certain nombre de villes, une seule et unique fois, et revenir à son point de départ. Quel est le chemin le plus court pour réussir sa mission ? Avec trois villes, il dispose de 6 trajets envisageables. Mais avec 10, il en a 3 628 800, et avec 25 villes, 10²⁶…

Les problèmes « NP » font partie de ces tâches exponentielles. Ce sont celles dont la résolution est ardue, mais où il est extrêmement simple de vérifier la valeur de la solution une fois que celle-ci est trouvée. Comme l’explique le New Scientist dans un second article, il est difficile de compléter une grille de sudoku, mais une fois les cases remplies, il est enfantin de vérifier si la solution proposée est exacte ou pas.

Même chose en cryptographie, continue le magazine : il est très compliqué de trouver les facteurs premiers d’un grand nombre comme 304 679, mais il est élémentaire de constater que multiplier 547 et 557 donne le nombre en question.

P est un sous-ensemble de NP : autrement dit, ce qui est simple à résoudre est facile à vérifier. En revanche, tout problème facile à vérifier implique-t-il l’existence d’un algorithme permettant de le résoudre facilement ? De la réponse à cette question dépendent bon nombre d’applications pratiques, en cryptographie notamment…

La question P = NP est l’objet d’une compétition entre mathématiciens, en compagnie d’autres mystères mathématiques. Celui qui trouvera la réponse est susceptible de gagner un prix d’un million de dollars !

L’hypercomputation, au-delà des limites

Ces limites n’ont donc rien à voir avec la puissance de calcul des ordinateurs ou même l’architecture de ces derniers. Ce sont des contraintes posées par la nature de la computation elle-même.

Mais nos machines de Turing sont-elles les seules formes de computation susceptibles d’exister ? Le New Scientist, dans un autre article, pointe vers une recherche très spéculative, celle de l’hypercomputation ou des calculateurs « super-Turing ».

Alan Turing jouait déjà avec cette idée dans sa thèse de 1938, et nommait une telle machine hypothétique « l’oracle ». Elle aurait été capable sortir du cadre de la simple logique et de donner une réponse à toute sorte de questions, quelle que soit leur complexité. Il aurait cependant compris qu’une telle notion restait très spéculative, voire tenait du mythe, et n’aurait jamais tenté de l’implémenter.

Pourtant, il aurait soupçonné que le hasard (le véritable, pas le pseudo aléatoire généré au sein des ordinateurs actuels) jouerait un rôle dans la créativité, et donc dans l' »hypercomputation » d’un hypothétique oracle. « En 1947, il est allé jusqu’à suggérer à ses patrons ébahis du National Physical Laboratory au Royaume-Uni près de Londres de placer du radium radioactif à l’intérieur de l’Automatic Computing Engine qu’il avait conçu, dans l’espoir que des désintégrations apparemment aléatoires donneraient aux inputs l’imprévisibilité désirée », nous raconte le New Scientist.

Personne ne se préoccupa de l’hypercomputation pendant les années qui ont suivi, celle-ci étant considérée comme un serpent de mer sans conséquence dans le monde réel. Dans les années 90, une chercheuse, Hava Siegelmann, travaillait sur les réseaux de neurones. Son intention était de prouver que ceux-ci étaient en fait incapables de posséder la puissance logique d’une machine de Turing traditionnelle. Non seulement sa tentative échoua, mais elle découvrit que les réseaux de neurones étaient en fait en mesure de produire quelque chose que la machine de Turing demeurait incapable d’obtenir : de l’aléatoire réel. Dans un réseau de neurones, chacun des éléments possède un « poids », c’est-à-dire un nombre traduisant son influence sur un autre neurone. Imaginons par exemple qu’un neurone A soit activé lorsque la somme de ses inputs atteint le chiffre 1. Il serait par exemple connecté à un neurone B possédant un poids de 0,50, un neurone C doté d’un poids de 0,3 et un neurone D d’un poids de 0,2. si ces trois neurones envoient leur message à A simultanément, alors ce dernier va s’activer. Mais Siegelmann va introduire une nouveauté. Elle va utiliser comme valeur pour ces poids des nombres irrationnels, à l’instar de Pi.

On ne peut pas dire que sa trouvaille suscita une réaction enthousiaste chez ses collègues, et elle-même perdit un moment tout intérêt pour le concept d’hypercomputation. Selon elle, ses travaux étaient exclusivement des mathématiques abstraites sans véritable impact sur le réel. Mais deux décennies plus tard, deux jeunes chercheurs Emmett Redd et Steven Younger reprirent les travaux de Siegelmann, la convainquant au passage de se pencher à nouveau sur le sujet.

Les trois chercheurs se sont donc concentré sur le chaos, cette branche des mathématiques qui étudie « l’extrême sensitivité aux conditions initiales », le fait qu’une toute petite modification dans les paramètres d’une équation (par exemple le dixième chiffre après la virgule) peut avoir des conséquences très importantes. C’est le fameux « effet papillon » (le battement des ailes d’un papillon à Berlin peut provoquer un ouragan à Melbourne). Ils ont donc construit deux « machines chaotiques » dans lesquelles les inputs du réseau neuronal sont en mesure, au plus petit changement de créer une cascade de transformations dans les outputs. La première d’entre elles, basée sur des circuits électroniques, contient 3 neurones et 11 connexions synaptiques. Le second dispositif, doté de 11 neurones reliés par 3 600 connexions, est basé sur des lasers des miroirs des loupes et des détecteurs de photons.

Il va sans dire qu’on reste encore dans l’expérimentation, et que la communauté scientifique est loin d’atteindre un consensus sur l’hypercomputation. Mais certains ont déjà franchi un pas supplémentaire : et si le cerveau humain était un de ces « hyperordinateurs » ?

Selon le New Scientist : « La construction d’un ordinateur doté des caractéristiques du cerveau est un vieux rêve, la dernière initiative à grande échelle dans ce domaine faisant partie du Human Brain Project basé à l’Ecole Polytechnique fédérale de Lausanne (NDE : voir notre article « Un cerveau, deux projets »). Ses efforts, cependant, se concentrent tous sur la construction de répliques de neurones normaux, basés sur la technologie numérique de la machine de Turing. Younger est convaincu que l’approche moins rigide des réseaux de neurones chaotiques sera plus susceptible de porter ses fruits. » Une telle application pourrait nous conduire vers une intelligence analogue à celle produite par notre cerveau, » affirme-t-il.

Rémi Sussan