I’ve been refreshing my knowledge of algorithms and computation when I can find a little free time, so I decided to take a look at Tom Stuart’s Understanding Computation: From Simple Machines to Impossible Programs since O’Reilly Media published it a few months back and they were willing to let me have a copy of the ebook in return for an honest review.
I expect that this book will mainly appeal to students of Computer Science, particularly anyone who’s struggling with a standard textbook approach to the theory of computation. The tone of the writing is much more accessible and easy to follow than the textbooks I’ve seen, so this is a worthwhile investment for students and/or programmers who want to fill in their knowledge of theory.
The book opens with a quick introduction to the Ruby programming language. It’s intended to be just enough that you can manage to understand the examples further along in the book, so if you already have a fair knowledge of Ruby that entire section is probably just going to be something you skim. In fact, if you have a pretty solid grasp on procedural programming in general, you’ll probably be able to mostly skim that area and then come back to the chapter later if you come across something in an example that seems puzzling.
From there on, the book builds from talking about extremely simple programs that can be easily represented by finite automata, and moves its way up to showing how some things can be (so far as we know) either impossible to compute in any reasonable amount of time or impossible to compute at all (e.g. the halting problem).
The text as a whole is more at the end of the theoretical computer science spectrum than focused on the practical details of programming. It makes good use of endnotes to offer additional details that aren’t necessarily absolutely crucial to what the text is saying, but still might be of some interest.