On me demande souvent :
Quelle est la meilleure méthode pour apprendre les mathématiques ou l'informatique ?
C'est une très bonne question
En fait, il y a un siècle
Le grand mathématicien David Hilbert
était précisément en quête d'une réponse
à cette quesiton
Il voulait une approche systématique
pour prouver des théorèmes mathématiques
ou comme un chercheur en informatique aujourd'hui dirait :
Peut-on résoudre tous les problèmes mathématiques avec un algorithme?
Turing a essayé d'adresser cette question
Et ce faisant,
il a voulu définir préciser ce qu'était un algorithme
C'était Rachid Guerraoui, professeur en Informatique et Communication à l'EPFL
et la question qu'il pose
est l'une des questions les plus profondes jamais posées dans l'Histoire des mathématiques
Qu'est-ce qu'un algorithme ?
Intuitivement, un algorithme, c'est un ensemble d'instructions
qui peuvent être exécutées par n'importe qui
Donc en gros, un algorithme, c'est une recette très détaillée
En fait, c'est une recette si détaillée
que si vous suivez très précisément les instructions d'un algorithme
vous finiriez par obtenir exactement le même résultat
que n'importe qui d'autre qui aurait appliqué
les instructions de l'algorithme lui aussi
Et ça ce fut super utile, car ça permettait aux mathématiciens
de décrire très précisément des méthodes pour résoudre des problèmes
En particulier, en concevant un algorithme pour résoudre un cas particulier,
Les mathématiciens fournissaient ainsi aussi
une méthode pour résoudre tous les problèmes similaires à venir
y compris des problèmes auxquels personne n'a encore pensé !
Sans surprise, c'est quelque chose sur lequel les mathématiciens ont commencé à travailler il y a très longtemps
et ils ont appelé cette chose "algorithme"
car la première personne qui a, dirons-nous, "formaliser" cette notion
s'appelait lui-même "algorithme"
Son nom complet était Muhammed Ibn Musa Al-Khwarizmi
Wow! Vous avez entendu cet accent de malade que j'ai !
Al-Khwarzimi décrivit un algorithme très précis
pour résoudre toute une gamme de problèmes
appelés les équations du second degré
Les détails importent peu
C'était il y a très longtemps, au 8ème siècle.
Et depuis, les mathématiciens ont inventé de nouveaux algorithmes
et les ont appliqué eux-mêmes
ou ont demandé à des non-mathématiciens de les exécuter
car il s'agit d'instructions très simples
En fait, avant la découverte de Turing,
les calculatrices n'étaient pas des machines
Les calculatrices étaient des humains
qui étaient embauchés pour effectuer de longs calculs fastidieux
Les calculatrices étaient des humains
qui devaient exécuter les algorithmes que les mathématiciens avaient conçus
Même à l'époque,
les mathématiciens dénigraient quelque peu les calculs
car les mathématiques, ce n'est pas faire des calculs
ce qui compte ne sont pas les calculs
ce qui compte, ce sont les algorithmes
Les algorithmes sont très utiles depuis longtemps
car ils permettent à tous de résoudre des problèmes très difficiles
À l'époque,
seuls les très grands mathématiciens savaient résoudre des équations
mais grâce Al-Khwarizmi,
tout le monde est maintenant capable
de penser à une équation du second degré et la résoudre immédiatement en calculant Delta
C'est devenu tout à coup très facile
Donc les algorithmes simplifient des tâches compliquées
En fait, même à l'époque, les mathématiciens ont commencé à se demander :
Et si les machines exécutaient les instructions, et donc les algorithmes ?
à la place d'un humain?
Et ils ont donc commencé à inventer des machines à calculer
Pascal a inventé une machine
Babbage a inventé une machine
Beaucoup inventèrent des machines pour exécuter un ensemble donné d'instructions
Par exemple, Pascal pensait à des algorithmes pour calculer les impôts
Babbage utilisait un algorithme pour calculer des polynômes pour calculer des nombres de Bernouilli
et d'autres trucs comme ça
Et il y avait cette idées
selon laquelle chaque machine ferait au plus un petit ensemble d'algorithmes
Insistons dessus
À l'époque, les mathématiciens s'étaient rendus compte
que les algorithmes étaient la solution à leurs problèmes
Cependant, ils pensaient qu'à chaque fois qu'ils voulaient lancer un nouvel algorithme,
ils devaient ou bien embaucher des humains pour exécuter le programme
ou ils devaient construire une machine spécifique
pour exécuter leur algorithme en particulier
et c'est ce que tout le monde pensait avant Turing
Donc en 1936
Alan Turing inventa une machine
beaucoup, beaucoup plus simple que les machines de ses prédécesseurs
mais la machine de Turing était si simple
qu'elle était universelle
La machine de Turing consistait en une bande mémoire
et une tête de lecture/écriture
avec un état interne
les détails sont un peu techniques
mais le message central est absolument fantastique
cette machine était une machine de calcul universelle
universelle dans le sens où elle pouvait exécuter n'importe quel algorithme
et ça, ça veut dire que si vous voulez faire tourner un nouvel algorithme auquel vous venez tout juste de penser
vous n'êtes pas obligé de construire une nouvelle machine pour votre algorithme
vous pouvez simplement utiliser n'importe laquelle des nombreuses machines de Turing universelles
qui nous entourent
les servers, les ordinateurs, les téléphones...
toutes ces machines sont capables d'exécuter votre nouvel algorithme
et ça, c'est presque magique!
Mais comment ça marche ?
Comment est-ce qu'une unique machine comme votre téléphone
peut exécuter n'importe quel algorithme ?
La machine de Turing est universelle car
comme je l'ai dit
elle permet d'exécuter tout algorithme
et elle y arrive car elle est si simple
que le programme, ou l'algorithme,
peut lui-même être entré comme une donnée
à l'algorithme
Donc vous pouvez avoir un algorithme
dont les données ou les paramètres
sont eux-mêmes des algorithmes
En termes de machines de Turing
ça veut dire que si j'ai ma machine de Turing universelle
et si vous m'amenez votre machine de Turing
Je peux analyser votre machine de Turing
et traduire les caractéristiques de votre machine en instructions
en un préfixe des données
que je vais mettre sur ma machine de Turing universelle
et ensuite, quelque soit les données que vous voulez mettre sur votre machine de Turing
on n'aura qu'à les copier-coller à la fin des données de ma machine de Turing
en addition du préfixe que j'ai mis pour décrire votre machine de Turing
Et ce qui est génial, c'est que peu importe les résultats de votre machine de Turing
j'aurais exactement les mêmes résultats
à l'aide de ma machine de Turing universelle
Les autres machines avant n'avaient pas cette spécificité
Et ça c'était le génie de l'universalité
et c'est grâce à cela que l'on comprend aujourd'hui la différence entre le software et le hardware
La machine de Turing est un hardware qui permet d'entrer le software
en tant qu'algorithmes
Et ça, ça a eu des grosses implications sur l'industrie de l'informatique
ça veut dire que l'on peut séparer
le software du hardware
Les gens qui s'intéressent aux algorithmes peuvent se concentrer
sans avoir à s'inquiéter de la machine qui exécutera leurs algorithmes
Ils sauront, par la thèse de Church-Turing, qu'ils seront capables de l'exécuter sur une machine
Une seconde... Qu'est-ce que la thèse de Church-Turing?
La thèse de Church-Turing est une conjecture
qui dit que tout algorithme auquel on peut penser
peut être exécuté par une machine de Turing
peut être formalisé et exécuté par une machine de Turing
Oui ! Parce que l'universalité de la machine de Turing
n'impliquait que le fait que n'importe quelle autre machine de Turing pouvait être simulée par une machine de Turing universelle
Mais on pourrait imaginer qu'il puisse exister une toute autre sorte de machine à calculer qui n'est pas une machine de Turing
et qui serait capable d'exécuter des algorithmes
que la machine de Turing ne pourrait pas !
Et bien, la thèse de Church-Turing fait le postulat
qu'il n'y a pas de telle autre machine
Toute machine à calculer
est une sorte de machine de Turing
ou du moins elle peut être simulée
par une machine de Turing universelle
Notez que cette thèse ne peut pas vraiment être prouvée
car elle a à voir avec notre réalité physique
en fait, il y a des modèles des mathématiques
dans lesquels vous pouvez construire des algorithmes
des algorithmes très bizarres
que la machine de Turing ne peut pas exécuter
Mais de tels modèles bizarres d'algorithmes
ne semblent pas correspondre à notre réalité physique
on ne semble pas en mesure de construire une machine
qui exécuterait les algorithmes de ces modèles mathématiques abstraits
Autrement dit, la thèse de Church-Turing n'est pas juste restreinte à la théorie du calcul
Certaines personnes pensent qu'elle a de grosses conséquences
sur les structures de notre univers
et sur la philosophie de l'esprit
Je ne vais pas rentrer dans de telles considérations...
Ce qui est incontestable
c'est que la thèse de Church-Turing a eu des impacts énormes
sur les nouvelles technologies que nous avons
et donc, sur nos sociétés
À cause de cette thèse, on a aujourd'hui une seule machine sur laquelle on exécute tout.
donc toutes les machines que nous avons
nos ordinateurs, nos voitures, nos téléphones
tout est construit selon le modèle de Turing
et ils obéissent donc à la thèse de Church-Turing
Et donc à cause de cela, on a une seule machine
qui fait tout
au lieu d'avoir une machine pour Facebook
une autre pour aller sur Google
et une autre pour faire d'autres calculs
Voilà donc la belle Histoire
En 1936, Alan Turing essaya de mieux comprendre
la quête d'Hilbert d'un algorithme
qui résolverait tous les problèmes mathématiques
et soit-dit en passant, cet algorithme n'existe pas
et en essayant de définir ce qu'est un algorithme
il a essayé de définir une machine simple
une machine humaine
mais une machine qui serait capable
d'exécuter ce qu'on pourrait appeler un algorithme
et ce faisant, il a inventé la très célébrée machine de Turing
donc le but était de montrer que quelque chose n'allait pas
et ce faisant, il a inventé un truc très très utile
Alors, vous avez peut-être maintenant l'impression
que le concept de machine de Turing (universelle)
aurait dû avoir résolu la question de la construction du Hardware
si la machine de Turing est déjà universelle,
pourquoi continuer la recherche sur les machines de Turing ?
En fait, le modèle a été inventé
mais le modèle de la machine ne fait que dire : « voilà ce qui peut être fait. »
il ne dit pas à quelle vitesse
avec quelle quantité de mémoire
si vous avez le droit à des petites erreurs ou non
donc depuis 1936
les informaticiens ont construit des machines de Turing
mais avec diverses caractéristiques
plus rapides, ou en utilisant moins de mémoire
moins de batterie
avec moins d'erreurs
avec des compilations qui se font bien
les inventions sont maintenant
plus sur des aspects quantitatifs
que sur les aspects qualitatifs qui ont été conçus par Turing en 1936
