Re: A modern view of the halting problem


Charles A. Crayne wrote:


To begin with, since the generalized proof applies to both humans and
computers,

This is where you are completely mistaken.
The generalized proof of undecideability (the generic problem posed by
the halting problem) does *not* apply to humans. It applies to *Turing
Machines* (an abstract model which models all real computers, as far as
we know). Human problem solving processes are *not* modelled by the
Turing machine. Yes, a human being *can* follow an algorithm
step-by-step, and by doing so be limited to the same results as any
proof about Turing machines, but humans can also transcend that.

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.

Yes, there is. Try reading Godel's incompleteness theorem some time.
Unless you can prove that the Human brain is Turing complete, you'll
have to accept the fact that humans *do* operate "outside the box".
Humans have things like "brainstorming", "flashes of brilliance",
"divergent thinking", etc., etc., that computers don't benefit from.


So long as the
argument derives from Turing's proof, then anything which is undecidable
by a computer, is also undecidable by a human.

Wrong.


Next, the proof is not limited to halting, nor even to two alternatives.

The generic proof is one of undecideability. Which the halting problem
can be reduced to. That was the main important of the halting problem,
it was shown to be undecideable and, therefore, if the halting problem
could be reduced to any other problem, then that other problem was also
undecideable.

For example, given the *true* purpose of your post as a subtle attack
on the claim that a disassembler cannot differentiate code and data, it
was show long ago that the halting problem can be reduced to the
problem of differentiating code and data in a Von Neumann machine.



The essence of the proof is the attempt to predict a future event which is
under some other entity's control.

No. It is not.
The essence of the proof (of any decideability problem) is "does there
exist an algorithm that can compute this function?"


In the real world, this situation
rarely arises, if for no better reason that we know better than to try.

In the real world, wanting to know whether an algorithm exists is a
very practical problem. And it *does* arise all the time. For example,
as an instruction, I would love to feed a program a copy of a working
solution to a programming problem and have that program compare my
working solution against a student's submission and tell me if the two
programs are equivalent (that is, do they produce the same outputs for
all the same inputs?). Alas, the problem is undecideable, so if I'm
looking for a *perfect* solution to this problem, I shouldn't waste my
time on the project (of course, if I'm willing to accept a "less than
perfect solution, that's another issue entirely; that's why, for
example, disassembler programs exist even though the generic problem of
disassembly is undecideable).


In
the real world, one does not write programs which use infinite loops as a
function's return code.

???
Not intentionally, anyway :-)
The main point of a "halting program" would be to verify that a program
that should halt, does indeed halt and doesn't contain any unintended
infinite loops (among other problems).


Nor, except as a joke, programs which accept a
user's input command, and then do something entirely different.

Surely you've done some embedded programming. Surely you realize that
infinite loops *are* valuable in some instances, right?



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.

No flaw at all. If you're willing to accept a less that correct
solution, including no solution at all for some sets of inputs, then
feel free to write the code. As I've pointed out already, the fact that
it is impossible to write a perfect disassembler hasn't stopped anyone
from writing imperfect ones. Some are just "less perfect" than others.
However, anyone who claims that a perfect disassembler can be written
(as Rene has, lately) is just flat out wrong. Likewise, you can write
a program that compares *many* programs for equivalency, but there's no
way it's going to work for all programs. And, despite what Herbert
might think, limited resources make no difference (actually, a limited
resource machine *does* make a difference, what it means is that the
analysis program can process even *fewer* inputs because it doesn't
have the resources to handler larger problems).


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.

The open questions, then, are "how many programs *will* it catch?" and
"what sort of effort is necessary to even catch the common problems?"
Yes, for those problems Turing's proof has no answer. But we *do* know
that the general problem is undecideable, so we don't run off trying to
do a perfect solution (as a certain disassembler author around here
seems to be doing) and we adjust our strategy accordingly.

This is why you study theoretical computer science. So you understand
things like this. And reading a Wikipedia article is not a good way to
study computer science.
Cheers,
Randy Hyde

.

Relevant Pages

  • Re: A modern view of the halting problem
    ... Turing did basically introduce turning machines as a formal way ... Entscheidungsproblem could be recast as the halting problem, ... And of course the results have no special relationship to computers. ... the halting problem is something of a triviality (just like ...
    (alt.lang.asm)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... unsolvability of the Halting Problem for a real programming language. ... The Halting Problem isn't really about computers, at least not directly, ... > computers* that does not contrive a logic paradox to make the proof? ... A paradox is an argument in which a contradiction follows from ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... the Halting Problem applies to "real" computers as much as Turing ... on what they can compute is obviously inherited by real machines. ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... >unsolvability of the Halting Problem for a real programming language. ... with computers. ... A paradox is an argument in which a contradiction follows from ...
    (sci.logic)