[Jodavaho.io] — Josh Vander Hook

John MacCormick, What Can Be Computed? A Practical Guide to the Theory of Computation (Princeton University Press, 2018).

Quick review:

It does a good job of introducing complexity theory, and is accessible for undergrads, practitioners, experienced folks, or maybe even hobby programmers with no serious background in theory (it’s hard to say how much load bearing my background was doing when I found it “accessible”).

But calling this a “practical” guide is a bit of a stretch. It will claim to use python to introduce you to theoretical CS, and so I figured surely they must have SAT solvers, teach you reductions, and discuss the practical limitations of using them. For a practitioner, the ideal skill is to recognize a “hard” problem, know when to map it to something a library can solve, and understand the limitations of that mapping. This book does none of that, not really.

What I expected, and did not get:

• How to go about proving a problem is hard
• What to do if it is - approximations and software solvers
• What can be done about it

What it does, is use python as a kind of “notation”, simply showing how programs can operate on themselves and introducing decidable and undecidable problems in that context. It then proceeds with an abbreviated skip through some harder classes of problems. This makes it accessible, but not practical.

The steps were more explicit, but not clearer, not really. God help you if you were coming in without python knowledge, then you’d be learning notation and concepts at the same time. Horrific!

What I did appreciate, a lot, was the historical context and asides, and the careful attention to mapping this book to other books. And the review/presentation of Turing original landmark papers was also much appreciated.

In all it’s well written, easy to read, quick to follow, full of good exercises, and yes, uses python. Read it if you want a decent intro and references to deeper book.

Back to Aerospace and Quantum Computing for me!