1988 marked the first centenary of Recursion Theory, since Dedekind’s 1888 paper on the nature of number. Now available in paperback, this book is both a comprehensive reference for the subject and a textbook starting from first principles.
Among the subjects covered in Volume I of Classical Recursion Theory are: various equivalent approaches to effective computability and their relations with computers and programming languages; a discussion of Church’s thesis; a modern solution to Post’s problem; global properties of Turing degrees; and a complete algebraic characterization of many-one degrees. Included are a number of applications to logic (in particular Gödel’s theorems) and to computer science, for which Recursion Theory provides the theoretical foundation.
Odifreddi has written a delightful yet scholarly treatise...[...]
G.E. Sacks, Harvard University and M.I.T.
An impressive presentation of classical recursion theory... highly recommended to everyone interested in recursion theory.[...]
C. Calude, Zentralblatt für Mathematik
A must as a reference manual for any mathematician, philosopher or theoretical computer scientist who deals with issues of computability.[...]
An incredible wealth of information, including much that occurs for the first time in book form.[...]
Journal of Symbolic Logic