
After my review of the first edition (referred to as 1e going forward) was published [1], the author contacted me by email to request the full list (reduced in the final review) of issues I had compiled for CR. He was already seriously involved in producing this second edition (called 2e here) and poised to correct whatever I had discovered. He offered me draft PDFs of 2e, along with a correction list to help verify the corrections were themselves correct.
Eventually 2e was published. After some time, CR arranged for me to have a publisher copy for review, and this is my review.
I promised in [1] that if I had a chance to review 2e and found the difficulties present in 1e to be overcome, I would heartily endorse it. Indeed, I heartily endorse this book as a great standalone introduction to computability and as a gateway to more serious, more formal books and surveys--I enthusiastically celebrate its entrance and improvements.
The shortcomings observed in 1e were divided into three classes, descriptively noted in [1]. The CR editor and I agreed to report only three in each class. Class 1 was trivial--“typographical errors, bad turns of grammar, or minor math missteps.” I collected ten of these. Class 2 was more serious “and should have been caught by mathematical copy editing.” I found nine of these. The eight Class 3 issues required rewriting the mathematics. In my judgement, 2e fixes my 27 objections.
The author found another eleven errors or aesthetic flow problems (and probably many more) and fixed them as well; the only Class 3 change among these is in Figure 6.21, where NO is twice replaced with YES, NO--this allows generation to continue.
As described in the preface to the second edition, the author made substantial modifications to 1e; I grant them to be improvements. We chase rainbows when we think we can find all mistakes--worse, if we think we have found them.
There are net increases of 93 pages and 91 bibliographic entries. An added 46-page Part 4, “Back to the Roots,” contains the new chapter 16 that revisits the Church-Turing thesis (CTT). Also added are a 19-page glossary and a 5-page discussion of the notion of truth (Section 3.1.2). The latter, combined with more bibliographical notes for chapter 4, addresses my previous objections that Alfred Tarski’s role in logic and computability are thinly covered in 1e. References to works of Tarski and articles about them have increased from one to nine.
Here are some notable strengths from 1e and 2e. The new Post machine material in Section 5.2.3 concisely clarifies a murky picture in 1e. The Post program in the new Figure 5.9 recognizes the language 0k1k (CFL, not regular) leaving Q empty on accepted words (check it out); v10 could be replaced by v2. The beginning of Section 12.1 has been rectified. Major books by Rogers and Odifreddi were added to chapter 17, “Further Reading.” In the footnotes, the birth years of living contributors are now written as “b. year.” Photos of most of the actors make the historical comments more personal. Diagrams, faithful visual representations, sketches, and alternative images energize the mathematical presentation. Cartoon characters Greg and Becky keep things light and lively.
Bibliographic notes and problems in some chapters have been augmented. The book provides definitions of notions required for problems, and comments on these notions have been added.
A few caveats: (1) On page 37, the law of excluded middle guarantees that the only values are true or false. It is the law of noncontradiction that is contradicted. (2) The reader should be ready to supply and apply parentheses correctly in discussions of syntax for P, L, F, A, and ZFC in Boxes 3.2-6 and Appendix A. (3) On page 44, consistency, said to be syntactic in 1e, is now oddly called semantic; ignoring that, the important thing is that consistency is metatheoretic. (4) Some confusion comes from the NB on page 58 applied to one model of F (again on page 63), but using all models of F as shown in Figure 4.4.
The new chapter 16 deserves careful reading. It is a monumental summary of multiple and sometimes conflicting roots and successive castings of the computability (Church-Turing) thesis. It glosses original-source quotes and links the diverse language in a coherent, cohesive, and comprehensive account. Beyond the history lesson, it reforms CTT for quantum, relativistic, hypercomputational models, and more. This chapter is a crowning finale to a wonderful book.
Disclosures: (1) The author credits my help with corrections for 2e. (2) Alfred Tarski was my thesis committee chair, and my dissertation was the last one he signed. He told me he invented decidable theories.