Understanding Computation: Impossible Code and the Meaning of Programs

by Tom Stuart

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.

Rather than use mathematical notation or an unfamiliar academic programming language like Haskell or Lisp, this book uses Ruby in a reductionist manner to present formal semantics, automata theory, and functional programming with the lambda calculus. It's ideal for programmers versed in modern languages, with little or no formal training in computer science. Understand fundamental computing concepts, such as Turing completeness in languages Discover how programs use dynamic semantics to communicate ideas to machines Explore what a computer can do when reduced to its bare essentials Learn how universal Turing machines led to today's general-purpose computers Perform complex calculations, using simple languages and cellular automata Determine which programming language features are essential for computation Examine how halting and self-referencing make some computing problems unsolvable Analyze programs by using abstract interpretation and type systems

Genres: Computer Science, Programming, Technology, Nonfiction, Computers, Software, Algorithms

332 pages, ebook

First published January 1, 2013

Reviews

[Rob · Rating 4 out of 5]

Despite the fact that there's no real reason to be apologetic, I also haven't yet reached the point in my career as a software developer where I've stopped apologizing for the fact that I have no "real" Computer Science Background.[^1] And/but that's exactly what draws me to books like Understanding Computation by Tom Stuart (O'Reilly, 2013). Stuart describes the books as for:

...programmers who are curious about programming languages and the theory of computation, especially those who don’t have a formal background in mathematics or computer science.

In other words, people like me. The people that Eric Miraglia described as the "liberal arts majors drafted into web-developer service during the dotcom boom".[^2] Yes: the liberal artsy non-computer science degree holders that wound up doing computer sciencey type software work just the same. Smart people that nevertheless are exploring some of these concepts for the first time.

For a taste of what I mean, observe the following quote:

In the end, syntax is only concerned with the surface appearance of programs, not with their meanings.

If that made you smile just a little bit, because you want to peel the onion layers away and get at the semantic questions underneath... then this book is for you.

Now before we go any further -- a couple words on what this book is not. This is not a book about software engineering. "Big O notation" does not make an appearance here in the text, not once. It isn't that we aren't concerned with "clean code" or efficiency or scalability or any of that -- but those are just implementation details that are not particularly interesting when you're otherwise diving into language semantics and finite automata.

Instead, the kind of questions this book poses are more like:

- What is a computer?
- How do you create one?
- How does a computer compute?
- How would you go about designing a language?
- Are there limits to computation? What are they?

These are fascinating questions, and reading this book was one of the first times where I really understood what separates "computer science" from "software engineering". The book is a fascinating read, even if it occasionally lapses into sentences like this:

The NFA class automatically takes account of free moves — we can see that when our NFA is started in state 3, it’s already possible for it to be in state 2 or 3 before it has read any input — so we won’t need to do anything special in NFASimulation to support them.

Awesome, but a little opaque.[^3] And/but, there's quite a bit of this; for a "simple" book about foundational computer science thinking, there's a lot of complicated material. ("But this is why you're here, right? To dip your toes into this particular pool?") It's often challenging, but also rewarding. (And there's plenty of humor along the way, if you're paying attention.)

A year from now, when I'm settling in to re-read this one, I probably won't remember the details about pushdown automata or what formalisms define a "universal Turing machine". However, I'm going to remember the in-depth discussions of static typing vs. dynamism and the trade-offs between them. I'll remember that we went through some engrossing exercises where we built up integers and arithmetic operators from scratch (even if I don't remember the details). I'll remember the flirtatious foray into language design. I'll remember The Halting Problem and most of the gory details around the limits of computation. And another thing I'll remember, statements like this:

The purpose of an expression is to be evaluated to produce another expression; a statement, on the other hand, is evaluated to make some change to the state of the abstract machine.

If you're "doing software" and you don't have a degree in computer science, I'm going to urge you to read this book. Even if you can't follow everything, you'll walk away with a lot of insight. (I'm particularly fond of the first and last thirds.) And if you do have a CS degree... Well, it's still worth skimming.


[^1]: The "full disclosure" footnote: I was briefly declared as a computer science major while in college. I performed... serviceably in an intro class (Common Lisp!) and in an "intro to AI" class (more Lisp!) but got ground to a frustrating halt in "Programming and Data Structures". I blamed Dr. Hunter, but I think I just wasn't ready to think that way. Call me a late bloomer. Call me a self-learner. Call me a frustrating bastard.

[^2]: That quote can be attributed to Miraglia's foreword to the second edition of Nicholas Zakas' Professional JavaScript for Web Developers (2nd ed.). The book is in its third edition now -- and I highly recommend that edition -- and/but: come on, that's a fantastic quote, and is the reason that the two editions will co-habitate on my bookshelf for as long as the bindings hold together.

[^3]: Partly my own fault for doing so much of the reading as my too-late-night bedtime reading.

---

A version of this review also appears on my blog: blog.founddrama.net/2013/07/review-understanding-computation/

[Stefan Kanev · Rating 5 out of 5]

Simply put: it's a great book.

It goes over various things in theory of computation. I really like both the depth and the presentation.

Unlike a "Math for Programmers" book I read recently, this one is not shallow. It goes deep enough into all its subjects (automata, state machines, Turing machines, lambda calculus, types, and so on). Things don't just get overviewed – you get enough details to appreciate how those things actually work and what they are used for. Furthermore, every single abstracting is backed up by code. You can copy it and run it and see how the abstractions behave by themselves. I personally ended up implementing a bunch of the examples in order to get a better sense of them. Particularly, Brzozowski's algorithm for minimizing a finite automata was so perplexing, that I felt I had to witness it actually working. I even wrote some code that generates GraphViz files in order to visualize the DFA. This alone speaks how engaging this book is.

I greatly recommend it to the professional programmer. If you're deep into Computer Science, you'll only get a refresher. But if you're not, you're likely to experience a lot of fascination with this curious subject.

[Shane · Rating 4 out of 5]

While most computer science students will already know the gist of this material, I found this to be a great refresher that also highlighted some other connections I had missed while learning the concepts in a purely academic setting. Stuart's use of Ruby definitely makes the material more approachable, as the semantics of Ruby are perhaps more intuitive to most developers than abstract mathematical notation.

Definitely would recommend for any Rubyist interested in either reacquainting themselves with computational theory, or are looking to get a better understanding than the one they hurriedly tried to acquire with an overworked course load.

[Regis Hattori · Rating 5 out of 5]

I have already studied all the content of this book in the College with the "Introduction to the Theory of Computation" book from Michael Sipser a long time ago. Those books are very similar in the content but Sipser's book is focused on theory and how to prove things. Stuart's book focused on explaining the theory with the help of a high-level programming language (Ruby) so it is a little bit easier to understand. Although it is more practical than its counterpart, it also contains a lot of theory that is hard to use in the real world so it is not a book I can recommend for everyone because the major part of programmers I know would think it a lit bit boring or not practical.

This book goes to the basics of computing. It does not mean it is easier to understand. Think about the difference between Assembly and JavaScript. Assembly is simpler, it has much fewer rules and edge cases, but for most programmers, it is harder to understand.

This book constructs a lot of different models like Deterministic and NonDeterministic Finite Automata (DFA and NFA), Deterministic and Nondeterministic Pushdown Automata (DPDA and NPDA) a Turing Machine (TM), and a lot of other Turing-complete models like Lamda Calculus and many others. It also compares the power of each model and how determinism and other features can or cannot increment their power. When possible, it also translates logic from one model to another to show they are equivalent in computational power. It is not proof in a mathematical sense, but it is much easier to understand when you had finished College a long time ago or if you have no Computer Science background. It also implements a simple type system to show some difficulties and trade-offs the programming designers should make.

Finally, it also talks about the limits of computation. What types of problems it cannot solve and why. It uses a technique very similar to what was used in the book "Godel, Escher, Bach" to explain Godel Incompleteness Theorem.

It has a git repository very well documented. Its README has links between chapters of the book and the repository code some of them with tests (which is very rare).

[Katherine · Rating 5 out of 5]

This book is excellent and delivers on exactly what the description says: "for (Ruby) programmers versed in modern languages, with little or no formal training in computer science". The examples are built up fairly well, given the topic. I was a little surprised at what "computation theory" really meant, so reading it in the context of book club with people who do have more formal training was quite helpful in answering my questions of "but what is the point of this" (usually the answer is: if we can show these things are equivalent, we can do mathy proofs on properties of one that apply to the other, and different kinds of properties are easier to prove with different setups). Probably much less directly practical than other programming books I've rated as 5 stars, but it's just well-done and I feel more confident in knowing a bit more of the theory.

[Georgi · Rating 4 out of 5]

Although anybody with a formal CS education will be familiar with most of the theory in the book, it was a fun read, containing lots of example code and interesting experiments. If you are curious to see FizzBuzz implemented in lambda calculus (the solution with Ruby procs is included, spanning over nearly 5 pages) or an overview of a few interesting universal systems, give this book a try.

[Jean-Luc · Rating 3 out of 5]

What book did I use for my Theory of Computation course? I don't remember. It was that (un)memorable. What did I learn in that course? Besides the Pigeonhole Principle... not much. It was a required course, so we had to take it. You'd think a required course would teach something useful, right? Well...

If Understanding Computation book had been my textbook for that course, I might have learned something. For starters, I didn't know Ruby before picking up this book, but the exposition at the beginning is just enough to get started. And then off we go: What is a program? What is a computer? How do you describe the two? What is the Lambda Calculus? What can you not program?

By itself, the book shouldn't work as a textbook since there aren't any exercises in it. Instead, the entire book is an exercise in simulating the theoretical things you would normally only read or reason about. More importantly, all the code still works! In that respect, this book holds up way better than Programming Collective Intelligence.

Recommended for anyone who wasn't a computer science major but somehow wound up in tech.

[Chad · Rating 5 out of 5]

This book is excellent. Learn about computer science and about Ruby programming at the same time. It's very approachable, very fun, and very mind-bendy. I had to pause it when live dragged me away enough that I couldn't give it the attention it deserved, but I absolutely will return to it later.

I think it makes a great third Ruby book to read; choose the first two well. I'd recommend Eloquent Ruby first, and second either Sinatra: Up And Running or Practical Object Oriented Design, if you want a pragmatic second book. Of course, you could go with Understanding Computation second if you prefer to go down a quirkier rabbit hole; there's no real need to read something else between Eloquent Ruby and this other than perhaps getting used to well-formed Ruby code that does things that can be useful to you in "real life".

Actually, Understanding Computation might even be used as a first Ruby book, if you're really inclined toward this subject matter. Have fun.

[Ray · Rating 4 out of 5]

Good over of things like FSMs, Turing machines, what it means to be Turing complete, and the limits of computability. I'm not a Ruby guru by any stretch, but his code examples are clear and readable for anyone that can follow basic modern OO code in a language like Ruby. It was fun to see the theory expressed as code and general reasoning instead of formal proofs.

I didn't have any "whoa, amazing" responses to what was presented --- most CS practitioners will encounter this stuff as part of their formal schooling. But if you've come to computation and programming from another field, or through something like a programming bootcamp, this is worth a read.

[Anthony O'Connor · Rating 4 out of 5]

Good intro to the basics

A good introduction to the basics. Machines and programs. Definition of computability. Finite state machines, deterministic and non-deterministic. All the way up to different ways of specifying semantics. BUT I found the overly long overly intricate examples in Ruby hard to follow and something of a distraction.
Short and pithy would have been better. Worth a read though.

[John Klassa · Rating 5 out of 5]

Loved it! Grad school was a very long time ago, and I’ve forgotten a lot of the academic concepts that interested me in computer science to begin with. Reading this book made me positively giddy in spots. Each chapter builds on the previous, and all of them ultimately lead to an investigation into what computation really is, where it shows up, and what it’s fundamental limits are. The author strikes a perfect balance between academic rigor and real-world accessibility. Heartily recommended.

[Tristan Colgate · Rating 4 out of 5]

This is a highly approachable introduction to computability. It has an exceptionally practical approach, guiding the reader through its various topics using simple ruby code. Even if you've never written ruby (or simply don't like it), do not dismiss the book for its choice of language.

[Shayne · Rating 3 out of 5]

A fun review of the stuff I learned in CS252 ("## - new life!"). Clever work here alongside the ruminations on computing power.

[Bohdan Shtepan · Rating 5 out of 5]

I only wish this book had a bit more math and chapters on algorithms and complexity theory.

[Jason Kowalski · Rating 5 out of 5]

An accessible, hands-on introduction to concepts of computing with example code in Python.

[Nicolay Hvidsten · Rating 2 out of 5]

This book does what it promises to do - take the reader from the most basic simplifications of computers (finite automata), through more complex simplifications (Turing machines) to reasoning about 'impossible' problems (The quotation marks are added because these problems will surely be solved one day or another by some clever fellow with too much brain activity and spare time, but are impossible for now). I really enjoyed the fact that the author was able to use Ruby code to illuminate his examples, which (me being a programmer) made them much easier to understand (easer being the operative word, this s*** is still complex as balls) than the mathematical notation commonly used by textbooks.

However, I feel that Mr. Stuart (much like all other authors of complicated, technical books I've read) falls into the trap of following a very predefined path for his line of reasoning, which leaves the reader with the feeling (at least, this was the case for me) that this is 'all planned out' and that there's a lot of information he intentionally leaves out or doesn't mention (this might not even be the case, but it still FEELS like this - which is a problem). If you have no idea what I'm talking about, read the book, and if you still don't know what I'm talking about then feel free to shake your head condescendingly.

Now, my interest in this particular field of computer science is cursory at best, which might not make me the ideal fit for Mr. Stuart's target audience, so if you get a major hard-on when syntax trees are generated (seek help) then you might get more out of this book than me.

That being said, he managed to peak my interest in concepts I felt were mind-numbingly boring in university (such as non-deterministic and deterministic finite automata), so kudos to Mr. Stuart for that. This book is a possible gold mine for the more interested pupil, especially when considering the problem of Turing completeness (in which he completely lost me, mid-chapter I put the book down and went to the fridge and rewarded myself with a beer for my efforts), reasoning about programs and (wait for it) generation of syntax trees.

All in all a good read, if you're into this sort of thing.

[Erwin · Rating 4 out of 5]

Understanding Computation provides a high-level overview of the theory behind computation. It does so from a highly practical perspective, showing the theoretical concepts using implementations in Ruby.

I used this book as a refresher on the relevant courses during my bachelor. Specifically, I was looking for ways how use the concepts in my work.

Although I had my doubts before reading, the book actually does a great job of covering most of the subjects. The focus on the practical/technical side of things, provides some nice insights that are often overlooked when purely discussing these concepts in theory. In comparison to most books on this subject the book just is a fun, casual read, even when you already familiar with most of the content. I especially liked the section on lambda calculus.

In some cases the author skips over subjects a bit fast, and keeps the description to high-level. His almost zealous attempts to refrain from using any mathematical equations/symbols, sometimes does't work out that well. Same goes for the Ruby implementations; often useful, but sometimes unnecessary or just too verbose.

All in all, great read for anyone wanting to get an introduction or quick refresher about computation (theory)

[John · Rating 4 out of 5]

This book is a little pearl. It aims right at the central topic on what is needed and not needed
to perform computation. It covers important material from operational semantics, automaton
theory, different computational models like the turing machine, lambda calculus, partical recusive functions etc. until it closes with important results of in those fields that affect the decidability of problems and ultimately the reasoning about program behaviour. It provides a practical view on that matter by providing example implementations in ruby code. It is truly a marvellous little book, that should not be missing in the bookshelf of an engineer.

The reason why it's only 4 and not 5 stars is because I would have loved to also have the mathematical notation instead of just the ruby code. Nevertheless I can wholeheartedly recommend that book.

[Ehnaton · Rating 3 out of 5]

Автор використовує Рубі, і пояснює, як створити власну метамову. Суть в тому, щоби на основі цієї штучної мови написати свій компілятор, який би запускав самописні процедури для ядра. Паралельно описується формальна семантика, функціональне програмування і нудна теорія автоматів. Купа коду, читати у форматі електронної книги, як я це робив, просто нема сенсу. Глибока і класна книжка, тільки чого ж бляха Рубі! Очі вилазять, тому що ця метамова на основі Рубі, чим далі абстракції (далі, ніж прості оператори додавання\множення..) стає просто неповоротким і потворним кнуром. Пітон був би вдалішим зручнішим вибором.

[pluton · Rating 4 out of 5]

It's an interesting book about the notion of computation, algorithms, abstract machines, and programs. Especially useful if you've had practical experience in programming and interested in more theoretical ideas behind it. Still, the book uses Ruby to explain the ideas instead of pure math.
It obviously describes the Turing machines and lambda calculus, and also partial recursive functions, SKI combinator calculus, Jota, tag systems, cyclic tag systems, Conway's Game of Life, Rule 110, and Wolfram's 2,3 Turing Machine. Turns out all of them are equivalent, universal, and are able to execute any algorithm. Fascinating!

[Cario Lam · Rating 4 out of 5]

First this is not a book about software engineering or programming. Instead it delves into the abstract core of what is the essence of a computer. Concepts like finite automata and Turing machines are a few that are presented and discussed. An engineering or mathematical background is not a requirement to tackling the material. In addition the simulations of the concepts presented are done in Ruby but fear not the author devotes a fair amount of pages to the features of Ruby so the non-programmer can understand the source code in the book.

[Jason · Rating 3 out of 5]

An interesting but brief look at the world of theoretical computer science. Combines an informal presentation with a focus on the practical implications of the concepts presented (e.g. specific examples of problems solvable by DFAs, DPDAs, etc.; automated checking of programs in spite of results like Rice's theorem). Worth the short read but for those interested in a more in-depth discussion of these topics, I recommend a textbook like Sipser's.

[Mihai · Rating 4 out of 5]

"Since every Ruby program has a unique number, we can automatically generate all possible programs: start by generating program number 1, then generate program number 2, and so on.5 If we did this for long enough, we’d eventually generate the next hot asynchronous web development framework and retire to a life of leisure." :)

[Fotis Koutoulakis · Rating 5 out of 5]

This is, simply, one of the best computer science books I've read in my career and CS education thus far.

There's so much more to what I want to say about this book, that I can't do it justice here (was thinking of doing a video review of this one). If you're interested in Computer Science, **just read it** (like, drop whatever you're doing and read it).

[Jonathan Lim · Rating 3 out of 5]

Good stuff, but not for me at this time. Maybe when I need a refresher.

[Xavier Shay · Rating 4 out of 5]

Fun read, inspired me to try out many different toy programming ideas. I skipped over the Ruby examples because the material made sense to me without it.

[Mikhail · Rating 2 out of 5]

Interesting idea, but the book is rather boring with the code and tech details.

[Pouya Kary · Rating 4 out of 5]

loved it, one of the best

[Minh Nhật · Rating 4 out of 5]

4.5
đã học được món automata T_T