Des limites du calcul… à l’oracle de Turing

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.

Statue d'Alan Turing au Bletchley Park museum
Statue d’Alan Turing au Bletchley Park museum

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, 1026

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

À lire aussi sur internetactu.net

15 commentaires

  1. Dommage que New Scientist, apparemment, n’ait pas rappelé que toute computation est avant tout « sociale ». Introduire un algorithme quelconque dans le corps social modifie son fonctionnement.

    Au profit de qui ?
    Souvent de ceux qui oublient de faire état de cette simple réalité !

    Sur l’origine politique du langage et les fonctions sociales de la computation, on peut lire : Jean-Louis Dessalles : « Why we talk? » Oxford University Press

  2. Pourquoi utiliser l’affreux anglicisme « computation » quand le mot « calcul » existe en français ?

  3. Cantor: pour éviter les répétitions 😉 J’utilise aussi le mot calcul pas mal de fois dans l’article !

    Olivier: je pense qu’il y a deux écoles : ceux qui pensent que les sciences y compris dans leur aspect le plus fondamental (comme c’est le cas avec p=np, par exemple) sont des productions sociales, dont la valeur est donc dépendante de qui pose ces questions et des rapports sociaux qu’elles induisent, et ceux qui pensent qu’au contraire il s’agit de questions universelles que n’importe quelle société, voire n’importe quelle espèce intelligente de l’univers, ne manquerait pas de finir par se poser . En ce qui me concerne, je me rattache fermement à cette seconde école…Mais c’est un débat qui est loin de se clore…

  4. Rémi, certes, mais remarque que les tenants de la première école sont plutôt du côté du manche, ce qui a pour effet d’occulter les tenants de la deuxième, et donc d’oblitérer le débat.
    La preuve, New Scientist, apparemment, n’en fait pas état.

  5. Olivier,il y a de cela un bon bout de temps, j’avais lu avec plaisir les deux livres de Paul Feyerabend, « contre la méthode » et « Adieu la raison ». Les thèses étaient assez séduisantes et en plus Feyerabend avait pas mal d’humour. Il faisait une démonstration assez convaincante de l’importance des aspects politiques et sociologiques chez Galilée (je ne me souviens pas de tout, mais par exemple il disait que Galilée écrivait italien et non en latin, et que cela aurait joué un rôle fondamental dans la diffusion de ses idées). Mais j’ai lu quelque part (c’est peut être une légende, je n’en sais rien) qu’à la fin de sa vie il aurait déclaré : « mais tout de même Galilée avait raison ». Je pense que ça résume bien le problème: la politique, le social joue un rôle évident dans l’histoire de la pensée scientifique, mais au final, au delà du social, il reste des hypothèses (définitivement) fausses et d’autres (provisoirement) justes…

  6. Les conclusions de Matthias Englert sur les décisions morales sont erronées.

    1. Dans la vaste majorité des cas pratiques, il est possible de savoir si un programme donné s’arrête (dans le formalisme restreint du langage turing-complet dans lequel est écrit le programme). Savoir ce que fait son algorithme, où il commence et où il s’arrête, c’est à la base de la programmation… Ce qui est impossible, c’est de construire une méthode automatique pour savoir si un programme quelconque s’arrête. Et encore, en faisant quelques hypothèses sur les entrées on peut faire des outils automatiques pas trop mauvais.

    2. A priori, notre cerveau ne cherche pas la solution exacte des décisions morales. On calcule des approximations.

    La fin de l’article me laisse sur ma faim. Je sais comment générer du chaos. Je sais faire des calculs sur de l’ordre. Mais je ne sais pas comment faire des calculs sur du chaos. Il me semble que c’est ce qui serait intéressant d’expliquer/vulgariser.

  7. Hadrien,
    « La fin de l’article me laisse sur ma faim. Je sais comment générer du chaos. Je sais faire des calculs sur de l’ordre. Mais je ne sais pas comment faire des calculs sur du chaos. Il me semble que c’est ce qui serait intéressant d’expliquer/vulgariser. »

    Bonne question, c’est un sujet sur lequel je reviendrai probablement, il me semble prometteur…

  8. L’article insiste beaucoup sur les réseaux de neurones, mais le réseau de neurones lui même ne permet pas de faire de l’hyper-computation. La structure et les mécanismes des réseaux de neurones peuvent se programmer sur une machine de Turing. Donc c’est de la « simple-computation ».

    Je n’ai pas lu les papiers cités mais je pense que l’astuce ici est que Pi ne peut pas être stocké/représenté par une machine de Turing classique. Donc l’astuce est en quelque sorte mécanique, pour stocker mécaniquement la valeur exacte de Pi ou d’autres nombres irrationnels, astuce qui pourrait probablement être employée dans un autre contexte que celui des réseaux de neurones.

  9. Jean Lassègue spécialiste de Turing a déclaré aux Entretiens du nouveau monde indudtriel de 2014:
    « Que pour Turing, il y a toujours un reste, un indécidable dans le tout numérique et c’est un enjeu de société. Pour Turing il y a de l’incalculable et que son image en est la morphogenese qui ne relève pas de la machine analytique à état discret déterministe Laplacienne dont il a défini le modèle en 1936. Pour Turing il y a ces 2 poles opposés ».
    Lassègue a rajouté « Que le combat social est la maîtrise de l’inaccessible et de l’accessible. »

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *