Alan Mathison Turing, né le 23 juin 1912 à Londres et mort le 7 juin 1954 à Wilmslow, est un mathématicien et cryptologue britannique, auteur de travaux qui fondent scientifiquement l'informatique.

​

Pour résoudre le problème fondamental de la décidabilité en arithmétique, il présente en 1936 une expérience de pensée que l'on nommera ensuite machine de Turing et des concepts de programmation et de programme, qui prendront tout leur sens avec la diffusion des ordinateurs, dans la seconde moitié du xxe siècle. Son modèle a contribué à établir définitivement la thèse de Church, qui donne une définition mathématique au concept intuitif de fonction calculable. Après la guerre, il travaille sur un des tout premiers ordinateurs, puis contribue au débat sur la possibilité de l'intelligence artificielle, en proposant le test de Turinga. Vers la fin de sa courte vie, il s'intéresse à des modèles de morphogenèse du vivant conduisant aux « structures de Turing ».

Durant la Seconde Guerre mondiale, il joue un rôle majeur dans la cryptanalyse de la machine Enigma, utilisée par les armées allemandes. Ses méthodes permirent de casser ce code et, selon plusieurs historiens, de raccourcir la capacité de résistance du régime nazi de deux ans et épargner la vie de quatorze millions de personnes.

​

En 1952, un fait divers lié à son homosexualité lui vaut des poursuites judiciaires. Pour éviter la prison, il choisit la castration chimique par prise d'œstrogènes. Turing est retrouvé mort dans la chambre de sa maison à Manchester, par empoisonnement au cyanure, le 7 juin 1954. La reine Élisabeth II le gracie à titre posthume en 2013. Il n'a été reconnu comme héros de guerre que 55 ans après sa mort.

​

Alan Turing est né à Maida Vale du fonctionnaire d'administration coloniale Julius Mathison Turing et de sa femme Ethel Sarah Turing (née Stoney). À partir de l'âge d'un an, le jeune Alan est élevé par des amis de la famille Turing.

​

Sa mère rejoint alors son père qui était en fonction dans l’Indian Civil Service. Ils reviendront au Royaume-Uni à la retraite de Julius en 1926. Très tôt, le jeune Turing montre les signes de son génie. On relate qu'il apprit seul à lire en trois semaines. De même, il montra une affinité précoce pour les chiffres et les énigmes.

​

Ses parents l'inscrivent à l'école St. Michael's à l'âge de six ans. La directrice reconnaît rapidement son talent, comme beaucoup de ses professeurs au cours de ses études au Marlborough College, sans que cela n'ait guère d'influence sur sa carrière scolaire. À Marlborough, l'enfant solitaire et introverti est confronté pour la première fois à des camarades plus âgés que lui et devient l'une de leurs têtes de turc. À 13 ans, il rejoint la Sherborne School. Son premier jour de classe ne passe pas inaperçu, la presse locale en rendant même compte. Le jour de la rentrée est celui de la grève générale de 1926, mais le jeune Turing, décidé envers et contre tout à faire sa rentrée, parcourt pour ce faire seul à bicyclette les 90 km qui séparent son domicile de son école, s'arrêtant même pour la nuit dans un hôtel.

​

Le penchant de Turing pour les sciences ne lui apporte le respect ni de ses professeurs, ni des membres de l'administration de Sherborne, dont la définition de la formation mettait plus en valeur les disciplines classiques (littérature, arts, culture physique) que les sciences. Malgré cela, Turing continue de faire des prouesses dans les matières qu'il aime, résolvant des problèmes très ardus pour son âge. En 1928, il découvre les travaux d'Albert Einstein et comprend, alors qu'il a à peine 16 ans, qu'ils remettent en cause les axiomes d'Euclide et les lois de la mécanique céleste de Galilée et Newton, à partir d'un texte de vulgarisation où ces conséquences ne sont pas indiquées explicitement.

​

À la Sherborne School, Turing se lie en 1927 d'une grande amitié avec son camarade Christopher Morcom, passionné de sciences et de mathématiques comme lui. Quand Morcom meurt en février 1930 des complications de la tuberculose bovine contractée après avoir bu du lait de vache infecté, Turing, bien que matérialiste et athée, n'admet pas la disparition complète d'un esprit aussi brillant. Persuadé que l'esprit de Morcom continue à exister, il décide d'incarner le destin scientifique qu'aurait dû avoir Morcom.

​

À cause de son manque d'enthousiasme à travailler autant dans les matières classiques que dans les matières scientifiques, Turing échoue plusieurs fois à ses examens. Il n'est admis qu'au King's College de l'université de Cambridge, alors qu'il avait demandé Trinity College en premier choix. Il étudie de 1931 à 1934 sous la direction de Godfrey Harold Hardy, mathématicien alors titulaire de la chaire sadleirienne puis responsable du centre de recherches et d'études en mathématiques. Il suit également les cours d'Arthur Eddington et, la dernière année, de Max Newman qui l'initie à la logique mathématique. En 1935, Turing est élu fellow du King's College, l'équivalent d'une bourse de thèse, grâce à sa démonstration du théorème central limite.

