Customer Reviews

Computability Theory (Chapman Hall/CRC Mathematics Series)

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

 

 

This book is an introduction to computability theory. It is organized in three parts, starting with basic computability theory and moving up to advanced topics, some of which cannot be found in textbooks today.

In the first part the reader is introduced to basic concepts and results of computability like models of computation, coding, universal machines, enumerability, fixed point theorem. The author also discusses the historical context in which various notions appeared (not only in this part but throughout the book) like Hilbert's programme and makes connections with logic (language, theories, Peano Arithmetic, Godel incompleteness theorem). Computability and Unsolvability in the real world is also discussed, along with the search for natural examples of incomputable sets, a topic which is currently more interesting than ever. Most of the content of Part I can be found in other good text books (like Odiffreddi's or Roger's) but the way it is presented is unique: the arguments and proofs are given in an informal yet accurate way (according to the modern mode for doing computability) and the whole arrangement is very schematic, often assisted by diagrams, figures, tables and boxes. This is especially helpful in a text book in computability theory, a subject that makes understanding rely so much on intuition and visual images.

The second part is concerned with oracle computation (a core part of computability), Turing degrees, Enumeration degrees, and many other related and complementary topics like polynomial bounds, P=?NP, the Scott model for Lamda calculus and others. The author here tries to give a general idea of the subject by discussing interesting topics (like the ones mentioned above) which don¡¯t necessarily lie on the core of computability theory. This is pretty much the spirit of the whole book: to give the non-expert reader access to the most exciting (and sometimes apparently inaccessible at this level) topics in the subject and motivate him/her to further study towards the direction that looks and feels more appealing.

The third and last part discusses advanced topics like approximation constructions, priority injury, Sack¡¯s theorems, maximal sets, even the 0¡¯¡¯¡¯-priority method. This is the longest part of the book and the choice its contents (along with the approachable and attractive way they are presented despite their advanced nature) is just another feature which makes this book unique. The construction of maximal sets is remarkable since it uses a tree argument (with infinitary activity of the nodes but without injury) thus making it more intuitive and understandable, in contrast to the usual e-maximal state method which was introduced by the original paper (with the first proof that maximal sets exist) and followed by most text books I am aware of, without many changes. The proof of the existence of a noncuppable c.e. noncomputable degree also deserves to be mentioned as it is not something that one finds in text books. Also, it is different than the original pinball argument one finds in papers (with the restraints tending to infinity, often mentioned as an example of this bizarre feature) as it is done on a tree. Finally, computability in mathematics (structures, combinatorics, Analysis) and science is discussed along with randomness and computable models.

In the end of the book there is a bibliography for further reading. This is very personal (and, of course, by no means complete) but very helpful as it ranges over a wide range of computability related topics and it matches the spirit of the book very well.

To sum up, this introduction achieves the aims set by the author (a leading specialist in computability) in the preface and the epilogue: it deals with the subject in a very wide context, discusses it from its most hardcore features (priority, forcing) to its most distant echoes (incomputability in science) and most importantly it relates these two, showing how technical work is motivated and inspired by more general concerns. It is intended as a text book for undergraduate and early postgraduate students but is also suitable for any non-specialist. The features discussed above along with the modern style of presentation make the subject look as attractive as it really is and the book unique over the other computability text books available today. I wish this book had been in my library when I first started reading computability.

This is a lovely book, which gives a fresh and invigorating account of current developments in computability theory. Personally, I don't feel it can helpfully be compared to Cutland's computability text, as though that book supplies enough background for some undergraduate introductory courses in computability theory, it doesn't reach beyond that level. Cooper sensibly avoids using the same approach as Cutland for the area of over-lap -there would be little point duplicating an existing, in-print work- instead, he has in the early chapters given an intuitive approach to those topics which helps the reader understand what is going on under the morass of symbols which so often obscure rather than promote comprehension. Nor can much useful comparison be drawn with Hartley Roger's classic text, as the main bulk of Cooper's book is concerned with material which post-dates Hartley Rogers.

Computability theory has a fearsome reputation for incomprehensibility and difficulty, even amongst logicians. When, many years ago, I attended my first logic conference and was asked my area of study by a senior logician, I was a little disconcerted by his response of, `Good luck - you'll need it,' to my reply of `computability theory'. Conversations with Cooper proved invaluable, in that his understanding is holistic: he understands what is going on, he understands the big picture. Better, he can draw pictures, both literal and figurative, to explain to others how particular proofs work.

