Page 222 - Discrete Mathematics and Its Applications

3.1 Algorithms 201

ALGORITHM 7 Greedy Algorithm for Scheduling Talks.

procedure schedule(s 1 ≤ s 2 ≤ ··· ≤ s n : start times of talks,
e 1 ≤ e 2 ≤ ··· ≤ e n : ending times of talks)
sort talks by finish time and reorder so that e 1 ≤ e 2 ≤ ... ≤ e n
S := ∅
for j := 1 to n
if talk j is compatible with S then
S := S ∪{talk j}
return S{S is the set of talks scheduled}

The Halting Problem

We will now describe a proof of one of the most famous theorems in computer science. We will
show that there is a problem that cannot be solved using any procedure. That is, we will show
thereareunsolvableproblems.Theproblemwewillstudyisthehaltingproblem.Itaskswhether
there is a procedure that does this: It takes as input a computer program and input to the program
and determines whether the program will eventually stop when run with this input. It would be
convenient to have such a procedure, if it existed. Certainly being able to test whether a program
entered into an infinite loop would be helpful when writing and debugging programs. However,
in 1936 Alan Turing showed that no such procedure exists (see his biography in Section 13.4).
Before we present a proof that the halting problem is unsolvable, first note that we cannot
simply run a program and observe what it does to determine whether it terminates when run
with the given input. If the program halts, we have our answer, but if it is still running after any
fixed length of time has elapsed, we do not know whether it will never halt or we just did not
wait long enough for it to terminate. After all, it is not hard to design a program that will stop
only after more than a billion years has elapsed.
We will describe Turing’s proof that the halting problem is unsolvable; it is a proof by
contradiction. (The reader should note that our proof is not completely rigorous, because we
have not explicitly defined what a procedure is. To remedy this, the concept of a Turing machine
is needed. This concept is introduced in Section 13.5.)

Proof: Assume there is a solution to the halting problem, a procedure called H(P, I). The
procedure H(P, I) takes two inputs, one a program P and the other I, an input to the program
P . H(P,I) generates the string “halt” as output if H determines that P stops when given I as
input. Otherwise, H(P, I) generates the string “loops forever” as output. We will now derive a
contradiction.
When a procedure is coded, it is expressed as a string of characters; this string can be
interpreted as a sequence of bits. This means that a program itself can be used as data. Therefore
a program can be thought of as input to another program, or even itself. Hence, H can take a
program P as both of its inputs, which are a program and input to this program. H should be
able to determine whether P will halt when it is given a copy of itself as input.
To show that no procedure H exists that solves the halting problem, we construct a simple
procedure K(P), which works as follows, making use of the output H(P, P). If the output of
H(P, P) is “loops forever,” which means that P loops forever when given a copy of itself as
input, then K(P) halts. If the output of H(P, P) is “halt,” which means that P halts when given
a copy of itself as input, then K(P) loops forever. That is, K(P) does the opposite of what the
output of H(P, P) specifies. (See Figure 2.)
Now suppose we provide K as input to K. We note that if the output of H(K, K) is “loops
forever,” then by the definition of K we see that K(K) halts. Otherwise, if the output of H(K, K)