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

Rod Adams

About the Author

Rod Adams received his PhD from the School of Information Sciences at The Hatfield Polytechnique under the supervision of Dr. Dale Johnson. Dr. Adams is currently a Professor of Neural Computation at the University of Hertfordshire.

Reviews

This detailed study of the history of definition by recursion from the nineteenth century through the 1930s includes valuable correspondence between the author and some of the key figures who discovered the crucial connection of such definitions with effective calculability.

Martin Davis
Professor Emeritus, Courant Institute, and Visiting Scholar, UC Berkeley

Recursive functions and related logical notions of computability are fundamental to modern mathematical logic. Kurt Gödel used them in a crucial way in his celebrated result on the incompleteness of formal arithmetic. Before Gödel, mathematicians and logicians such as Dedekind, Peano, Skolem, Hilbert, and Ackermann had explored them for reasons related to the foundations of mathematics. Rod Adams’ book, originally his thesis of 1983, explores the sweep of the history of recursive function theory and computability from earliest times to the work of Gödel, Church, Kleene, and Turing. Dr. Adams provides an excellent and readily understandable view of the history for those interested in mathematical logic and its history during a particularly important time of its overall development.

...

Dale M. Johnson
Department Head, The MITRE Corporation

Recursion theory started with a burst of activity in the 1930s when Gödel introduced the general recursive functions and within a few years, Church, Turing and Kleene showed that they were the appropriate mathematical definition of the intuitive notion of computable function. The development of recursion theory since then is very well documented, and well known to most people working in the field. But it is not easy to sort out the detailed chronology of this initial burst. Adams gives a very thorough treatment of it. He has written several letters to Church and Kleene and includes copies of their replies. These give a fascinating record of how they came to their results and were influenced by the work of each other and of Gödel. Adams also traces the origins of recursion theory back to the early nineteenth century use of recursion to define simple arithmetic functions. Anyone who is interested in the early development of recursion theory will find this book indispensable.

...

John Shepherdson
Emeritus Professor of Mathematics, University of Bristol

Related Categories:

Publication Date: May 28, 2011

ISBN/EAN13: 0983700400 / 9780983700401

Page Count: 310

Binding Type: US Trade Paper

Trim Size: 6" x 9"

Language: English

Color: Black & White

Table of Contents

Chapter 1 Early Recursive Definitions
Introduction
The First Recursive Definitions
Mathematical Thought at the Turn of the Nineteenth Century
Mathematical Truth and Consistency
The Paradoxes of the Infinite
Concluding Remarks
Chapter 2 Skolem’s Contribution
Introduction
The 1923 Paper
Comments and Conclusion
Chapter 3 Hilbert’s Program and Gödel’s Incompleteness Theorems
Introduction
Hilbert’s Approach
Hilbert’s Foundational Papers
Results on Recursive Function Theory
Scope of the Functions
Transfinite Recursion
General Schema for Ordinary Recursion
Extension of Ordinary Recursion
The Fate of Hilbert’s Plan
Gödel’s 1931 Paper
Comments and Conclusion
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
The Equivalence Theorem
Some Extended Equivalence Results
Church’s Thesis
The Heuristic Evidence
The Equivalence of Various Diverse Formulations
Turing’s Computable Functions
Church’s Formulations
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
Bibliography