NB. I was sent this book as a review copy.

From Princeton University Press.

It’s not often that a textbook comes along that is compelling enough that you want to read it from cover to cover. It’s also not often that the seed of inspiration of a textbook is quoted as being Douglas Hofstadter’s Pulitzer prize-winning book Godel, Escher Bach. However, in the case of “What can be computed”, both of these things are true.

I am not a computer scientist, but I have spent some time thinking about computability, Turing machines, automata, regular expressions and the like, but to read this book you don’t even need to have dipped your toes into such waters. This is a textbook of truly outstanding clarity, which feels much more like a popular science book in terms of the journey that it takes you on. If it weren’t for the fact that it is a rigorous guide to the theory of computability and computational complexity, complete with a lot of well thought through exercises, formal definitions and huge numbers of examples, you might be fooled by the easy-reading nature of it into thinking that this book couldn’t take you that far. However, building up from the basics of Python programming, and Turing Machines, it takes you through a very thorough (to my somewhat untrained eye) exploration of many of the most important topics in the field, at a level where you can truly go out and explore these ideas yourself.

One thing that I really liked about this book is the way it is able to motivate an idea, and give simple, concrete examples, which you can write yourself in a few lines of code, or which you can follow in a graphical realisation of a Turing machine. Such realisations take very theoretical ideas and make them wonderfully tangible and easy to grasp.

The topics of the book are:

1. What can and cannot be computed
2. What is a computer program
3. Some impossible Python programs
4. What is a computational problem
5. Turing machines: The simplest computers
6. Universal computer programs: Programs that can do anything
7. Reductions: How to prove a problem is hard
8. Nondeterminism: Magic or reality
9. Finite automata: Computing with finite resources
10. Complexity theory: When efficiency does matter
11. Poly and Exp: The two most powerful complexity classes
12. Polycheck and NPoly: Hard problems that are easy to verify
13. Polynomial-time mapping reductions: Proving X is as easy as Y
14. NP-completeness: Most hard problems are equally hard
15. The original Turing machine (This chapter is particularly beautiful, as it goes through in detail, parts of Turing’s 1936 paper “On Computable Numbers”, where the foundations for much of what is in the rest of the book were laid).
16. You can’t prove everything that’s true
17. Karp’s 21 problems
18. Conclusion: What will be computed

I write this exhaustive list to show the trajectory that the book takes you on from humble beginnings to fundamental and cutting-edge questions.

Essentially, I sat down and read this book in three long and very enjoyable sessions. This is indeed one way to work through the book, and I do believe that you will get a lot out of it, at least in guiding you to the landscape of problems out there and the methods used to answer them. However, to really get everything that this book has to offer, one would work through all of the incredibly well-designed exercises. Doing so would be equivalent, I think, to a serious university course in the area of computability and complexity, which would probably be around a year’s worth of material. If time allowed, I would happily work through these exercises in detail (both pen and paper exercises as well as programming exercises), and anyone who has any interest in working in this area of theoretical computer science (or its implied, applied tangents), would do very well to spend a few months doing so.

I have to admit to being really blown away by the thought that has gone into the flow of ideas and the design of the exercises. I try, in my teaching, to spend as much of my time in the head of a theoretical student who I am trying to bring to a specific place of understanding. Without knowing where my students might be in their own path means that they will likely get lost with my explanations, and so to me, a deep understanding of where the student is, is vital. I think that unlike almost any other textbook I’ve read, John MacCormick does this to near perfection.

I will definitely be recommending this book to students who have interests in these directions and I would certainly say that anyone who may be teaching a course in these topics would do well to give this book a thorough investigation.