Now available in Japanese and Chinese!

Hello! Understanding Computation is (I hope) a fun and interesting book about computation theory, with explanations written in real Ruby code instead of mathematical notation. It contains old, deep ideas from theoretical computer science, deconstructed and explained in an engaging, practical way for an audience of working programmers without assuming any academic background.

The focus is on answering questions about computation and the fundamental mechanics of programming languages: how do they really work? what can they really do? what do the programs we write in them really mean? The book’s full of pragmatic explorations of these questions, demonstrated with real code and meaningful examples in a familiar language.

These are foundational concepts that you’ll wish you’d always known, digested and presented in a way that makes sense; universal truths which are interesting in their own right, but which also give you a better understanding of the way you do your job and the limitations of what’s possible.

Over the course of the book, you will:

• implement two different interpreters, and a compiler, for a toy programming language;
• build simulations of deterministic and nondeterministic finite automata, pushdown automata and Turing machines;
• build a simple implementation of regular expressions from scratch;
• construct a lexical analyzer and LL parser for a toy programming language;
• write Ruby programs in the style of the lambda calculus;
• implement the lambda calculus directly in Ruby;
• implement other universal systems (partial recursive functions, the SKI combinator calculus, Iota, tag systems and cyclic tag systems) in Ruby;
• extend a program to make it compute its own source code;
• investigate programs that can’t be written in Ruby; and
• build a simple type system.

To find out more, please check out the table of contents, download a sample chapter, read what people are saying on Twitter, watch some related videos, download the example code, and get in touch with any questions or comments.