Pour en revenir à notre fameux problème, dans son cours à Cambridge, Newmann explique que ce problème devrait se résoudre par une méthode définie, ou un processus mécanique.

C'est au cours d'un cross dans la campagne, au début de l'été 1935, que cette expression fit tilt dans l'esprit d'Alan et qu'il se convainquit que ce problème se résoudrait par une machine.

Il décida de partir de zéro, c'est à dire d'une machine fort simple, la machine à écrire. Sa mère en possédait une et Alan, tout enfant , avait rêvé d'en fabriquer une.

Lorsqu'on tape sur un clavier de machine, le résultat dépend de 2 choses :

Le caractère frappé, et de la "configuration" de la machine, c.a.d dans le cas présent de la position du panier (haut ou bas) , mais pas de celle du papier .

A chaque pas la machine lit le caractère écrit sur la bande (blanc ou 1).

En fonction de cette lecture et de la configuration de la machine définie dans une table (c'est ce qu'on appellera plus tard le programme) elle fera une ou plusieurs des actions suivantes :

Modifier la valeur de la case, ou la laisser.

Avancer ou reculer d'une case, ou ne pas bouger.

Modifier ou non la configuration dans la table.

Voici un exemple extrêmement simple de machine de Turing, configurée pour faire une addition. Nous voulons additionner 2 groupes de 1 séparés par un blanc, représentés sur la bande comme ci-dessous, la machine étant positionnée au départ à gauche case M.

En fait la machine se résume en ses tables de configurations.

En compliquant la table, on peut imaginer résoudre n'importe quel problème défini.

On peut même avec une table finie définir n'importe quel nombre, même ayant un nombre infini de décimales. Turing a donc imaginé une machine résolvant tous les problèmes existants. En utilisant un raisonnement analogue à celui de Cantor pour montrer l'existence des nombres irrationnels à partir des nombres rationnels, Alan a montré qu'on pouvait toujours trouver de nouveaux problèmes et que par conséquent il n'y avait pas de méthode définie pour résoudre toutes les questions mathématiques. Ceux qui désirent plus de détails sur cette question; qu'il serait trop long et trop compliqué de présenter ici, pourront avec profit consulter le livre de Hodges, pages 100 à 110.

Le même Hodges conclut le chapitre en disant que "Alan avait prouvé qu'il n'y avait pas de machine miraculeuse pour résoudre tous les problèmes mathématiques, mais dans son processus de démonstration, il avait découvert quelque chose d'également miraculeux, l'idée d'une machine universelle pouvant effectuer le travail de n'importe quelle machine".

Entre temps le logicien de Princeton Alonzo Church avait publié une solution à ce même problème et avait donc devancé Alan. Heureusement les deux approches étaient totalement différentes et il n'y avait eu aucune concertation entre les deux hommes. Celle de Church était basé sur un symbolisme mathématique très abstrait, alors que celle de Turing avec sa machine universelle était beaucoup plus porteuse d'avenir. Il est probable qu'il n'aurait pas abouti à une solution aussi originale s'il avait lu toute la littérature sur le sujet et s'il n'avait pas travaillé seul.

Cet imprévu retarda légèrement sa présentation à la London Mathematical Society qui eut lieu le 28 mai 1936 et portait sur "les nombres calculables avec une application au problème de la décidabilité". Dans la foulée Newman écrivit à Church pour lui vanter les mérites de Turing , lui faisant valoir que les 2 approches étaient très complémentaires et lui demander de l'accueillir à Princeton pour travailler avec lui. Alan postula alors au Procter fellowship de Princeton, qui en accorda 3, un au Collège de France, un à Oxford et un à Cambridge qui fut accordé à l'astronome Lyttelton. Malgré cet échec, il décida de partir, ses 300£ lui permettant de subsister chichement à Princeton.

Entre temps, il avait complété son mémoire à la lumière des travaux de Church et publié un complément le 28 août.

Il s'embarque le 23 septembre sur le Berengaria et suit à Princeton les cours de Church qui ne le passionnent pas. Il apprécie d'ailleurs assez peu la vie américaine. Il reçoit à ce moment les épreuves de "Computable numbers" qui seront publiées en janvier 1937 sans provoquer de grands remous dans la communauté scientifique, ce qui ne laisse pas de le décevoir. Church relut son texte pour une publication dans le journal de logique symbolique et y fit figurer les mots de Machine de Turing. Il lui proposa également de faire une conférence sur le même sujet. Celle-ci eut lieu le 2 décembre, et, là encore, Alan fut déçu par l'assistance. L'article dans le journal de logique symbolique n'eut pas plus de succès. Il faut dire que ce travail était uniquement théorique et qu'aucune application pratique ne pouvait être envisagée. Ce souci ne viendra que plus tard dans l'esprit d'Alan.

Il travaille alors sur le lambda calcul (méthode utilisée par Church pour la décidabilité) et sur la théorie des groupes, ce qui le met en contact avec von Neumann;

A la suite de ces travaux, on lui propose de rester une année supplémentaire à Princeton.

N'ayant pas obtenu de poste à Cambridge, il accepte sans enthousiasme, et décide de préparer un PhD, portant sur les implications du théorème de Gödel.

Il retourne néanmoins passer l'été en Angleterre et s'embarque le jour de ses 25 ans sur le Queen Mary. Il passe à Cambridge un été studieux en travaillant sur le suivi de Computable numbers, où quelques corrections sont à faire, sur de nouvelles idées en logique mathématique, et sur la théorie des nombres .

Il reprend le bateau et de retour à Princeton, et s'inquiétant des risques de guerre avec l'Allemagne, il commence à s'intéresser aux méthodes de chiffrement. Celles-ci mettant en œuvre la multiplication de grands nombres , étudie un multiplicateur binaire à relais , et le fabrique lui-même au labo de physique et miracle, il fonctionne ! En effet Alan était particulièrement maladroit de ses mains et avait peu de goût pour les activités pratiques.

Il travailla aussi sur les zeta-fonctions de Riemann, mais sa principale activité fut sa thèse de PhD sur le théorème de Gödel.

Son intention était de rentrer à Cambridge, mais von Neumann lui proposa un poste d'assistant à l'IAS (Institute for Advanced Studies) à Princeton, à 1500£ par an, ce qui était évidemment un excellent tremplin pour une carrière universitaire aux Etats Unis.

Mais Alan tenait à entrer au Kings. Il soutint sa thèse le 31 mai, obtint son PhD le 21 juin et débarqua du Normandie à Southampton le 18 juillet, avec son multiplicateur dans ses valises.

A cette époque le GS and CS cherchait à embaucher, et la compétence et l'intérêt d'Alan pour les problèmes de chiffrement vinrent aux oreilles de Denniston. Tout en donnant quelques cours à Cambridge, Alan s'impliqua de plus en plus avec le GS and CS, participant à des conférences, ramenant des travaux à Cambridge, jusqu'au fameux coup de téléphone du 3 septembre 1939. Comme nous l'avons déjà vu, Alan passa toute la guerre à Bletchley park. Nous verrons la prochaine fois la suite de sa carrière et son implication dans la naissance de l'informatique britannique, et en particulier, le Manchester Mark 1 qui est généralement considéré comme le premier ordinateur au monde ayant tourné un programme.