Mathematics for Computer Science

7.2. The Halting Problem 217

Definition 7.2.1.

No-haltWWDfs 2 ASCIIjPsapplied tosdoes not haltg: (7.3)

We’re going to prove

Theorem 7.2.2.No-haltis not recognizable.

We’ll use an argument just like Cantor’s in the proof of Theorem 7.1.11.

Proof. For any strings 2 ASCII, letf.s/be the set of strings recognized byPs:

f.s/WWDft 2 ASCIIjPshalts when applied totg:

By convention, we associated a string procedure,Ps, with every string,s 2 ASCII,
which makesfa total function, and by definition,

s 2 No-haltIFF s...f.s/; (7.4)

for all strings,s 2 ASCII.
Now suppose to the contrary thatNo-haltwas recognizable. This means there is
some procedurePs 0 that recognizesNo-halt, which is the same as saying that

No-haltDf.s 0 /:

Combined with (7.4), we get

s 2 f.s 0 / iff s...f.s/ (7.5)

for alls 2 ASCII. Now lettingsDs 0 in (7.5) yields the immediate contradiction

s 02 f.s 0 / iff s 0 ...f.s 0 /:

This contradiction implies thatNo-haltcannot be recognized by any string pro-
cedure. 

So that does it: it’s logically impossible for programs in any particular language
to solve just this special case of the general Halting Problem for programs in that
language. And having proved that it’s impossible to have a procedure that figures
out whether an arbitrary program halts, it’s easy to show that it’s impossible to have
a procedure that is a perfect recognizer foranyoverall run time property.^3

(^3) The weasel word “overall” creeps in here to rule out some run time properties that are easy
to recognize because they depend only on part of the run time behavior. For example, the set of
programs that halt after executing at most 100 instructions is recognizable.