ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

TURING Alan Mathison, anglais, 1912-1954

Passionné dès son plus jeune âge par les énigmes logiques et la cryptologie, Alan Turing étudia au collège de Sherbone et se fait remarquer par ses capacités d'apprentissage des sciences, mathématiques en particulier. En 1930, il entre au King's College de Cambridge et quatre ans plus tard le brillant étudiant obtient une bourse afin de poursuivre ses recherches. Il travaille sur la logique mathématique. C'est ainsi qu'il publiera à 24 ans, son article sur le problème de la décision.

Cette même année 1936, dans le cadre du concept de calculabilité lié à celui de la décision (» ci-après), vaste sujet étudié par Church aux États-Unis et Gödel en Autriche, dans le cadre de la refondation des mathématiques, Turing inventa une machine algorithmique abstraite, qu'il qualifie de « machine à penser », préfigurant l'informatique avec la théorie des algorithmes récursifs et la construction des ordinateurs, accélérée en particulier (hélas?) par la seconde guerre mondiale : décryptage  des messages secrets, fabrication de la bombe atomique.

Appelées aujourd'hui machines (universelles) de Turing, ces machines sur papier étaient censées interpréter des instructions logiques (affectations, tests, branchements) et susceptibles de dégager les catégories de problèmes résolubles de logique propositionnelle (c'était l'ambition de Leibniz), à savoir ceux dont le programme (algorithme qui le caractérise) s'arrête après un nombre fini d'étapes en "répondant" true (vrai) ou false (faux).

Issu du latin recurrere = courir en arrière, l'épithète récursif utilisé à l'époque de Turing est dû à Gödel dans l'exposé de son théorème d'incomplétude (1931). Au sens des machines de Turing, il s'agit d'une suite finie (s) d'instructions (algorithme) procédant à des branchements dans (s) et se terminant dans (s) : le processus peut ainsi courir en arrière mais ne boucle pas indéfiniment. Sinon, le problème n'est pas résoluble.

   En dehors de la littérature sur le sujet, les liens sur le Web sont nombreux. On trouvera in fine (» réf. 2, 5, 6 en particulier) une description claire et instructive de ces "machines" abstraites. Sur Dailymotion, on visionnera cette vidéo décrivant une machine de Turing concrétisée en Logo (!) en l'honneur d'Alan Turing par des étudiants en master d'informatique de l'ENS de Lyon à l'occasion du centenaire de sa naissance.

Al-Khwarizmi et le concept d'algorithme : »           Fonctions &  procédures récursives : »       Complexité algorithmique : »

Fort de ses succès, Turing, recommandé par ses professeurs quitte l'Angleterre pour les États-Unis (1936-38) et rencontre Von Neumann (qui mit à profit les idées de Turing dans la conception des premiers ordinateurs américains pour la mise au point de la bombe atomique), ainsi que Church qui dirigea son doctorat (Systems of logic based on ordinals, 1938).

Sans doute eu égard aux impératifs de communication sécurisée en temps de guerre, le début des années 1940 voit naître une toute nouvelle branche des mathématiques : la théorie de l'information dont Shannon, avec lequel il travailla entre 1941 et 1943, fut un des principaux précurseurs aux USA. Turing met ses compétences au service de son pays dans le décryptage des messages ennemis et réussit à casser les codes secrets du système allemand Enigma.

Après la guerre, Turing sera professeur de mathématiques à Manchester où il entame (dès 1950) la concrétisation d'un calculateur électronique à lampes (le transistor, inventé en 1947, n'a pas assez de puissance).

Durant les quatre dernières années de sa vie, Turing étudie la morphogenèse (étude de la structure des organes au cours de leur évolution) et initie ce que l'on appelle aujourd'hui l'intelligence artificielle. En 1953, une chaire en théorie du calcul, première du genre, lui est attribuée à Manchester. Mais brimé et poursuivi en Angleterre pour homosexualité, condamné à la castration chimique, Turing se suicida. Fin tragique, à 42 ans, d'un logicien de génie. 

Ce n'est qu'en 1967 que l'homosexualité fut dépénalisée au Royaume-Uni. Et il fallut attendre l'année 2013, pour que la reine Elisabeth II graciât et réhabilitât Alan Turing à titre posthume.

» Le terme Informatique fut introduit en France en 1962, voulant signifier science du traitement l'information. Les anglo-saxons préféraient alors computer science (science du calcul) puis computing. En France, le mot ordinateur est adopté en 1955 à l'initiative du journaliste et romancier Jacques Perret (1901-1992). En anglais, on parle de computer. Noter que compter est une forme contractée du latin computare. Le moyen-âge nous a transmis comput pour désigner le calcul des dates des fêtes chrétiennes mobiles. On parle aussi de computation pour désigner leur méthode de calcul » calculus

    » The Turing Machine Simulator : http://ironphoenix.org/tril/tm/            »  Babbage

