Par Jonathon Keats

EN 1935, Alan Turing a entrepris de se forger une réputation en devançant le plus grand mathématicien du monde. Turing avait 22 ans et était un nouveau boursier à Cambridge. Sa cible, David Hilbert, était le professeur vénéré de l’Université de Göttingen qui avait à lui seul établi le programme de recherche pour les mathématiques du 20e siècle.

Hilbert n’était pas à la hauteur de l’arriviste britannique. Dans son livre Turing’s Vision, Chris Bernhardt montre habilement comment Turing a anéanti l’une des grandes ambitions de Hilbert avec une preuve magistrale – au cours de laquelle il a inventé par inadvertance l’ordinateur moderne.

Le titre de l’article de Turing, « On Computable Numbers, With an Application to the Entscheidungsproblem » (qui signifie « problème de décision »), n’est guère invitant, et sa lecture nécessite une formation avancée. Cela peut expliquer pourquoi, alors que la renommée de Turing explosait, les écrits les plus populaires se concentraient sur son piratage de code en temps de guerre, ses écrits d’après-guerre sur l’intelligence artificielle – ou sa persécution et ses poursuites pour être gay et son pardon royal posthume.

Mais ce qui manque au livre de Bernhardt dans le drame, il le compense dans l’explication lucide. La vision de Turing permet aux lecteurs attentifs d’apprécier la preuve qui a fait le nom de Turing et, en prime, de comprendre les bases des ordinateurs modernes.

L’Entscheidungsproblem faisait partie des travaux de Hilbert pour montrer que les axiomes de base des mathématiques sont logiquement cohérents. À cette fin, Hilbert a cherché un algorithme – une procédure de calcul – qui indiquerait si un énoncé mathématique donné pouvait être prouvé à partir de ces seuls axiomes. Turing a montré de manière décisive qu’il n’existait pas d’algorithme de ce type.

« Turing a prouvé qu’il n’y avait pas d’ensemble mécanique de règles pour les solutions de tous les problèmes mathématiques »

Pour ce faire, explique Bernhardt, Turing devait d’abord établir une définition de travail pour le terme algorithme – pour définir ce que signifie calculer. Turing a regardé les « ordinateurs » humains – des gens qui faisaient des calculs. La tâche consiste à écrire des symboles sur papier, a-t-il noté. « Le comportement de l’ordinateur à tout moment est déterminé par les symboles observing qu’il observe et son « état d’esprit ». »

En décomposant la cogitation apparemment complexe en procédures arithmétiques simples, Turing a rendu le calcul explicite et a éliminé l’élément humain. « La nouvelle vision de Turing était de définir des algorithmes en termes de machines informatiques théoriques », écrit Bernhardt. « Tout ce qui peut être calculé peut être calculé par une machine de Turing. »

C’est pourquoi les machines étaient au cœur du papier de Turing. Montrer qu’il y avait des algorithmes que les machines de Turing fonctionneraient indéfiniment et de manière non concluante était une façon de montrer que Hilbert se trompait. Turing a prouvé « qu’il y avait des questions qui dépassaient le pouvoir des algorithmes de répondre”. Son triomphe fut spectaculaire et dévastateur pour ceux qui croyaient (comme Hilbert) que tous les problèmes pouvaient être résolus.

Pourtant aussi cruciales que les machines théoriques étaient pour la preuve de Turing, elles se sont avérées avoir encore plus d’impact à part entière, fournissant un modèle conceptuel pour les ordinateurs modernes. L’influence a été directe, informant la conception pionnière de John von Neumann en 1945 pour les ordinateurs électroniques et les machines de la taille d’une pièce qui ont appliqué son architecture. Comme les machines de Turing, les ordinateurs utilisaient des zéros et des uns pour coder des programmes et des données. Cela reste essentiel pour les langages et les réseaux de haut niveau, donc en apprenant sur les machines de Turing, les lecteurs reprennent les principes de l’informatique.

Il y a aussi des ramifications philosophiques aujourd’hui. Ayant basé les ordinateurs sur le comportement humain, Turing a noté que les gens sont vraiment des machines de Turing. Les ordinateurs sont nos miroirs: que nous nous émerveillions ou que nous frissonnions devant la dernière IA, nous ne faisons que nous regarder.

Cet article est paru sous le titre « Sommes-nous des machines de Turing? »

(* Lorsque vous achetez via des liens sur cette page, nous pouvons gagner une petite commission, mais cela ne joue aucun rôle dans ce que nous examinons ou dans notre opinion à ce sujet.)

Plus sur ces sujets:

• mathématiques
• informatique
• algorithmes