What Is Computable?
Let me remind you of some of the problems of computing
—RICHARD FEYNMAN (1965 Nobel Prize in physics)
We’ve now seen quite a number of clever, powerful, and beautiful algorithms—algorithms that turn the bare metal of a computer into a genius at your fingertips. In fact, it would be natural to wonder, based on the rhapsodic rhetoric in the preceding chapters, if there is anything that computers cannot do for us. The answer is absolutely clear if we limit ourselves to what computers can do today: there are plenty of useful tasks (mostly involving some form of artificial intelligence) that computers can’t, at present, perform well. Examples include high-quality translation between languages like English and Chinese; automatically controlling a vehicle to drive safely and quickly in a busy city environment; and (as a teacher, this is a big one for me) grading students’ work.
Yet, as we have seen already, it is often surprising what a really clever algorithm can achieve. Perhaps tomorrow, someone will invent an algorithm that will drive a car perfectly or do an excellent job of grading my students’ work. These do seem like hard problems— but are they impossibly hard? Indeed, is there any problem at all that is so difficult, no one could ever invent an algorithm to solve it? In this chapter, we will see that the answer is a resounding yes: there are problems that can never be solved by computers. This profound fact—that some things are “computable” and others are not— provides an interesting counterpoint to the many algorithmic triumphs we’ve seen in the preceding chapters. No matter how many clever algorithms are invented in the future, there will always be problems whose answers are “uncomputable.”
The existence of uncomputable problems is striking enough on its own, but the story of their discovery is even more remarkable.