# An Early History of Recursive Functions and Computability from Gödel to Turing

Publisher:
Docent Press
Number of Pages:
297
Price:
17.99
ISBN:
9780983700401

Many mathematicians know that Turing analyzed the concept of computability and investigated computable functions well before electronic computers ever existed. But somewhat less familiar is that even earlier, several people were already studying, under various guises, what turned out to be the class of functions computable by a Turing machine. Adams’ book provides a detailed account of the development of this field of study during the first part of the twentieth century. Actually, the subtitle From Gödel to Turing understates the ground covered. Adams devotes nearly the first quarter of the book to significant pre-Gödel work on the recursive definitions of functions. Prominent names here include Grassmann, Dedekind, Peano, Skolem, Hilbert, and Ackermann.

Gödel’s seminal results on incompleteness brought to the fore what later came to be known as the class of primitive recursive functions, which contained all the functions he needed to encode logical goings-on into arithmetic, despite the minimal set of tools allowed in the construction of these functions. Shortly afterwards, Rózsa Péter proposed and pursued the investigation of recursions and functions defined by recursions as objects in their own right, as opposed to just tools in foundational studies. (Péter’s contributions to the field often receive short shrift, but one of the strengths of Adams’ treatment is the proper credit that he gives to her work.)

Meanwhile, during this same period, research at Princeton in logic conducted by Alonzo Church and his students, Stephen Kleene and J. Barkley Rosser, led to the formulation of the so-called λ-definability of functions. Kleene had also worked with the general recursive functions, which Gödel had developed extending the class of primitive recursive functions. It quickly transpired that general recursivity was equivalent to λ-definability and, after Turing’s work, that both were equivalent to computability by a Turing machine (and by a similar model independently introduced at the same time by Emil Post.)

All of the above-mentioned events from Gödel onwards cover a span of only about five years. Different people obtained several related results more or less independently, yet there were also various points of contact among the participants. The brief summary here gives just a hint of the complex history that emerges in Adams’ book. An appendix reproduces correspondence Adams received from key figures, and Kleene’s letters are particularly valuable in providing a first-hand account of the chronology and web of influences involved.

Adams’ text sometimes becomes a trifle repetitious. And it suffers from many typos that seem to have been introduced in the process of rendering the original, a typewritten 1983 doctoral thesis, into the present typeset edition. However, these are the traditional minor complaints about a highly informative and interesting book.

Leon Harkleroad admits to some bias here, having done historical research on and translated many works of Rózsa Péter.

Tuesday, June 21, 2011
Reviewable:
Yes
Include In BLL Rating:
Yes
Publication Date:
2011
Format:
Paperback
Category:
Monograph