R. Clayton (rclayton@monmouth.edu)
Tue, 28 Mar 2000 13:42:16 -0500 (EST)
A few lectures ago I mentioned the halting problem and tried to describe it.
I'd like to take another stab at it in this message.
The halting problem was originally stated and proved impossible to solve by the
English mathematician Alan Turing in the 40s, and he used his Turing machine
model of computation in the proof. I'm going to skip the Touring machine model
and use a procedural pseudo-language. The only interesting feature of the
pseudo-language is that procedures can accept other procedures as input
arguments; this feature is interesting but not unusual - languages such as C
and Pascal have a similar feature.
Given a procedure P and an input instance I, the computation P(I) can either
execute for a finite time and produce an answer or execute forever and produce
no answer. In the latter case, the computation P(I) is said to diverge or be a
divergent computation; the most common form of divergent computation is the
infinite loop.
Many people - for example, software testers - have often wanted to be able to
determine, in a finite amount of time, if procedure P diverges or not on input
instance I. Note that the requirement for an answer after a finite time means
that just executing P(I) and examine the results is not acceptable because, in
general, it's impossible to differentiate between a computation that takes a
long, long time to produce an answer and a divergent computation (Turing proved
this; I'm going to skip the proof and assume it's true). The problem of
determining, in finite time, if P(I) diverges or not is called the Halting
Problem.
Turing showed no algorithm solves the Halting Problem. The proof is by
contradiction. Suppose the procedure Halt solves the Halting Problem: Halt
accepts as input procedure P and input instance I and returns, in finite time,
true if P(I) halts with an answer or false if P(I) diverges.
Using Halt, we can build the procedure HaltLoop, which accepts as input a
procedure P and an input instance I and behaves as follows:
boolean HaltLoop(P, I)
L1: if Halt(P, I) then goto L1
return false
If P(I) halts with an answer, then HaltLoop(P, I) diverges; if P(I) diverges,
then HaltLoop returns false.
Notice that HaltLoop is a procedure that accepts as input a procedure; that
means we can call HaltLoop on itself:
C: HaltLoop(HaltLoop, HaltLoop)
The question is, what does the call C return? If the call C returns false,
then HaltLoop diverges when called on itself, and the call C diverges. On the
other hand, if the call C diverges, then HaltLoop, and so call C, returns
false. Because there's a contradiction either way (and there are only two
ways), the supposition about the existence of Halt must be false.
This proof by contradiction was developed in the mid 60s by the English
computer scientist Christopher Strachey. In addition to using Turing machines,
Turing's original proof used a mathematical technique known as diagonalization
and was intimately related to the structure of Turing machines.
Problems for which there exist no possible algorithmic solutions are known as
undecidable problems; "undecidable" coming from the proven absence of a
decision algorithm for the problem.
It's useful to know that the halting problem is undecidable because you can use
the absence of any algorithm for Halt to show that other things are undecidable
too. For example, Java and Internet security are hot topics right now, and
everybody wants algorithms that determine if an applet will do malicious things
when you run it on your browser. Unfortunately, almost all such security
problems are undecidable because, if such a decision algorithm existed for one
of them, the algorithm could be used to solve the halting problem.
To illustrate, suppose I have a procedure BadReader which accepts as input an
applet and the name of a file and returns true if the applet reads the file and
returns false if the applet never reads the file. I can use BadReader to solve
the halting problem as follows:
boolean Halt(A)
A' = applet{ A(); read data from a secret file }
return BadReader(A', a secret file)
"a secret file" is the name of a file known only to Halt, which means that, for
any applet A, BadReader(A, a secret file) returns false. If applet A
terminates, then A' goes on to read the secret file and BadReader returns true;
if applet A diverges A' will never read the secret file and BadReader returns
false.
This archive was generated by hypermail 2.0b3 on Wed Apr 26 2000 - 09:35:05 EDT