Understanding Computation (From Simple Machines to Impossible Programs), by Tom Stuart, is an absolute gem of a book. It's described as:
"Finally, you can learn computation theory and programming language design in an engaging, practical way. Understanding Computation explains theoretical computer science in a context you’ll recognize, helping you appreciate why these ideas matter and how they can inform your day-to-day programming."
And it does exactly that. If you're a self-taught programmer, or a hobbyist who wants to learn more about the theoretical side of computer science, without drowning in research papers, I cannot recommend a better book. Using the ruby language as the starting point, the author moves concisely and clearly through parsers, DFA and NFA, regular expressions, and alone for these components would be worth recommending. Readers will get a solid understanding of how these common and critical components of most programming languages work, without actually getting lost in the complex source code of a full real-world implementation in a modern day language.
I don't recall another book that manages to treat Turing Machines in such a practical way, and expands into the lambda calculus, and the final section of the book covers core computer science concepts such as non-computability (the halting problem) in a way that will bring relief to many future computer science students.
With its absolute clarity, practical and engaging style, this book will be a classic for years to come.
I bought this book after the rave reviews it received from the Ruby Rogues Podcast (Amazon does not allow links, so you have to search for it) - and so far, I haven't been disappointed! I'm about halfway through and many of the concepts I had previously learned the mathematical way became much, much clearer still. I'm just not sure exactly if this book is really aimed at readers with "no formal background in mathematics or computer science" as the author suggests. Knowing about Turing machines, semantics, grammars and such certainly helped me through some of the denser parts.
I have to confess that my Ruby isn't all that great though and I have to read and re-read the code blocks a lot. My verdict would be that you should speak Ruby quite well _or_ have some basic understanding of computation before you pick this one up. If you lack both, this book might be a little too hard for an enjoyable read.