5.3. The Halting Problem 95
Larger Infinities
There are lots of different sizes of infinite sets. For example, starting with the
infinite set,N, of nonnegative integers, we can build the infinite sequence of sets
NstrictP.N/strictP.P.N//strictP.P.P.N///strict::::
By Theorem 5.2.6, each of these sets is strictly bigger than all the preceding ones.
But that’s not all: the union of all the sets in the sequence is strictly bigger than each
set in the sequence (see Problem 5.10). In this way you can keep going indefinitely,
building “bigger” infinities all the way.
5.3 The Halting Problem
Granted that towers of larger and larger infinite sets are at best just a romantic
concern for a computer scientist, thereasoningthat leads to these conclusions plays
a critical role in the theory of computation. Cantor’s proof embodies the simplest
form of what is known as a “diagonal argument.” Diagonal arguments are used to
show that lots of problems logically just can’t be solved by computation, and there
is no getting around it.
This story begins with a reminder that having procedures operate on programs
is a basic part of computer science technology. For example,compilationrefers to
taking any given program text written in some “high level” programming language
like Java, C++, Python,... , and then generating a program of low-level instruc-
tions that does the same thing but is targeted to run well on available hardware.
Similarly,interpretersorvirtual machinesare procedures that take a program text
designed to be run on one kind of computer and simulate it on another kind of com-
puter. Routine features of compilers involve “type-checking” programs to ensure
that certain kinds of run-time errors won’t happen, and “optimizing” the generated
programs so they run faster or use less memory.
Now the fundamental thing that computation logically just can’t do is aperfect
job of type-checking, optimizing, or any kind of analysis of the complete run time
behavior of programs. In this section we’ll illustrate this with a basic example
known as theHalting Problem. The general Halting Problem for some program-
ming language is, given an arbitrary program, recognize when running the program
will not finish successfully —halt —because it aborts with some kind of error, or
because it simply never stops. Of course it’s easy to detect when any given program
willhalt: just run it on a virtual machine and wait. The problem is what if the given
program doesnothalt —how do you recognize that? We will use a diagonal argu-
