À 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, notamment aux problèmes fondamentaux posés quelques années plus tôt par l'Allemand David Hilbert. 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 limite8. Son remarquable article de 1936, « On Computable Numbers, with an Application to the Entscheidungsproblem »9,10, répond à un problème posé par Hilbert dans les théories axiomatiques, le problème de la décision (« Entscheidungsproblem ») : est-il possible de trouver une méthode « effectivement calculable » pour décider si une proposition est démontrable ou non. Pour montrer que cela n'est pas possible, il faut caractériser ce qu'est un procédé effectivement calculable11. Turing le fait 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 à 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êtera12. Bien que sa preuve ait été publiée après celle d'Alonzo Church, le travail de Turing est plus accessible et intuitif12. 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. Turing passe la plus grande partie de 1937 et de 1938 à travailler sur divers sujets à l'université de Princeton, sous la direction d'Alonzo Church. Il obtient en mai 1938 son Ph.D.13 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 oraclesnote 2, 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. De retour à Cambridge en 1939, il participe à 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.