Origins of Recursive Function Theory
- 1 January 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Annals of the History of Computing
- Vol. 3 (1) , 52-67
- https://doi.org/10.1109/mahc.1981.10004
Abstract
For over two millenia mathematicians have used particular examples of algorithms for determining the values of functions. The notion of "?-definability" was the first of what are now accepted as equivalent exact mathematical descriptions of the class of the functions for which algorithms exist. This article explains the notion and traces the investigation in 1931-1933 by which the notion was quite unexpectedly so accepted. The Herbrand-Gödel notion of "general recursiveness" in 1934 and the Turing notion of "computability" in 1936 were the second and third equivalent notions. Techniques developed in the study of ?-definability were applied in the analysis of general recursiveness and Turing compatibility.Keywords
This publication has 47 references indexed in Scilit:
- R. M. Friedberg. The fine structure of degrees of unsolvability of recursively enumerable sets. Summaries of talks presented at the Summer Institute for Symbolic Logic, Cornell University, 1957, 2nd edn., Communications Research Division, Institute for Defense Analyses, Princeton, N.J., 1960, pp. 404–406.The Journal of Symbolic Logic, 1963
- Recursive Unsolvability of a problem of ThueThe Journal of Symbolic Logic, 1947
- Recursive functions and intuitionistic number theoryTransactions of the American Mathematical Society, 1947
- Computability and λ-definabilityThe Journal of Symbolic Logic, 1937
- Finite combinatory processes—formulationThe Journal of Symbolic Logic, 1936
- Some Properties of ConversionTransactions of the American Mathematical Society, 1936
- The Inconsistency of Certain Formal LogicsAnnals of Mathematics, 1935
- A Set of Postulates For the Foundation of LogicAnnals of Mathematics, 1933
- Some Additions to the Theory of CombinatorsAmerican Journal of Mathematics, 1932
- An Analysis of Logical SubstitutionAmerican Journal of Mathematics, 1929