Ce document (ici l'original)
a été remis en page et modifié à partir de
celui écrit par Jean Marc FEDOU.
Alan Turing (1912-1954)
Une bibliographie remarquable : "Alan Turing ou l'enigme de l'intelligence",
par Andrew Hodges, Bibliothèque scientifique Payot, 1988.
1912 (23 Juin) : Né à Londres
1928 : Etude de la relativité
1932-35 : Etude de la méchanique quantique, la relativité,
la logique
1936 : La machine de Turing
1940 : Machine à décripter
1954 (7 Juin) Mort par empoisonnement au cyanure
Ses travaux touchent des domaines très variés (Informatique,
Réseaux neuronaux, Intelligence artificielle, logique ...)
Machines de Turing
Une bande infinie
Un jeu de caractères A,B...
Un ensemble fini d'états S,T ...
Des opérations :
Lecture
Ecriture
Déplacement à gauche (1 case)
Déplacement à droite ( 1 case)
Un ensemble de règles qui précise, pour chaque état,
le comprtement de la machine à l'étape suivant. Plus précisément,
La lettre à écrire dans la case en cours
Le nouvel état de la machine
Le sens de déplacement de la tête de lecture
La machine qui boucle sur deux états
L'addition de deux nombres (cf p 158 "Les mathématiques d'aujourd'hui" chez Belin)
La machine de Turing a permis de classifier les problèmes
Les problèmes calculables sont les problèmes résolus
par une machine de Turing.
Il existe des problèmes non calculables : par exemple le problème
de l'arrêt de la machine de Turing.
Les problèmes de complexité P : ceux qui sont résolubles
par une machine de Turing en temps pôlynomial. De fait ce sont les
seuls problèmes effectivement résolubles par ordinateur.
Les problèmes N-P (Non déterministe en temps pôlynomial)
qui sont résolus à l'aide d'une machine de Turing non déterministe.
Ceux sont les problèmes qui "reconnaissent" une solution en temps
polynomial.
Les problèmes intrinsèquement difficiles, comme celui de
l'arrêt d'une machine de Turing.