Le problème de la décision (ou problème de l'arrêt) résolu par la négative :

A peine âgé de 20 ans, Turing se pencha sur un problème que se posait Schröder dès 1895 et repris par Hilbert en 1918, appelé problème de la décision (en allemand : Entscheidungsproblem) à savoir la décidabilité d'un énoncé de logique mathématique  :

Pour un langage donné (» Frege), peut-on exhiber un algorithme universel permettant
de prouver qu'un énoncé est vrai ou faux ?

Utilisant à des fins d'automatisation théorique a priori indépendantes de ce problème, le concept de fonctions récursives (on devrait plutôt dire -et on dit aussi- calculables) outil de base de sa fameuse « machine », Turing a reformulé ce problème en termes tout à fait nouveau à l'époque :

Problème de l'arrêt :   

Peut-on exhiber un programme universel permettant de prouver qu'un autre programme est vrai ou faux ?
 le programme s'arrête après un nombre fini d'étapes en "répondant" vrai ou faux (oui ou non).

Un énoncé décidable devient alors équivalent à une fonction calculable : en 1936, il put ainsi répondre négativement au problème de la décision dans un article publié auprès de la London Mathematical Society : On computable numbers with an application to the Entscheidungsproblem.

Théorème de Church :    

Church aboutit à la même conclusion au moyen de ses fonctions λ-définissables, fonctions s'avérant équivalentes aux fonctions calculables de Turing :

Aucune théorie fondée sur la logique des prédicats du premier ordre ne permet d'exhiber un algorithme général
permettant d'établir qu'une formule de la théorie est vraie ou fausse.

» Kalmár , Rózsa Péter , Post , Frege , Tarski , Markov (fils) , Cook

Théorie mathématique : »            Fonctions &  procédures récursives, exemples simples : »

Turing et le « chiffre » :

En 1941, Turing mit ses compétences aux services de l'armée britannique lors de la seconde guerre mondiale en concevant avec Max Newman (1897-1984), un de ses professeurs à Cambridge, le Colossus 1, une machine mécanique qui fut capable, après près de deux ans de recherches en conception et fabrication, de déchiffrer les codes de la célèbre machine allemande Enigma, d'origine hollandaise et utilisée pour la transmission des messages secrets. On estime que grâce au génie de Turing, 14 000 000 de vies humaines furent épargnées et la guerre abrégée d'au moins deux années.

La conception du Colossus, concrétisation de la « machine à penser », resta top secret jusqu'en 1975 ! Turing contribuera aussi à la mise en place du premier puissant ordinateur : le Mark 1, qui vit le jour à Harvard (U.S.A.).

» Von Neumann            Cryptologie et petit exercice de « chiffre »... : »

   Concernant le terme déchiffrer, rappelons que le chiffre, en français, désigne l'institution spécialisée dans le codage et le décodage des mes messages secrets. Le mot chiffre provient de l'arabe et de l'italien : sifrone , en arabe, désigne zéro et cifrare, en italien signifie coder. Au 12è siècle, l'introduction du système décimal en Italie, et donc du zéro en particulier, fut perçu comme un codage mystérieux réservé aux initiés.

Prix Turing :

Ce prix récompense des travaux en technologie informatique. Il est en quelque sorte le complément "hardware" du prix Gödel récompensant des travaux théoriques ("software"). Créé en 1966 par l'ACM (Association for Computing Machinery, USA), ce prix très réputé dans le monde de l'informatique, est à la hauteur de la récompense : sponsorisé par Intel et Google, il rapporte 250 000 $US, soit 50 fois le montant du prix Gödel, 25 fois celui de la médaille Fields. Pour mémoire le prix Nobel rapporte environ 920 000 euros, soit l'équivalent de 1 160 000 $US.

On trouvera sur le site de l'ACM (» réf.12) la liste des lauréats depuis 1966 : la page renvoie aux motivations et présente une biographie des récipiendaires.

»  Dijkstra , Cook , Hamming


   Pour en savoir plus :

  1. La machine de Turing , théorie des nombres calculables, fonctions récursives, par Alan Turing (traduit de l'anglais).
    Commentaires et compléments de J. Y. Girard, Coll. Points Sciences, Ed. du Seuil.

  2. Algorithmique et Calculabilité (Université de Liège), dont machines de Turing :
    http://www.discmath.ulg.ac.be/cours/main_calcul.pdf
  3. Computing machinery and intelligence, par Alan Tuing (1950).
  4. Fonctions récursives et Machines de Turing , cours et exercices de Nhan Le Tanh (Univ. Nice) :
    http://www.i3s.unice.fr/~nlt/cours/licence/it/s5_itdut_poly.pdf
  5. Machines de Turing, Calculabilité et décidabilité, cours d'Alain Lecomte, univ. Paris VIII :
    http://lecomte.al.free.fr/ressources/LIC_MIASS/coursTuring.pdf
  6. Algorithmes polynomiaux de classes P et NP et problème de la décision :
    http://www.labri.fr/perso/betrema/MC/MC8.html
  7. Le λ-calcul (lambda calcul ) de Church : cours de Jean Betrema :
    http://www.labri.fr/perso/betrema/MC/MC6.html
  8. Techniques récursives en programmation, D.W. Barron, Ed. Dunod, Paris - 1970
  9. Dictionnaire des Mathématiques, fondements, probabilités, applications
    Encyclopædia Universalis, Récusivité, p.518-536
  10. Les algorithmes, Que sais-je n°2928, Patrice Hernert, P.U.F., Paris.
  11. The Alan Turing Home page par Andrew Hodges.
  12. Site de l'Association for Computing Machinery (ACM)  : http://amturing.acm.org/alphabetical.cfm

Fortet  Delange
© Serge Mehl - www.chronomath.com