Computability: An Introduction to Recursive Function Theory [Paperback]

Nigel Cutland (Author)

Book Description

ISBN-10: 0521294657 | ISBN-13: 978-0521294652 | Publication Date: June 30, 1980

What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest.

Editorial Reviews

Review

"Dr. Cutland has produced here an excellent and much needed textbook which will undoubtedly help to establish recursion theory as a more widely taught branch of mainstream mathematics." Mathematics & Physics

Book Description

This introduction to recursive theory computability begins with a mathematical characterization of computable functions, develops the mathematical theory and includes a full discussion of noncomputability and undecidability. Later chapters move on to more advanced topics such as degrees of unsolvability and Gödel's Incompleteness Theorem.

Product Details

• Paperback: 264 pages
• Publisher: Cambridge University Press (June 30, 1980)
• Language: English
• ISBN-10: 0521294657
• ISBN-13: 978-0521294652
• Product Dimensions: 8.8 x 5.8 x 0.6 inches
• Shipping Weight: 12.8 ounces (View shipping rates and policies)
• Average Customer Review: 4.3 out of 5 stars  See all reviews (7 customer reviews)
• Amazon Best Sellers Rank: #397,668 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

16 of 17 people found the following review helpful:

5.0 out of 5 stars An excellent book for beginners in computability theory, September 14, 2000

By 

Todd Ebert (Long Beach California) - See all my reviews

This review is from: Computability: An Introduction to Recursive Function Theory (Paperback)

If you are a computer scientist who would like to delve into the foundations of computing for the first time, this is the perfect book for you. The author uses unlimited register machines as his computing model, then shows equivalence with this model and other models , such as the Turing machine. The reader should find more advanced topics, such Godel's Incompleteness Theorem, the Recursion Theorem's, and Reducibility to be quite accessible.

15 of 16 people found the following review helpful:

4.0 out of 5 stars Excellent book for the right audience; often incomplete or informal, January 1, 2007

By 

Christopher D. Smith (Colorado Springs, CO) - See all my reviews
(REAL NAME)   

This review is from: Computability: An Introduction to Recursive Function Theory (Paperback)

This is a well-written book, and gives a satisfying account of the field of recursion theory. It covers basic aspects of recursion theory, Godel numbering, the structure of recursive and recursively enumerable sets, and even a brief (and quite sketchy) foray into complexity results at the end. It is, however, worth deciding whether you are in the target audience before making a purchase.

If you are trying to make a first transition over into theory topics from, say, a career of practical software development tasks, then this is the wrong book. Try Sipser's Introduction to the Theory of Computation instead. Sipser is more willing to spend time on demonstrating the intuitive picture, and relies less on formal mathematical arguments. This book can come later to fill in some of the mathematical properties.

On the opposite end of the spectrum, this is a passable but mediocre reference book for recursion theory. It omits major topics, such as the arithmetic hierarchy. It deviates considerably from other traditional treatments. These decisions will get annoying if you plan to read bits and pieces rather than learn in sequence according to the author's presentation. A better reference is Hartley Rogers' Theory of Recursive Functions and Effective Computability.

Buy this book if you are in the middle. It's a great book if you've seen some decidability results, but not a formal mathematical treatment; and if you intend to follow the book and learn what it decides rather than look up specific topics. In that situation, it's hard to see how you could do better.

9 of 9 people found the following review helpful:

3.0 out of 5 stars Clearest mathematical introduction, July 11, 2005

By 

Nathan Oakes (Ashland, Oregon) - See all my reviews

This review is from: Computability: An Introduction to Recursive Function Theory (Paperback)

This introduction for undergrads assumes no specifics other than general experience in college math. The writing is clear and exercises are interspersed and follow naturally from the explanations. Proofs are explanatory and easy to follow, though often rather informal.

However, it looses some of its best qualities about halfway through the book. The early chapters give excellent context and motivation, but by chapter 4 that is mostly gone. It seems that the push to cover more topics is what led to making the introduction of new topics more and more brief. The later chapters give little feeling for how it all fits together and why we should care. You can look up the same topics in Rogers or Odifreddi to get an idea of the interesting things that could have been said.