What is needed is an algorithm for inspecting the program, an algorithm which will tell us
whether the program will eventually halt, given a particular set of inputs.
If there is such an algorithm for inspecting a program, there is a TM to implement it. Unfortunately however,
the halting problem has been shown to be an unsolvable problem, and the proof that there is no solution is
a proof by contradiction. We begin by assuming there is, indeed, a TM that implements a solution to the halting
problem. We will call this TM 'H', for it solves the big halting problem.
The input to H must include both the program under test p, and the input to the program i. In pseudocode,
we call H like this:
H(p, i)
We assume that H must itself halt, and that the output from H must be true or false??”the program under
test must be found either to halt, or not to halt. Whatever H does, it does not rely on simply running the
program under test, because H itself must always halt in a reasonable time.
Now suppose that we create another TM called NotH that takes a symbolic argument that will include the
encoding of a program, p. NotH will call H, passing the code for p as both the program p and the input data i
to be tested.
Pages:
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84