What Can Be Computed?: A Practical Guide to the Theory of Computation by John MacCormick is for both undergraduate students venturing into the heart of computer science for the first time and veterans of the subject looking to review the theory of computation.
The book, which is included in the spring 2018 catalogue of the Princeton University Press, is a rewarding read. The beginner will undoubtedly glean a wealth of knowledge embedded within the pages and find MacCormick’s coverage of the topics helpfully succinct, while the expert will find it to be a deserving opportunity for further study or reference.
What Can Be Computed? is a one-term undergraduate course fitted into a textbook. It has been carefully designed to encompass a great number of traditional theory topics appropriate for all interested students, provided they possess some programming experience for the Python examples that come later in the book. It largely covers computability theory, which concerns with whether the answer to a problem can be computed in the first place, and computational complexity theory, which asks whether solutions to problems can be computed efficiently.
It opens by delving into three categories of computation problems and goes on to explore them in great depth. Focusing on computability theory, “Part I” investigates whether computational programs can be solved by writing computer programs. Beginning with some Python basics intended to help readers acquainted with Python programs, the book rigorously explores the concept of a computational problem as well as its expression and categorization.
The book then investigates topics such as the simplest computer — the concept of computer programs executing other programs — and the multitasking ability of computers.
“Part II” continues on to cover computational complexity theory in an extensive and elaborate manner. The book finishes off with the origins and applications of the theory of computation in “Part III.”
What Can Be Computed? goes into great depth on a wide number of topics in regard to the computability and complexity of computer programs, and it makes things very easy to understand with its concise language and often sequential progression of ideas.
Aiming to provide readers with a firm grasp on the fundamentals, the book also offers plenty of supplementary content to further enrich the reader’s understanding. They range from a fascinating historical perspective of computer science to example problems manipulating mainly Python-language programs in order to actively establish a connection between the theory and application of computation.
The book includes clear figures pertaining directly to the material and does not include any explicit citations, instead opting for a bibliography with full descriptions of relevant sources for each author or source mentioned. At the end of each chapter, there is also a section of exercises relevant to the new material to help the reader review the important concepts. Each concept introduced is explored rigorously, and the book does an excellent job of encouraging further interest in the theory of computation as well as computational models.
There is also an online component, with Python and alternative Java computer programs to guide readers through the material as well as lecture slides.
In taking inspiration from Gödel, Escher, Bach: An Eternal Golden Braid — Douglas Hofstadter’s 1979 book — MacCormick has written the book with a great appreciation for the beautiful and profound ideas he believes collectively encompass the field of computer science.