Friday, July 26, 2013

Review: Computability: An Introduction to Recursive Function Theory

Review: Computability: An Introduction to Recursive Function Theory


Computability: An Introduction to Recursive Function Theory

Posted:

Computability: An Introduction to Recursive Function Theory (Paperback)
By Nigel Cutland

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.


Pin It Now!

0 comments:

Post a Comment

 
//PART 2