Understanding Computation

Part II. Computation and Computability

Throughout the first part of this book we’ve played around with familiar examples of computation: imperative programming languages, state machines, and general-purpose computers. Those examples have showed us that computation is—more or less—the process of using a system to manipulate information and answer questions.

Now, in this second part, we’re going to be a bit more adventurous. We’ll start by looking for computation in unfamiliar places, and finish by exploring the fundamental limits of what computing machines can do.

As programmers we work with languages and machines that are designed to fit our mental models of the world, and we expect them to come equipped with features that make it easy to translate our ideas into implementations. These human-centered designs are motivated by convenience rather than necessity; even the simple design of a Turing machine is meant to remind us of a mathematician working with pencil and paper.

But friendly, familiar machines aren’t the only places where computation can happen. More unusual systems can be just as computationally powerful, even if their inner workings aren’t as easy for humans to control or to understand. We’ll investigate this idea in Chapter 6 by trying to write programs in an extremely minimal language that doesn’t seem to have any useful features at all, and follow the thread further in Chapter 7, where we’ll survey a variety of simple systems and see how they’re able to perform the same ...