- Membership
- Publications
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Docent Press

Publication Date:

2011

Number of Pages:

297

Format:

Paperback

Price:

17.99

ISBN:

9780983700401

Category:

Monograph

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

[Reviewed by , on ]

Leon Harkleroad

08/6/2011

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 |

Introduction | |

The First Recursive Definitions | |

Mathematical Thought at the Turn of the Nineteenth Century | |

Concluding Remarks | |

Chapter 2 |
Skolem's Contribution |

Introduction | |

The 1923 Paper | |

Comments and Conclusions | |

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

Introduction | |

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 |

Introduction | |

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 |

Introduction | |

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 | |

Conclusion | |

Chapter 6 |
Church's Thesis |

Introduction | |

λ-Definable vs. General Recursive | |

Church's Thesis | |

Reaction to Church's Thesis | |

Recursive Unsolvability | |

Constructivity and Conclusion | |

Chapter 7 |
Turing's Computable Functions |

Introduction | |

Turing's Machines | |

Post's Formulation and Later Devices | |

Turing's Thesis | |

The Non-Existence of Certain Machines | |

Computable, Recursive and λ-Definable Functions | |

Conclusion | |

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 |

- Log in to post comments