Alan Turing

Alan Mathison Turing (June 23, 1912 – June 7, 1954) was a British mathematician, logician, and cryptographer.

College and his work on computability

Due to his unwillingness to work as hard on his classical studies as on science and mathematics, Turing failed to win a scholarship to Trinity College, Cambridge, and went on to the college of his second choice, King's College, Cambridge. He was an undergraduate from 1931 to 1934, graduating with a distinguished degree, and, in 1935 he was elected a Fellow at King's on the strength of a dissertation on the Gaussian error function.

Related Topics:
Trinity College, Cambridge - King's College, Cambridge - 1931 - 1934 - 1935

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In his momentous paper "On Computable Numbers, with an Application to the Entscheidungsproblem" (submitted on May 28, 1936), Turing reformulated Kurt Gödel's 1931 results on the limits of proof and computation, substituting Gödel's universal arithmetics-based formal language by what are now called Turing machines, formal and simple devices. He proved that such a machine would be capable of performing any conceivable mathematical problem if it were representable as an algorithm, even if no actual Turing machine would be likely to have practical applications, being much slower than alternatives. Turing machines are to this day the central object of study in theory of computation. He went on to prove that there was no solution to the Entscheidungsproblem by first showing that the halting problem for Turing machines is uncomputable: it is not possible to algorithmically decide whether a given Turing machine will ever halt. While his proof was published subsequent to Alonzo Church's equivalent proof in respect to his lambda calculus, Turing's work is considerably more accessible and intuitive. It was also novel in its notion of a "Universal (Turing) Machine," the idea that such a machine could perform the tasks of any other machine. The paper also introduces the notion of definable numbers.

Related Topics:
May 28 - 1936 - Kurt Gödel - 1931 - Turing machine - Algorithm - Theory of computation - Entscheidungsproblem - Halting problem - Alonzo Church - Lambda calculus - Definable number

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Most of 1937 and 1938 he spent at Princeton University, studying under Alonzo Church. In 1938 he obtained his Ph.D. from Princeton; his dissertation introduced the notion of hypercomputation where Turing machines are augmented with so-called oracles, allowing a study of problems that cannot be solved algorithmically.

Related Topics:
1937 - 1938 - Princeton University - Ph.D. - Hypercomputation - Oracles

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Back in Cambridge in 1939, he attended lectures by Ludwig Wittgenstein about the foundations of mathematics. The two argued and disagreed vehemently, with Turing defending formalism and Wittgenstein arguing that mathematics is overvalued and does not discover any absolute truths.

Related Topics:
Ludwig Wittgenstein - Foundations of mathematics

~ ~ ~ ~ ~ ~ ~ ~ ~ ~