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: 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. |
You are subscribed to email updates from Shield To stop receiving these emails, you may unsubscribe now. | Email delivery powered by Google |
Google Inc., 20 West Kinzie, Chicago IL USA 60610 |
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment