(TMs can be linked this way, but the details are not important to this discussion.) NotH will return
true if H fails to halt under these conditions, and will loop forever if H does halt. In pseudocode NotH looks
like this:
NotH(p)
if(H(p, p) is false) return true
else
while(true) {} //loop forever
endNotH
Now suppose we test NotH itself with this approach. That is, suppose we pass the code for NotH itself to
NotH. We will refer to the code for NotH as 'nh', and we can ask, ???Does the program NotH halt when it is
run with its own code as input???? Saying this another way, does NotH(nh) halt?
If NotH(nh) halts, this can only be because H(nh,nh) reports that NotH does not halt. On the other
hand, if NotH(nh) does not halt, this can only be because H(nh,nh) reports that NotH does halt. These are
obviously contradictions.
28 ALGORITHMS [CHAP. 2
The original assumption, that a TM does exist that can determine whether any particular program will
run to completion when presented with any arbitrary input data, must be incorrect. That assumption led to the
contradictory state illustrated by NotH. Therefore, computer scientists conclude that there can be no one algorithm
that can determine whether any particular program will run to completion, or fail to run to completion, for every
possible set of inputs.
Pages:
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85