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).
Read more about this topic: Alan Turing
Famous quotes containing the words university and/or work:
“It is in the nature of allegory, as opposed to symbolism, to beg the question of absolute reality. The allegorist avails himself of a formal correspondence between “ideas” and “things,” both of which he assumes as given; he need not inquire whether either sphere is “real” or whether, in the final analysis, reality consists in their interaction.”
—Charles, Jr. Feidelson, U.S. educator, critic. Symbolism and American Literature, ch. 1, University of Chicago Press (1953)
“What we often take to be family values—the work ethic, honesty, clean living, marital fidelity, and individual responsibility—are in fact social, religious, or cultural values. To be sure, these values are transmitted by parents to their children and are familial in that sense. They do not, however, originate within the family. It is the value of close relationships with other family members, and the importance of these bonds relative to other needs.”
—David Elkind (20th century)