That is what you get with this book: a minimum of technical jargon and deceptively clear explanations of many modern developments in computability theory. It's a great book for anyone beginning research in the area, or for an undergraduate who wants a deeper understanding to underpin their coursework, or, indeed, for researchers in other areas wanting to find out more about modern computability theory and its relevance to their work.

The book is divided into roughly three parts: an introduction to computability theory, followed by a more advanced introduction to the theory of degrees of unsolvability and decidable theories, and finally some newer material on computation and structure.

As for the introduction to computability, let me just say that I'm thankful to have already been introduced to computability via Nigel Cutland's excellent and concise text "Computability : An Introduction to Recursive Function Theory". Unlike this book, Cutland does not skip any of the important details (or have the reader fill them in with exercises). For example, Cutland acutally provides rigorous but intuitive proofs of the s-m-n Theorem and the existence of universal computers. Contrast this with how this book leaves the general theorem as an exercise, follwed by the sentence "But let us get back to more important matters". What I found remarkable when reading Cutland is that because of the s-m-n (which is trivialized in this book), Cutland rarely invoked "Church's Thesis" when proving the computability of a function or relation, where as Church's Thesis gets invoked in this book for matters as trivial as showing that computable relations are closed under the various logical operations. In short, by reading Chapters 1-11 of Cutland, the reader can easily (and thankfully) skip the first 8 or 9 Chapters of this book, while receiving a more complete thoughtful treatment. Yet another reason to read Cutland is his excellent introductions to both recursion theorems, where as in this book the fixed-point theorem receives one page in an awkward location in the book.

As for the remaining parts, I made an honest attempt to read them in hope that the author's informal style of writing might shed light on some of the more complex results about degrees of unsolvability. And to his credit, I found the Chapter on priority and immunity more understandable than say what is presented in Hartley Rogers's classic "Theory of Recursive Functions and Effective Computability".

The following editorial note originally enticed me to buy the book: "The final chapter explores a variety of computability applications to mathematics and science". Unfortunately this chapter seemed overly brief, and left me looking for better references. In short, reading this book did little to enhance my viewpoint towards computability theory. I'm glad the author is excited about the subject and wants to make the material seem more appealing by trying to provide more intuition about the subject matter, but the way that it was carried out simply did not work for me. For the casual reader I recommend Dewdney's "Turing Omnibus", and for the serious reader, the books by Cutland, Oddifredi, and Rogers in that order. I often hear or read the claim that Rogers's book is "outdated", but it still makes for an amazing read, and is in my opinion still the best graduate text on the subject. Note that most of the results in this book can be found in Rogers. And for the programming oriented reader, the book by Neil Jones "Computability and Complexity" ought not to be missed.

The first part (about 100 pages) introduces the basics of computability theory including some logic (Gödel's theorem + computability of theories). For me the presentation was a bit too informal (often invoking Church's thesis, only a few very simple problems are actually encoded in Turing machines/µ-recursion, proofs of basic theorems such as the equivalence of the two models or the non-primitive-recursiveness of the Ackermann function are not even sketched).

The second part and the first chapter of the third part deal with reducibilities and corresponding hierarchies and degree structures. The treatment is both intuitively accessible and rather thorough. Besides the standard Turing degrees/arithmetical hierarchy, it includes topics such as enumeration reducibility, the Medvedev lattice and finally an introduction to immunity and the priority method, which I found very accessible. Much more material on these topics can be found in classics like Rogers, but Cooper book provides a very good introduction even to quite complicated technical areas.

The third part first gives an overview of applications of forcing, topology and determinacy to computability theory. The treatment is not very deep (many results are left unproven and only simple problems are given as exercises), but there seems to be no comparable textbook treatment of these topics (which partly post-date Rogers), in particular not in textbooks at this level. Thus, I found it a very useful starting point. The last two chapters deal with the computability of theories and with the relation between computability and other mathematical structures. The last chapter was again somewhat shallow, but very interesting from a broader mathematical perspective, which Cooper also emphasizes in other parts.

In general, the book is maybe not the ideal first introduction, but a very accessible intermediate texbook which guides the reader to more advanced topics which are of interest to current research in the field.