Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1 (Studies in Logic and the Foundations of Mathematics, Vol. 125) (Volume 125)

I agree with much of what another reviewer has said (July 11, 2005 ). But I don't think that Odifreddi has exaggerated when he claims that the prerequisites of reading his book will be roughly freshman math. Having said that, I admit that since many students in their sophomore year still don't possess a working knowledge of, say proof by mathematical induction, the book is certainly too heavy for those readers. Further aggravating the difficulty for beginners is the book's admittedly less-than-ideal organization and presentation of some portion of the enormously many topics it treats. This will be frustrating for readers who are not enthusiasts of the book's multifarious viewpoints and prefer a quick introduction to the subject instead. I recommend N.Cutland's "Computability" to newcomers. Nevertheless, for those who plan a future career in mathematical logic, especially recursion theory, Odifreddi's book will prove to be a treasure trove of unusual and stimulating insights not easily encountered elsewhere - even though one might not always agree with his ideas. For the future logicians I also recommend R.Soare's "Recursively enumerable sets and degrees" for a deeper treatment of r.e. sets. 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 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 Godel's theorems) and to computer science, for which Recursion Theory provides the theoretical foundation. 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 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. 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 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 Gdel's theorems) and to computer science, for which Recursion Theory provides the theoretical foundation. As a first approximation, we introduce static complexity measures in an abstract way as follows: given an acceptable system of indices {e}e for the partial recursive functions (see II.5.2), we call a static complexity measure any total recursive function m, and call complexity or size of e the number m(e).