Limits to Computation - Data Structures and Algorithm Analysis - page 559

17.3.2 The Halting Problem Is Unsolvable
While there might be intellectual appeal to knowing that there exists some function
that cannot be computed by a computer program, does this mean that there is any
such useful function? After all, does it really matter if no program can compute a
“nonsense” function such as shown in Bin 4 of Figure 17.7? Now we will prove
that the Halting Problem cannot be computed by any computer program. The proof
is by contradiction.
We begin by assuming that there is a function named halt that can solve the
Halting Problem. Obviously, it is not possible to write out something that does not
exist, but here is a plausible sketch of what a function to solve the Halting Problem
might look like if it did exist. Function halt takes two inputs: a string representing
the source code for a program or function, and another string representing the input
that we wish to determine if the input program or function halts on. Function halt
does some work to make a decision (which is encapsulated into some fictitious
function named PROGRAMHALTS ). Function halt then returns true if the input
program or function does halt on the given input, and false otherwise.

boolhalt(Stringprog,Stringinput){
if(PROGRAMHALTS(prog,input))
returntrue;
else
returnfalse;

}

We now will examine two simple functions that clearly can exist because the
complete code for them is presented here:

//Returntrueif"prog"haltswhengivenitselfasinput
boolselfhalt(Stringprog){
if(halt(prog,prog))
returntrue;
else
returnfalse;

}

//Returnthereverseofwhatselfhaltreturnson"prog"
voidcontrary(Stringprog){
if(selfhalt(prog))
while(true);//Gointoaninfiniteloop

}

What happens if we make a program whose sole purpose is to execute the func-
tion contrary and run that program with itself as input? One possibility is that
the call to selfhalt returns true ; that is, selfhalt claims that contrary
will halt when run on itself. In that case, contrary goes into an infinite loop (and
thus does not halt). On the other hand, if selfhalt returns false , then halt is
proclaiming that contrary does not halt on itself, and contrary then returns,