Computability theory is a scholarly field of fine vintage, preceding the rest of what subsequently came to be known as theoretical computer science, and anticipating the advent of electronic computers by decades. The theory allows us to pose (and in some cases answer) questions about the foundations of mathematics, the capabilities of computing devices (in the absolute sense, independent of their underlying technologies), and the limits of reasoning and derivation using deductive formal systems. Computability theory attracted some of the best mathematical minds of the 20th century, and perhaps had its greatest peak during the period between the two World Wars, with the development of now-familiar concepts and results such as the Turing Machine, lambda-calculus, and Gödel’s incompleteness theorems. It has since matured into a solid body of work that is well connected with diverse theoretical subjects and application domains.

This book gives a primarily historical perspective, focusing largely on the works of Turing, Gödel, and Church, but also considers more contemporary topics such as computation over the real numbers and quantum computation. The editors are well-known scholars in the field, and the various chapter authors are likewise familiar names held in high regard. Though readers will get the most out of this anthology if they have already acquired some knowledge of computability theory, including its mathematical underpinnings, there is very little mathematics per se to be found in it, and the style has more in common with philosophical treatises than with math or computer science monographs. This of course is not a criticism, given that this is, after all, one of the few areas of computer science old enough for such a perspective to arise at all. To provide a historical perspective of computability theory and a frank treatment of the controversies and disagreements among its stalwarts (for example, the philosophical differences between Gödel and Turing concerning the nature of the human mind), one needs a discursive exposition more frequently found in the humanities than in the rigorous mathematical style favored in computer science.

The one consequence of this is that the book is more likely to be warmly received by the philosophically minded who are interested in parsing details of some philosophical claims of Turing or Gödel than by computer scientists wishing to delve rigorously into the mathematics of computability.