A modern view of the halting problem
- From: "Charles A. Crayne" <ccrayne@xxxxxxxxxx>
- Date: Fri, 20 Oct 2006 18:03:43 -0700
In 1936, Alan Turing presented a proof that it is possible to write a
program such that it is not possible by analysis alone (i.e. without
actually running the program) to determine if the program will eventually
halt. At the time, this proof created quite a stir among his colleagues,
however after 70 years of rapid development in computer science, it is now
clear that his proof, albeit valid, is more of a parlor trick, than any
real insight into computing theory, and, although it does apply to
computers, it has no special connection with them. To demonstrate that
these two points are true, it is necessary only to restate Turing's proof
without reference to computers.
Let us postulate that the "The Great Melvini" claims to be able to predict
which of two checkers (one red, one black) a volunteer will choose in any
given trial. To lend credibility to this test, "The Amazing Randi"
volunteers to be the one who chooses the checker.
The fairness of such a test clearly depends upon the time sequence in which
the predictions and the choices are made and revealed. If, for example, the
rules allow Randi to know Melvini's prediction before making his own
choice, then Randi is in complete control of the results, and can make
Melvini look either very good, or very bad, as Randi may wish. As this
situation should be obvious to the casual observer, it is unlikely to draw
much of a crowd. And yet, this unlikely set of rules is exactly what
Turing choose for his famous proof.
In other words, by proposing a program which consults an oracle, and then
does the opposite of whatever the oracle predicts, Turing has not so much
proven anything about computers, as he has drawn on the well known fact
that predicting the future is fraught with difficulties.
However, since Turing did choose to focus on computers, let me offer a
couple of observations on the consequences of his proof:
To begin with, since the generalized proof applies to both humans and
computers, any proof which is derived from his proof also applies to both
humans and computers. There is no "wiggle room" for a human to "step
outside the box" and decide what a computer can not decide. So long as the
argument derives from Turing's proof, then anything which is undecidable
by a computer, is also undecidable by a human.
Next, the proof is not limited to halting, nor even to two alternatives.
The essence of the proof is the attempt to predict a future event which is
under some other entity's control. In the real world, this situation
rarely arises, if for no better reason that we know better than to try. In
the real world, one does not write programs which use infinite loops as a
function's return code. Nor, except as a joke, programs which accept a
user's input command, and then do something entirely different.
And finally, in the real world, one does not demand 100% precision. The
fatal flaw in Turing's proof is that it is qualitative, and not
quantitative. If one wishes to write a program which analyzes programs
submitted by students, and reject those which are likely to loop forever,
one doesn't care that it may not be possible to catch them all, but rather
what percentage of such programs can be caught. And for such questions,
Turing's proof has no answer.
.
- Follow-Ups:
- Re: A modern view of the halting problem
- From: KiLVaiDeN
- Re: A modern view of the halting problem
- From: randyhyde@xxxxxxxxxxxxx
- Re: A modern view of the halting problem
- From: Herbert Kleebauer
- Re: A modern view of the halting problem
- From: robertwessel2
- Re: A modern view of the halting problem
- From: Phil Carmody
- Re: A modern view of the halting problem
- Prev by Date: Re: HLL design
- Next by Date: Re: HLL design
- Previous by thread: HLL design
- Next by thread: Re: A modern view of the halting problem
- Index(es):
Relevant Pages
|
