Alan Turings Contributions éternelles à l’informatique, à l’IA et à la cryptographie

Supposons que quelqu’un vous demande de concevoir l’ordinateur le plus puissant possible. Alan Turing, dont la réputation de figure centrale de l’informatique et de l’intelligence artificielle n’a fait que croître depuis sa mort prématurée en 1954, a appliqué son génie à des problèmes comme celui-ci à une époque antérieure aux ordinateurs tels que nous les connaissons. Ses travaux théoriques sur ce problème et d’autres restent à la base de l’informatique, de l’IA et des normes cryptographiques modernes, y compris celles recommandées par le NIST.

Le chemin qui mène de la conception de l’ordinateur le plus puissant possible aux normes cryptographiques comporte quelques rebondissements, tout comme la brève vie de Turing.

À l’époque de Turing, les mathématiciens se demandaient s’il était possible de construire une seule machine polyvalente capable de résoudre tous les problèmes calculables. Par exemple, nous pouvons calculer l’itinéraire le plus économe en énergie d’une voiture vers une destination et (en principe) la manière la plus probable dont une chaîne d’acides aminés se repliera en une protéine tridimensionnelle. Un autre exemple de problème calculable, important pour le cryptage moderne, est de savoir si des nombres plus grands peuvent ou non être exprimés comme le produit de deux nombres plus petits. Par exemple, 6 peut être exprimé comme le produit de 2 et 3, mais 7 ne peut pas être factorisé en nombres entiers plus petits et est donc un nombre premier.

Certains mathématiciens éminents ont proposé des conceptions élaborées pour des ordinateurs universels qui fonctionneraient en suivant des règles mathématiques très compliquées. Il semblait extrêmement difficile de construire de telles machines. Il a fallu le génie de Turing pour montrer qu’une machine très simple pouvait en fait calculer tout ce qui est calculable.

Son appareil hypothétique est maintenant connu sous le nom de machine de Turing. La pièce maîtresse de la machine est une bande de ruban adhésif, divisée en boîtes individuelles. Chaque case contient un symbole (comme A, C, T, G pour les lettres du code génétique) ou un espace vide. La bande de bande est analogue aux disques durs d’aujourd’hui qui stockent des bits de données. Initialement, la chaîne de symboles sur la bande correspond à l’entrée, contenant les données pour le problème à résoudre. La chaîne sert également de mémoire à l’ordinateur. La machine de Turing écrit sur la bande les données auxquelles elle doit accéder plus tard dans le calcul.

L’appareil lit un symbole individuel sur la bande et suit les instructions indiquant s’il faut changer le symbole ou le laisser seul avant de passer à un autre symbole. Les instructions dépendent de l’état actuel de la machine. Par exemple, si la machine doit décider si la bande contient la chaîne de texte TC, elle peut balayer la bande vers l’avant tout en basculant entre les états la lettre précédente était T et la lettre précédente n’était pas C. Si dans l’état la lettre précédente était T il lit un C, il passe à un état trouvé et s’arrête. S’il rencontre le symbole vide à la fin de l’entrée, il passe à l’état ne l’a pas trouvé et s’arrête. De nos jours, nous reconnaîtrions le jeu d’instructions comme le programme de la machine.

Cela a pris du temps, mais finalement il est devenu clair pour tout le monde que Turing avait raison : la machine de Turing pouvait en effet calculer tout ce qui semblait calculable. Aucun nombre d’ajouts ou d’extensions à cette machine ne pourrait étendre sa capacité de calcul.

Pour comprendre ce qui peut être calculé, il est utile d’identifier ce qui ne peut pas l’être. Dans une vie antérieure de professeur d’université, j’ai dû enseigner la programmation à quelques reprises. Les étudiants rencontrent souvent le problème suivant : Mon programme fonctionne depuis longtemps ; c’est coincé ? C’est ce qu’on appelle le problème d’arrêt, et les étudiants se sont souvent demandé pourquoi nous ne pouvions tout simplement pas détecter des boucles infinies sans nous y coincer. Il s’avère qu’un programme pour faire cela est une impossibilité. Turing a montré qu’il n’existe pas de machine qui détecte si une autre machine s’arrête ou non. De ce résultat séminal ont suivi de nombreux autres résultats d’impossibilité. Par exemple, les logiciens et les philosophes ont dû abandonner le rêve d’un moyen automatisé de détecter si une assertion (comme s’il y a une infinité de nombres premiers) est vraie ou fausse, car cela est incalculable. Si vous pouviez faire cela, alors vous pourriez résoudre le problème de l’arrêt simplement en demandant si l’énoncé que cette machine arrête est vrai ou faux.

Turing a ensuite apporté des contributions fondamentales à l’IA, à la biologie théorique et à la cryptographie. Son implication dans ce dernier sujet lui a valu honneur et renommée pendant la Seconde Guerre mondiale, lorsqu’il a joué un rôle très important dans l’adaptation et l’extension des techniques de cryptanalyse inventées par les mathématiciens polonais. Ce travail a brisé le cryptage de la machine allemande Enigma, apportant une contribution significative à l’effort de guerre.

Turing était gay. Après la guerre, en 1952, le gouvernement britannique l’a condamné pour avoir eu des relations sexuelles avec un homme. Il est resté hors de prison uniquement en se soumettant à ce qu’on appelle maintenant la castration chimique. Il est mort en 1954 à 41 ans d’un empoisonnement au cyanure, qui a été initialement considéré comme un suicide mais qui pourrait avoir été un accident selon une analyse ultérieure. Plus de 50 ans s’écouleront avant que le gouvernement britannique ne lui présente ses excuses et lui pardonne (après des années de campagne menée par des scientifiques du monde entier). Aujourd’hui, la plus haute distinction en informatique s’appelle le prix Turing.

Les travaux de calcul de Turing ont jeté les bases de la théorie moderne de la complexité. Cette théorie tente de répondre à la question Parmi ces problèmes qui peuvent être résolus par un ordinateur, lesquels peuvent être résolus efficacement ? Ici, efficace signifie non pas en milliards d’années mais en millisecondes, secondes, heures ou jours, selon le problème de calcul.

Par exemple, une grande partie de la cryptographie qui protège actuellement nos données et nos communications repose sur la conviction que certains problèmes, tels que la décomposition d’un nombre entier en ses facteurs premiers, ne peuvent être résolus avant que le Soleil ne se transforme en géante rouge et ne consomme la Terre (actuellement prévision pour 4 milliards à 5 milliards d’années). Le NIST est responsable des normes cryptographiques utilisées dans le monde entier. Nous ne pourrions pas faire ce travail sans la théorie de la complexité.

La technologie nous lance parfois une courbe, comme la découverte que si un ordinateur quantique suffisamment grand et fiable était construit, il serait capable de factoriser des nombres entiers, brisant ainsi une partie de notre cryptographie. Dans cette situation, les scientifiques du NIST doivent s’appuyer sur les experts mondiaux (dont beaucoup sont internes) afin de mettre à jour nos normes. Il y a de profondes raisons de croire que les ordinateurs quantiques ne pourront pas casser la cryptographie que le NIST est sur le point de déployer. Parmi ces raisons, la machine de Turing peut simuler des ordinateurs quantiques. Cela implique que la théorie de la complexité nous donne des limites sur ce qu’un puissant ordinateur quantique peut faire.

Mais c’est un sujet pour un autre jour. Pour l’instant, nous pouvons célébrer la façon dont Turing a fourni les clés d’une grande partie de la technologie informatique d’aujourd’hui et nous a même donné des conseils sur la façon de résoudre les problèmes technologiques imminents.