Robert I. Soare
(University of Chicago)
Mathematics and the Turing Renaissance

David Hilbert greatly influenced the foundations of mathematics from 1900 to 1930. First, Hilbert wanted a finite consistency proof for mathematics, beginning with arithmetic. Second, he proposed the Entscheidungsproblem (decision problem), which was to find an algorithm to decide whether a given statement in the language of mathematics is valid. In 1931 Kurt Gödel dramatically refuted the first program.

Turing and Alonzo Church (Turing's subsequent thesis adviser at Princeton) worked independently on the Entscheidungsproblem. Their approach was: (1) to find a precise mathematical definition for the computable functions; and (2) to demonstrate that every informally computable function was captured by the formal definition. Gödel doubted that this was even possible because "the notion of a finite computation is not defined, but serves as a heuristic principle." In 1934 and 1935 Church proposed two different solutions, but Gödel rejected both, even though the second was based on Gödel's own definition in 1934 of a recursive function. In constrast, Gödel immediately accepted Turing's 1936 analysis and wrote, "That this really is the correct definition of mechanical computability was established beyond any doubt by Turing."

By 1937, the three definitions of computable functions had been proved mathematically equivalent. In retrospect, Church got it right and got it first. Why should Church not get the credit? The problem, however, was not simply a mathematical one. Turing demonstrated extraordinary creative insight into the nature of computability. Like Michelangelo, Turing saw the figure in the marble more clearly than anyone else. Why Turing and not Church? The reply is, "Why Michelangelo and not Donatello?" This lecture will include slides of Renaissance art and a careful comparison to make this point.