​

En 1928, l'Allemand David Hilbert énonce le problème de la décision — connu sous le nom allemand d'« Entscheidungsproblem ») —. Pour cela il se place dans les théories axiomatiques et demande s'il est possible de trouver une méthode « effectivement calculable » pour décider si une proposition est démontrable. Pour résoudre ce problème, il faut caractériser ce qu'est un procédé effectivement calculable6. C'est ce que fait Turing dans son remarquable article de 1936, 

 

« On Computable Numbers, with an Application to the Entscheidungsproblem », en imaginant, non une machine matérielle, mais un « être calculant », qui peut être indifféremment un appareil logique très simple ou un humain bien discipliné appliquant des règles — comme le faisaient les employés des bureaux de calcul ou les artilleurs à l'époque. Dans le cours de son raisonnement, il démontre que le problème de l'arrêt d’une machine de Turing ne peut être résolu par algorithme : il n’est pas possible de décider avec un algorithme (c’est-à-dire avec une machine de Turing) si une machine de Turing donnée s’arrêtera. Bien que sa preuve ait été publiée après celle d'Alonzo Church, le travail de Turing est plus accessible et intuitif. Il est aussi complètement nouveau dans sa présentation du concept de « machine universelle » (de Turing), avec l'idée qu'une telle machine puisse accomplir les tâches de n'importe quelle autre machine. L'article présente également la notion de nombre réel calculable. Il déduit de l'indécidabilité du problème de l'arrêt que l'on peut définir des nombres réels qui ne sont pas calculables. Il introduit les concepts de programme et de programmation.

​

Turing passe la plus grande partie de 1937 et de 1938 à travailler sur divers sujets à l'université de Princeton, sous la direction du logicien Alonzo Church qui a déjà encadré le travail de Stephen Kleene sur la récursivité. Il obtient en mai 1938 son Ph.D.12 de l'université de Princeton ; son manuscrit présente la notion d'hypercalcul, où les machines de Turing sont complétées par ce qu'il appelle des oraclesd, autorisant ainsi l'étude de problèmes qui ne peuvent pas être résolus de manière algorithmique. L'appellation de « machine de Turing » vient de Church, son directeur de thèse, qui l'emploie pour la première fois dans un compte-rendu du travail de son élève dans le Journal of Symbolic Logic.

​

Turing obtient des résultats importants sur le lambda-calcul, notamment en montrant son équivalence avec son propre modèle de calculabilité13, en inventant le combinateur de point-fixe qui porte son nom14 et en proposant la première démonstration de la normalisation du lambda calcul typé.

​

De retour à Cambridge en 1939, il assiste à des cours publics de Ludwig Wittgenstein sur les fondements des mathématiques. Tous deux discutent avec véhémence et constatent leur désaccord, Turing défendant le formalisme alors que Wittgenstein pense que les mathématiques sont surestimées et qu'elles ne permettent pas de découvrir une quelconque vérité absolue.

​

Fin 1938, après les accords de Munich, la Grande-Bretagne comprend enfin que le nazisme est une menace, et commence à se réarmer. Turing fait partie des jeunes cerveaux appelés à suivre des cours de chiffre et de cryptanalyse à la Government Code and Cypher School (GC&CS). Juste avant la déclaration de guerre, il rejoint le centre secret de la GC&CS à Bletchley Park. Il y est affecté aux équipes chargées du déchiffrage de la machine Enigma utilisée par les forces armées allemandes. Ce travail profite initialement des percées effectuées par les services secrets polonais du Biuro Szyfrów16 et du renseignement français au PC Bruno, que Turing visite entre décembre 1939 et les premiers mois de 1940 et d'où il rapporte des copies des feuilles de Zygalski.

 

Mais, en mai 1940, les Allemands perfectionnent leur système cryptographique. Turing participe aux recherches qui permettent de pénétrer les réseaux de l'armée de terre et de l'aviation. Il conçoit des méthodes mathématiques et des versions améliorées de la « Bombe » polonaise, machine électromécanique permettant d'essayer rapidement des ensembles de clés potentielles sur des blocs de communication d'Enigma. Une fois l'affaire lancée, Turing prend la tête de l'équipe chargée de trouver les clés bien plus hermétiques des réseaux de l'Enigma navale. Ces percées décisives redonnent à la Grande-Bretagne un avantage temporaire dans les batailles d'Angleterre, de Libye et de l'Atlantique.

​

Jusqu'au milieu des années 1970, seuls quelques anciens cryptanalystes français et polonais avaient publié quelques informations sur la lutte contre Enigma dans leurs pays respectifs ; les capacités de décryptage de Bletchley Park et l'opération Ultra restaient un secret militaire absolu en Grande-Bretagne. Puis les autorités britanniques déclassifièrent progressivement les techniques de décryptage d'Enigma jusqu'à 2000.