http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
Classic graduate-level introduction to theory of computability, usually referred to as theory of recurrent functions. New preface and appendix.
Introduction -- Heuristic remarks on decision problems -- Suggestions to the reader -- Notational conventions -- Part I. The General Theory of Computability -- Computable functions -- Turing Machines -- Computable functions and partially computable functions -- Some examples -- Relatively computable functions -- Operations on computable functions -- Preliminary lemmas -- Composition and minimalization -- Recursive functions -- Some classes of functions -- Finite sequences of natural numbers -- Primitive recursion -- Primitive recursive functions -- Recursive sets and predicates -- Turing machines self-applied -- Arithmetization of the theory of Turing machines -- Computability and recursiveness -- A universal Turing machine -- Unsolvable decision problems -- Semicomputable predicates -- Decision problems -- Properties of semicomputable predicates -- Recursively enumerable sets -- Two recursively enumerable sets -- A set which is not recursively enumerable -- Part 2. Applications of the General Theory -- Combinatorial problems -- Combinatorial systems -- Turing machines and semi-thue systems -- Thue systems -- The word problem for semigroups -- Normal systems and post systems -- Diophantine equations -- Hilbert's tenth problem -- Arithmetical and diophantine predicates -- Arithmetical representation of semicomputable predicates -- Mathematical logic -- Logics -- Incompleteness and unsolvability theorems for logics -- Arithmetical logics -- First-order logics -- Partial propositional calculi -- Part 3. Further Development of the General Theory -- The Kleene hierarchy -- The iteration theorem -- Some first applications of the iteration theorem -- Predicates, sets, and functions -- Strong reducibility -- Some classes of predicates -- A representation theorem for P subscript 2 superscript A -- Post's representation theorem -- Computable functionals -- Functionals -- Complete computable functionals -- Normal form theorems -- Partially computable and computable functionals -- Functionals and relative recursiveness -- Decision problems -- The recursion theorems -- The classification of unsolvable decision problems -- Reducibility and the Kleene hierarchy -- Incomparability -- Creative sets and simple sets -- Constructive ordinals -- Extensions of the Kleene hierarchy -- Appendix 1. Some results from the elementary theory of numbers -- Appendix 2. Hilbert's tenth problem is unsolvable.
Reprint. Originally published: New York : (McGraw-Hill, 1958. McGraw-Hill series in information processing and computers. With new preface and appendix).
Includes bibliographical references (pages 237-241) and index.
McGraw-Hill series in information processing and computers