Computability Theory

Rating:
Summary: A Unique Introduction to Computability
Review: 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.