Alan Turing - University and Work On Computability

University and Work On Computability

After Sherborne, Turing studied as an undergraduate at King's College, Cambridge from 1931 to 1934, where he gained first-class honours in Mathematics. In 1935, at the young age of 22, he was elected a fellow at King's on the strength of a dissertation in which he proved the central limit theorem, despite the fact that he had failed to find out that it had already been proved in 1922 by Jarl Waldemar Lindeberg.

In 1928, German mathematician David Hilbert had called attention to the Entscheidungsproblem (decision problem). In his momentous paper "On Computable Numbers, with an Application to the Entscheidungsproblem" (submitted on 28 May 1936 and delivered 12 November), Turing reformulated Kurt Gödel's 1931 results on the limits of proof and computation, replacing Gödel's universal arithmetic-based formal language with the formal and simple hypothetical devices that became known as Turing machines. He proved that some such machine would be capable of performing any conceivable mathematical computation if it were representable as an algorithm. He went on to prove that there was no solution to the Entscheidungsproblem by first showing that the halting problem for Turing machines is undecidable: in general, it is not possible to decide algorithmically, whether a given Turing machine will ever halt.

Although Turing's proof was published shortly after Alonzo Church's equivalent proof using his lambda calculus, Turing had been unaware of Church's work. Turing's approach is considerably more accessible and intuitive than Church's. It was also novel in its notion of a 'Universal Machine' (now known as a Universal Turing machine), with the idea that such a machine could perform the tasks of any other machine, or in other words, is provably capable of computing anything that is computable. Von Neumann acknowledged that the central concept of the modern computer was due to this paper. Turing machines are to this day a central object of study in theory of computation.

From September 1936 to July 1938 he spent most of his time studying under Church at Princeton University. In addition to his purely mathematical work, he studied cryptology and also built three of four stages of an electro-mechanical binary multiplier. In June 1938 he obtained his PhD from Princeton; his dissertation, Systems of Logic Based on Ordinals, introduced the concept of ordinal logic and the notion of relative computing, where Turing machines are augmented with so-called oracles, allowing a study of problems that cannot be solved by a Turing machine.

Back in Cambridge, he attended lectures by Ludwig Wittgenstein about the foundations of mathematics. The two argued and disagreed, with Turing defending formalism and Wittgenstein propounding his view that mathematics does not discover any absolute truths but rather invents them. He also started to work part-time with the Government Code and Cypher School (GCCS).