Understanding Computation

Chapter 8. Impossible Programs

The most merciful thing in the world, I think, is the inability of the human mind to correlate all its contents.

—H. P. Lovecraft

In this book, we’ve explored different models of computers and programming languages, including several kinds of abstract machine. Some of those machines are more powerful than others, and two varieties in particular come with pretty obvious limitations: finite automata can’t solve problems that involve unrestricted counting, like deciding whether a string of brackets is correctly balanced, and pushdown automata can’t handle any problem where information needs to be reused in more than one place, like deciding whether a string contains the same number of a, b, and c characters.

But the most advanced device we’ve seen, the Turing machine, seems to have everything that we need: it’s got unlimited storage that can be accessed in any order, arbitrary loops, conditionals, and subroutines. The extremely minimal programming language from Chapter 6, the lambda calculus, turned out to be surprisingly powerful too: with a little ingenuity it allows us to represent simple values and complex data structures as pure code, as well as implement operations that manipulate those representations. And in Chapter 7, we saw many other simple systems that, like the lambda calculus, have the same universal power as Turing machines.

How much further can we push this progression of increasingly powerful systems? Perhaps not indefinitely: our attempts ...