An Early History of Recursive Functions and Computability: From Gödel to TuringDocent Press, 2011 - 297 páginas An Early History of Recursive Functions and Computability traces the development of recursive functions from their origins in the late nineteenth century, when recursion was first used as a method of defining simple arithmetic functions, up to the mid-1930's, when the class of general recursive functions was introduced by Godel, formalized by Kleene and used by Church in his thesis. The book explains how the proposal given in Church's 1936 paper, now known as Church's thesis, first arose and concludes with the consideration of another class of functions, the Turing computable functions, that were specially created to be equivalent to the class of effectively calculable functions. The book includes previously unpublished letters between the author and many of the key historical figures. |
Índice
| 1 | |
| 19 | |
Hilberts Program and Gödels Incompleteness Theorems | 33 |
Early Work Leading to λDefinable Functions | 73 |
General Recursive Functions | 105 |
Churchs Thesis | 147 |
Turings Computable Functions | 189 |
Términos y frases comunes
Ackermann's function Alonzo Church argument arithmetic axiomatic axioms Bernays bounded quantifiers chapter Church's system Church's thesis class of effectively class of functions computable functions concept considered consistency proof constructive contained contradiction conv course-of-values recursion decision problem Dedekind definable functions definition of recursive effectively calculable functions Entscheidungsproblem equivalent existence finitary finite footnote Formal Logic formal system formally definable foundations free symbols functional calculus functions defined given Gödel number Hence Herbrand identity functions incompleteness theorem inconsistency induction initial functions introduced Kleene lectures letter machine Math mathematicians metamathematical method natural numbers notion ordinary recursive functions Peano Péter positive integers possible primitive recursive functions Princeton procedure produced proposition provable real numbers recursive definitions recursive function theory recursively enumerable represent Richard Paradox Rosser Rózsa Péter schema sequence set theory Skolem successor function system of equations system of logic theory of positive tions Turing Turing's undecidable unsolvable variables w-consistency well-formed formula X-definable