Customer Reviews

Computability: An Introduction to Recursive Function Theory

5 star:		(3)
4 star:		(3)
3 star:		(1)
2 star:		(0)
1 star:		(0)

 

 

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.

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.

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.

Cutland's book "Computability: An Introduction to Recursive Function Theory" is without doubt the best introduction to recursion theory available on the market. Elementary Recursion Theory is a logician's expression for theoretical computer science, with an emphasis on negative results, i.e. what computers cannot do. Cutland could have exploited Church's Thesis in the manner of H. Rogers, and this could have perhaps make the book readable for a larger public from the human science. Instead Cutland defines the computable functions in a rather standard way through the use of the Register Machine. Then all the basic chapters of recursion theory are introduced, including a gentle explanation of Kleene second recursion theorem, on recursive operators, on formal arithmetic and Godel's incompleteness theorem, Post creative and productive sets. It contains a chapter on Blum complexity theory, with the gap theorem and Blum's speed-up theorem. The book is a must for those who want to penetrate this fundamental subject.

GENERAL POINTS/AUTHOR PRACTICES
This book is a mathematical, but not at all fully rigorous textbook on computability and recursive functions in 12 chapters on much of the standard theory. Nigel Cutland is/was a professor of 'pure' mathematics, hence the strongly mathematical flavor. One thing I really appreciate about this textbook thru Chapter 7 is that as one progresses thru the the book, it mostly stays at a steady level of abstraction, not becoming much more difficult. Therefore, if a reader can understand the first two chapters, they can probably understand Chapters 3-7 pretty well.

In a number of places, Professor Cutland cranks out definitions / theorems / proofs in clusters, which is student-unfriendly, but he also does write helpful descriptive prose, especially in the latest chapters. Cutland, in another disrespect for students uses the word 'clearly' to excess (41 usages in Chap 1-10 / 7 usages of 'easily seen'). Many of those uses are in proofs of theorems, the worst place for them. Clear to whom?

THE URM VS. OTHER MODELS OF COMPUTATION
It is interesting that Cutland's standard model of computation is the unlimited register machine (URM), not the sequence of finite automaton, pushdown automaton and Turing machine that is FAR more common in textbooks. This uniqueness of the URM model also means it is independent of the Chomsky hierarchy of language classes that run on those automata just mentioned. All this makes the URM a very clean single model of computation, which has some strong advantages. The URM programs have only four simple operations, Zero/Successor/Transfer/Jump, which are introduced in Chapter 1 and used mostly thru Chapter 4. In late Chapter 9, URMs return briefly in a completely different URMO form, or 'Oracle' URM.

By Chapter 5, the text mainly deals with general sets of programs, which gets rid of most of the overt URMishness. At that point, this becomes a math text on the theory of computing using no particular model of computation.

SCOTT'S MAIN OPINIONS/THE LATER BOOK
In my opinion, this book is most accessible and interesting thru Chapter 7. Then short Chapter 8 is misplaced in the book and also unfamiliar in subject matter to the author, so he told us the five older textbooks he used to fake that chapter. With long Chapter 9, the book becomes marginally more difficult than previous chapters to its end with Chapter 12. For this reader, Chapter 9 was unremittingly tedious to read, a completely theoretical treatment, with no linkage at all to good examples of more concrete 'reductions' in earlier chapters. Chapter 10 was much more interesting again and somewhat linked back to Chapter 5. Chapter 11, my final one, was quite unusual in 'sort of' getting into anthropology, psychology, and damaging enemy computers in war, inspired by the seemingly quite weak 2nd recursion theorem. For this chapter, a reader could just read the highly clarifying remarks at bottom of p. 209 and call it good. I read this book 12Jun to 30Jul11.

THE CHAPTER TITLES FOR REFERENCE:
Prologue / 1 Computable functions / 2 Generating computable functions / 3 Other approaches to computability: Church's thesis / 4 Numbering computable functions / 5 Universal programs / 6 Decidability, undecidability, and partial decidability / 7 Recursive and recursively enumerable sets / 8 Arithmetic and Godel's incompleteness theorem (very sketchy, can skip) / 9 Reducibility and degrees / 10 Effective operations on partial functions / 11 The second Recursion theorem / 12 Complexity of computation

A MORE DIFFICULT VERSION
It's amazing how many times Nigel Cutland in this 1980 book referred to the 1967 book by Hartley Rogers for more detail. That book is still available from Amazon and appears to be quite difficult, with notably dense page layouts. The present MIT paperback of the Rogers was a 1987 reprinting of the original 1967 book on different publisher. For those interested, here is a link to that book: Theory of Recursive Functions and Effective Computability In Oct11, I finally did buy the inexpensive Hartley Rogers text for reference and for informal comparison with this text by Cutland. The Rogers text is a quite credible 'next level' read for after reading this very good book presently under review.

A BOOK WITH SOME SIMILARITIES TO CUTLAND
In early 2012, I am reading the great 400 page computability text by Barry Cooper, and he covers some of the same rather unique territory as Cutland with even less rigor, but with expanded subject coverage. Notably, Cooper also uses the URM model, but not as completely as Cutland did. Computability Theory (Chapman Hall/CRC Mathematics Series)

For those who are studing the Recursive Function Theory it is an indispensable book. Recommended.

Elements of the Theory of Computation (2nd Edition) I just got through reading other book and I realized the only reason I understood it at all was that I had read this book.When I first read this book I thought some of the parts elementary, but comparing it to the above text I realized it was doing the job of teaching by giving good illustrations of the processes involved.