Re: Disproof of the Halting Problem's Conclusion

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 07/24/04 

Date: Sat, 24 Jul 2004 14:40:21 GMT

"Chris Menzel" <cmenzel@remove-this.tamu.edu> wrote in message news:slrncg0a0c.3mj.cmenzel@philebus.tamu.edu...
> On Thu, 22 Jul 2004 00:05:33 GMT, Peter Olcott <olcott@worldnet.att.net>
> said:
> > It is not merely that I have not accepted a proof that everyone
> > else accepts. It is that my disprove of this proof has not yet
> > been found in error.
>
> Well, golly. I guess it wasn't clear to me that you thought you'd
> "disproved" the proof -- not that it's ever been clear to me what you
> think your doing. Be that as it may, if you've "disproved" the proof,
> that means you think that either an invalid inference is made at some
> point, or you think one of the premises is false. So perhaps it will be
> useful if you explicitly identify the problem in a very clear and simple
> statement of the Halting Problem. Even if it might be pointless to try
> to get you to see that there is no problem, this will at least make it
> clear to posterity what it is that you see that everyone else doesn't,
> or vice versa. I've got an hour to kill, so let me join Daryl in the
> ranks of second-order crackpottery and try to spell out the argument
> carefully.
> +------------+
                                           | |
                                           v |
q(0)-------->q(y)------->q(a)-------->q(b)
    |
    |
    +-------->(q(n))

>From An Introduction to Formal Languages and Automata
by Peter Lintz, page 319

The state transition from q(0) to q(y) indicates that the TM
has determined that the program being analyzed will halt.

The state transition from q(0) to (q(n)) indicates that the TM
has determined that the program being analyzed will not halt.

Here is my part:
The state transition from q(y) to q(a) is not mandatory. This state
transition is equivalent to the halt analyzer returning its result to the
program being analyzed. Since there are other ways to define a
halt analyzer that do not return their result back to the program being
analyzed, therefore Turing did not prove that it is impossible to solve
the Halting Problem.

Turing did not show that there is no possible way to refute:
No program can ever be written to determine whether any
arbitrary program will halt

He merely showed one way that will not always work.

Relevant Pages

  • Re: Halting Problem Final Conclusion
    ... > was to detect programs that failed to halt, ... The primary benefit of a universal Halting Problem ... about programs that fail to halt. ... if this program would halt" analyzer may be as ...
    (comp.theory)
  • Re: Halting Problem Final Conclusion
    ... > was to detect programs that failed to halt, ... The primary benefit of a universal Halting Problem ... about programs that fail to halt. ... if this program would halt" analyzer may be as ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... >Alan Turing conclusively proved is that it is impossible to construct a halt ... >way to construct a halt analyzer, his proof did not show that constructing ... halting problem", there is no program that solves the halting problem. ... that generalizing the notion of "solving the halting problem" would ...
    (comp.theory)
  • Re: What is the Result from Invoking this Halt Function?
    ... >Alan Turing conclusively proved is that it is impossible to construct a halt ... >way to construct a halt analyzer, his proof did not show that constructing ... halting problem", there is no program that solves the halting problem. ... that generalizing the notion of "solving the halting problem" would ...
    (sci.logic)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... > If the state transition diagram representation of the Halting Problem ... > result is that this counter-example program does indeed halt. ... Turing shows that there is absolutely positively _no_ turing machine ...
    (comp.theory)
Quantcast