What can be computed? A practical guide to the theory of computation – by John MacCormick, a review
NB. I was sent this book as a review copy.
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.…