Computability theory is often included in studies of automata and formal languages, or of recursion theory. These topics, which originated with the work of some remarkable mathematicians (Gödel, Church, Turing, and Post) were the basis of the creation of modern computers (including the one you have in front of you).

The book is a highly readable and a comprehensive introduction to contemporary computability theory. It covers some recent topics just published in contemporary research papers, providing a guide to the direction of current research. These topics are presented in their appropriate philosophical and historical contexts. The book will be accessible for undergraduate and graduate students in computer science, mathematics, physics, or applied mathematics, and for the beginner or the expert.

I agree with the author’s two-part approach to covering the topic: he perfectly combines a presentation of the necessary formalism with a discussion of the historic background of the topic, and a development of the theory, a topic itself often studied in philosophy of science books. This is the first book of more than ten I have read that does this combination of topics well, associating the history with the formal theory without losing the power of its presentation. This book can be used to teach formal computability theory, while taking advantage of the power of its pedagogical resources to explain the story behind each formal fact.

The author makes it abundantly clear that he is a mathematician, not hesitating to include formal expositions throughout the book. However, Cooper is also concerned about context for its own sake, or as a pedagogical resource. Here, he has succeeded in his attempt to present a different approach to this not always intuitive theory. From the Hilbert tenth problem to the self-reference paradoxes, Church-Turing thesis, Gödel theorems, and universal Turing machines, Cooper leads us through computablity theory’s most important topics and problems, including more wide-ranging topics like the theory of reducibilities and their degree structures; computably enumerable sets and their automorphisms; and subrecursive hierarchy classifications. He also includes coverage of more advanced issues, like Post’s problem, forcing, and category or effective Ramsey theory.

Some topics covered in this book that I have never seen explained well in other textbooks include computing with oracles, forcing and category, the computability of theories, and computability and structure. Some of the other topics in this book have been explained well in other textbooks, but with a different orientation. For example, there is a very good explanation of natural examples of computable and noncomputable phenomena in The computational beauty of nature [1], and some great explanations in the textbook Cellular automata: a discrete universe [2].

Before reading this book, I recommended some other titles as textbooks: Automata and computability, by Kozen [3]; Computability and complexity theory, by Homer and Selman [4]; An introduction to formal languages and automata, by Linz [5]; Computability and logic, by Boolos, Burgess, and Jeffrey [6]; and Computability and unsolvability, by Davis [7]. Now, without hesitation, I can add this book to my list.