Early life and career
The son of a civil servant, Turing was educated at a top private school. He entered the University of Cambridge to study mathematics in 1931. After graduating in 1934, he was elected to a fellowship at King’s College (his college since 1931) in recognition of his research in probability theory. In 1936 Turing’s seminal paper “On Computable Numbers, with an Application to the Entscheidungsproblem [Decision Problem]” was recommended for publication by the American mathematical logician Alonzo Church, who had himself just published a paper that reached the same conclusion as Turing’s, although by a different method. Turing’s method (but not so much Church’s) had profound significance for the emerging science of computing. Later that year Turing moved to Princeton University to study for a Ph.D. in mathematical logic under Church’s direction (completed in 1938).
The Entscheidungsproblem
What mathematicians called an “effective” method for solving a problem was simply one that could be carried by a human mathematical clerk working by rote. In Turing’s time, those rote-workers were in fact called “computers,” and human computers carried out some aspects of the work later done by electronic computers. The Entscheidungsproblem sought an effective method for solving the fundamental mathematical problem of determining exactly which mathematical statements are provable within a given formal mathematical system and which are not. A method for determining this is called a decision method. In 1936 Turing and Church independently showed that, in general, the Entscheidungsproblem problem has no resolution, proving that no consistent formal system of arithmetic has an effective decision method. In fact, Turing and Church showed that even some purely logical systems, considerably weaker than arithmetic, have no effective decision method. This result and others—notably mathematician-logician Kurt Gödel’s incompleteness results—dashed the hopes, held by some mathematicians, of discovering a formal system that would reduce the whole of mathematics to methods that (human) computers could carry out. It was in the course of his work on the Entscheidungsproblem that Turing invented the universal Turing machine, an abstract computing machine that encapsulates the fundamental logical principles of the digital computer.
The Church-Turing thesis
An important step in Turing’s argument about the Entscheidungsproblem was the claim, now called the Church-Turing thesis, that everything humanly computable can also be computed by the universal Turing machine. The claim is important because it marks out the limits of human computation. Church in his work used instead the thesis that all human-computable functions are identical to what he called lambda-definable functions (functions on the positive integers whose values can be calculated by a process of repeated substitution). Turing showed in 1936 that Church’s thesis was equivalent to his own, by proving that every lambda-definable function is computable by the universal Turing machine and vice versa. In a review of Turing’s work, Church acknowledged the superiority of Turing’s formulation of the thesis over his own (which made no reference to computing machinery), saying that the concept of computability by a Turing machine “has the advantage of making the identification with effectiveness…evident immediately.”
Top comments (0)