Computability Theory in the Twentieth Century

Martin Davis

Some of the highlights in the development of computability/recursion theory will be surveyed. The importance of recursive definitions became evident in some of the foundational work of Dedekind and Peano around the turn of the century. In this same period, Axel Thue studied operations on strings. Moving to the 1920s Skolem proposed to use recursive definitions to found arithmetic in a free variable calculus, and Hilbert wanted to use them in order to prove the Continuum Hypothesis. In 1931 Gödel used the class of (what are now called) primitive recursive functions in his classic paper proving the existence of undecidable arithmetic propositions in formal systems. In lectures in 1934, Gödel suggested that if the notion of recursive definition were appropriately extended, it might lead to a class of functions coextensive with those algorithmically calculable. Very soon thereafter, Church concluded that the class of functions expressible in his lambda-calculus indeed had this very property and his student Kleene proved that this lambda-definability was equivalent to Gödel’s recursiveness. Meanwhile in England, Turing proposed his notion of computability by an abstract machine, and provided an analysis of the process of computation, concluding that his machines were sufficient to encompass any computation. It soon became clear that Turing’s notion was equivalent to the other two. Post had found his own (also equivalent to the others) path in the 1920s but had never managed to produce a convincing development. After Church’s work had appeared in print, but before he knew about Turing’s work, Post produced his own variant of Turing’s machines.

The year 1936, in which the Journal of Symbolic Logic was launched, saw the publication of the proofs of the equivalence of the various notions, and the first example of an important problem that could be proved unsolvable using the new techniques, namely the proof by Turing and by Church that Hilbert’s Entscheidungsproblem is algorithmically unsolvable. Computability theory was now launched as a coherent subject that could be developed in a number of directions, only highlights of which can be dealt with in this talk.

In a seminal paper in 1938 Kleene introduced the notion of partial recursive function, proved the S-m-n theorem and the two recursion theorems, and applied this apparatus to the constructive ordinals. In a 1943 paper he studied the arithmetic hierarchy. Turing in his 1939 dissertation had introduced the seminal notion of computability relative to an oracle. Post in a highly influential address to the American Mathematical Society in 1944 launched the study of recursively enumerable (r.e.) sets and their degrees and posed the question (“Post’s problem”) of the existence of an non-computable r.e. set of lower degree than that of his creative set K. Post also showed how the levels of the arithmetic hierarchy were related to the “jump” from a set to sets r.e. in that set. Davis and Mostowski (1950) studied extensions of the arithmetic hierarchy (the hyperarithmetic hierarchy) later studied by Kleene and Spector.

Post and Markov each proved the unsolvability of the word problem for semi-groups, and Novikov and Boone later extended this to the unsolvability of the word problem for groups. In 1950 Davis moved towards a proof of the unsolvability of Hilbert’s 10th problem by obtaining an arithmetic normal form for r.e. sets. At the same time Julia Robinson approached the problem from the opposite direction studying the problem of defining exponentiation by a Diophantine equation. Joined by Hilary Putnam the two approaches met in the middle in their 1960 proof of the unsolvability of the decision problem for exponential Diophantine equations. To complete the proof of the unsolvability of Hilbert’s 10th problem, a Diophantine equation whose solution grow exponentially was needed and such an equation was supplied in Matiyasevich’s (1970) ingenious construction.

The key to the solution of Post’s problem was the “priority method” introduced by Friedberg and Muchnik (1957): this method enabled infinitely many apparently conflicting requirements to all be ultimately satisfied using a limit process of which the result was an r.e. set. This initiated a continuing development in which great virtuosity was applied to obtain a number of surprising theorems. In this talk two examples due to Sacks will be explained.

Address: Visiting Scholar UC Berkeley – Professor Emeritus, New York University, USA

E-mail: martin@eipye.com