7.2. The Halting Problem 215
Here is why the diagonal argument has its name: we can form a sequenceDcon-
sisting of the bits on the diagonal.
DD 1 1 1 0 0 1 ;
Then, we can form another sequence by switching the 1 ’s and 0 ’s along the diago-
nal. Call this sequenceC:
CD 0 0 0 1 1 0 :
Now ifnth term ofAnis 1 then thenth term ofC is 0 , andvice versa, which
guarantees thatCdiffers fromAn. In other words,Chas at least one bit different
fromeverysequence on our list. SoCis an element off0;1g!that does not appear
in our list—our list can’t be complete!
This diagonal sequenceC corresponds to the setfa 2 Aja ...g.a/gin the
proof of Theorem 7.1.11. Both are defined in terms of a countable subset of the
uncountable infinity in a way that excludes them from that subset, thereby proving
that no countable subset can be as big as the uncountable set.
7.2 The Halting Problem
Although towers of larger and larger infinite sets are at best a romantic concern for
a computer scientist, thereasoningthat leads to these conclusions plays a critical
role in the theory of computation. Diagonal arguments are used to show that lots of
problems 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.
The fundamental thing that just can’t be done by computation is aperfectjob of
type-checking, optimizing, or any kind of analysis of the overall run time behavior
of programs. In this section, we’ll illustrate this with a basic example known as the
Halting Problem. The general Halting Problem for some programming language
