You are here

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

Rod Adams
Docent Press
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Leon Harkleroad
, on

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.

Chapter 1 Early Recursive Definitions
  The First Recursive Definitions

Mathematical Thought at the Turn of the Nineteenth Century

Concluding Remarks
Chapter 2 Skolem's Contribution


The 1923 Paper

Comments and Conclusions
Chapter 3 Hilbert's Program and Gödel's Incompleteness Theorem

Hilbert's Approach

Hilbert's Foundational Papers

Results on Recursive Function Theory
  The Fate of Hilbert's Plan
  Gödel's 1931 Paper

Comments and Conclusions
Chapter 4 Early Work Leading to λ-Definable Functions


Church's System of Logic

The Development of Church's System

A Theory of Positive Integers in Formal Logic
  λ-Definable Functions

Decision Problems

Conclusion - The Inconsistency of Church's Logic
Chapter 5 General Recursive Functions


The Development of Ordinary Recursive Functions

General Recursive Functions
  Kleene's Normal Form for General Recursive Functions

The First Definition

An Example of the First Definition

The Second Definition
  Other Developments
Chapter 6 Church's Thesis
  λ-Definable vs. General Recursive
  Church's Thesis
  Reaction to Church's Thesis
  Recursive Unsolvability
  Constructivity and Conclusion
Chapter 7 Turing's Computable Functions
  Turing's Machines
  Post's Formulation and Later Devices
  Turing's Thesis
  The Non-Existence of Certain Machines
  Computable, Recursive and λ-Definable Functions
Appendix A Dates of Major Figures
Appendix B Letters
  Alonzo Church to Stephen C. Kleene, November 29, 1935
  Stephen C. Kleene to Author, July 28, 1977
  Alonzo Church to Author, April 21, 1978
  Hao Wang to Author, July 16, 1979
  Stephen C. Kleene to Author, July 17, 1979
  Jean van Heijenoort to Author, August 17, 1979
  Stephen C. Kleene to Author, November 3, 1981
  Stephen C. Kleene to Author, November 13, 1981
  J. Barkley Rosser to Author, November 19, 1981
  Stephen C. Kleene to Author, September 9, 1982
  Stephen C. Kleene to Author, April 4, 1983