Understanding Computation

I’ve written a book called “Understanding Computation” for O’Reilly Media. You can buy it from the O’Reilly shop or Amazon (US, UK). Here’s a sample chapter and all the code.

It’s a book about old, deep ideas from theoretical computer science, deconstructed and explained in an engaging, practical way for an audience of working programmers.

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 consists 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.

The chapters are:

Introduction. What is this book for? Who should read this book? What is Ruby?
Part I: Programs and Machines
- The Meaning of Programs. What is a programming language? When we write a program, how do we know what it means, and how does the computer know?
- The Simplest Computers. What does the simplest possible computer look like? What can it be used for? How powerful is it?
- Just Add Power. How can we make a simple computer more powerful? What can we do with it? How much more powerful can it get?
- The Ultimate Machine. What does the most powerful computer look like? How simple is it? How can we program it?
  - Turing machines
  - Universal Turing machine
Part II: Computation and Computability
- Programming with Nothing. How many features does a programming language need? How much work can a language do if we remove all of its features?
- Universality is Everywhere. Can a simple system do as much as the most powerful computer? How simple is it possible to get?
- Impossible Programs. What jobs can programs do? How do they do them? What jobs are impossible for any program to do?
- Programming in Toyland. How can programs handle difficult or impossible problems? How do programs cope with incomplete or contradictory information?