Alan Turing : 1912-2012
Le 17 mai dernier a eu lieu la 8ème journée mondiale contre l'homophobie, l'occasion d'évoquer le destin tragique de Alan Turing, dont on fête le centenaire en cette année 2012.
Le Memorial Alan Turing au Sackville Park (Manchester).
Fait intéressant : Turing est représenté avec une pomme.
Si on devait résumer la vie de Turing, on pourrait le faire ainsi :
- 23 juin 1912 : il naît du côté de Londres.
- 1936-1937 : il révolutionne l'informatique théorique en inventant la notion d'algorithme (renvoyant dans les cordes Church et son lambda-calcul) et les machines de Turing, ce qui lui permet de résoudre le problème de la décision (peut-on toujours résoudre un problème par un algorithme ?) et le problème de l'arrêt (peut-on savoir à l'avance si un algorithme va boucler ?).
- 1942-1943 : il révolutionne la cryptanalyse (le cassage de codes secrets), en décryptant les messages allemands codés par Enigma. Impliqué dans les services de renseignement militaires britannique, c'est un peu grâce à lui que le monde a été sauvé des nazis.
- 1950 : il révolutionne l'histoire de l'intelligence artificielle, en inventant le test de Turing : on pourra dire que l'intelligence artificielle existe le jour où on ne pourra plus la différencier de l'intelligence humaine. C'est pour cela que, aujourd'hui, on croise tous les jours le nom de Turing : c'est le T de l'acronyme CAPTCHA (vous savez, les mots illisibles qu'il faut identifier dès que l'on veut s'inscrire sur un site de rencontre éducatif).
- 1952 : il révolutionne l'histoire de la morphogénèse (en l'inventant), en proposant une bonne raison au fait que les zèbres sont zébrés, alors que les léopards, ben non.
- 1952 : du seul fait de son homosexualité, il jugé coupable d'"indécence manifeste et de perversion sexuelle" (comme l'a été Oscar Wilde 50 ans plus tôt), qui lui donne le choix entre plusieurs années de prison et la castration chimique. Il choisit la deuxième option. Mauvaise idée.
- 1954 : on le retrouve mort deux semaines avant ses 42 ans, empoisonné au cyanure. Les circonstances de sa mort ne sont pas parfaitement comprises, la thèse la plus probable étant celle du suicide à la pomme empoisonnée, façon Blanche-Neige. (Notons au passage que la pomme d'Apple fait référence à celle de Newton, et non à celle de Turing)
- 1966 : son nom est donné au prix Turing, l'équivalent du Nobel en informatique.
- 2009 : Gordon Brown, premier ministre britannique, reconnaît que, finalement, c'était peut-être pas une bonne idée que de castrer chimiquement l'un des plus grand mathématicien britannique, d'autant plus que son aide a été la bienvenue pendant la guerre.
Machines de Turing et problème de l'arrêt
En 1928, Hilbert propose ce qu'il appelle dans sa langue le Entscheidungsproblem (problème de la décision) : peut-on toujours prouver mécaniquement (par un algorithme) qu'un énoncé est (ou non) un théorème. Ce problème est lié au problème de l'arrêt : si j'écris un algorithme dans un langage de mon choix, peut-on vérifier sans le lancer que l'algorithme ne va pas boucler indéfiniment (et donc, qu'il va finir par s'arrêter) ?
Pour répondre à ces questions, il faut tout de même savoir exactement ce qui peut mériter d'être appelé "algorithme", et définir la calculabilité. Ce travail est surtout l’œuvre de Alonzo Church, l'inventeur λ-calcul. Ce système formel, qui fonde historiquement la notion de fonctions, a permis à Church de résoudre le problème de la décision. Le λ-calcul a tout de même un gros défaut : il est (beaucoup) moins intuitif que les machines de Turing, qui seront inventés quelques années plus tard par le mathématicien qui nous intéresse cette année. Même Church le reconnaîtra.
Concrètement, une machine de Turing, c'est une machine (théorique) composée :
- d'un ruban de papier (si possible, infini) divisé en cases. Dans chacune de l'une d'elle, un 0 ou un 1.
- d'une tête de lecture/écriture, capable de lire le ruban et, le cas échéant, de remplacer un 0 par un 1, ou inversement.
- d'un registre d'état (un compteur - fini -, qui liste les états dans lequel peut être la machine)
- d'une table d'action, qui dit à la tête de lecture quand il faut faire quoi (du genre "si tu es en état x et que tu lis un 0, alors tu le transforme en 1, tu te mets en état y et tu passe à la case d'à côté"). C'est le programme en lui même.
Le ruban correspond à l'input du programme, tandis que la table d'action correspond au programme lui-même.
Une machine de Turing peut donc ressembler à ceci :
Démarrer en l'état 0 avec une bande pleine de 0.
Étape 1 (état 0) : la tête est en position 0, elle lit "0". Elle va donc écrire "1", se déplacer à droite, et se mettre dans l'état 1
Étape 2 (état 1) : la tête est en position 1, elle lit "0". Elle écrit alors "1", se déplace à gauche, et revient en état 0.
Et ainsi de suite...
Bon, ce programme n'est pas spécialement intéressant, surtout qu'il ne s'arrête jamais. On pourrait cependant simuler avec une machine de Turing n'importe quel algorithme (comme le crible d'Erathostène, l'algorithme d'Euclide...), aussi compliqué soit-il. C'est finalement cette définition que l'on retiendra d'un algorithme : si on peut le simuler par une machine de Turing, c'est que c'est un algorithme.
Du coup, on peut théoriser beaucoup de chose sur les algorithmes, notamment celui du problème de l'arrêt, en utilisant un argument diagonal à la Cantor.
Pour cela, numérotons de 1 à ∞ l'ensemble (dénombrable) des machines de Turing, et appelons h(i,x) la fonction qui renvoie 1 si la machine n°i avec l'entrée x s'arrête, et 0 sinon. Cette fonction, si elle est mécanisable, résoudrait le problème de l'arrêt pour n'importe quel algorithme.
Notons de plus g(i) la fonction qui renvoie 0 si h(i,i)=0, mais qui n'est pas défini sinon. Supposons que cette dernière fonction est calculable et qu'elle correspond à la machine n°e. Mais alors, quelle est la valeur de g(e) ? Deux possibilités : soit 0, soit rien du tout.
Si g(e)=0, c'est que h(e,e)=0. Mais dans ce cas, e a une image par g, et donc, le programme n°e s'arrête bien : h(e,e)=1. Absurde !
Si g(e) n'est pas défini, c'est que h(e,e)=1. Dans ce cas, h(e,e)=0, car le programme n°e ne s'arrête pas. Absurde !
La fonction h n'est donc pas calculable !
Bref : le seul moyen de savoir si un algorithme boucle ou non, c'est de le lancer et d'attendre. Merci Turing d'avoir trouvé ça.
Être ou ne pas être Turing-complet ?
Par essence, tout ce qui est calculable l'est par une machine de Turing. Du coup, on dira d'un système qu'il est Turing-complet s'il permet (au moins en théorie) de calculer autant de choses qu'une machine de Turing. On retrouve de la Turing-complétude dans la plupart des langages de programmation (du C++ au brainf*ck), mais on le retrouve ailleurs... Top 5 dans endroits étrange où l'on retrouve de la Turing-complétude :
N°5 : Minecraft
N°4 : Little Big Planet
N°3 : L'eaurdinateur, un assemblage de siphons et de réservoirs.
N°2 : Le jeu de la vie
N°1 : Une véritable machine de Turing en Légo !
(à suivre...)
Sources :
The Alan Turing Year - page officielle dédiée à l'année Alan Turing.
Images : Alan Turing Memorial
