Re: What is the Result from Invoking this Halt Function?

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 08/08/04 

Date: 8 Aug 2004 10:29:02 -0700

Peter Olcott says...

>Quick Summary:
>Alan Turing conclusively proved is that it is impossible to construct a halt
>analyzer that always returns a correct result back to the program being
>analyzed.
>
>Since returning the result back to the program being analyzed is not the only
>way to construct a halt analyzer, his proof did not show that constructing
>a halt analyzer that works correctly for all input is impossible
>
>So then you have no problem completely agreeing with the above statements?

Yes. Turing proved that, under a very precise definition of "solving the
halting problem", there is no program that solves the halting problem. If
you allow a more general definition of "solving the halting problem", then
Turing's proof does not directly apply.

However, all the evidence so far supports the thesis that every
function that is computable in a general sense is also computable
in Turing's more restricted sense. So there is no reason to believe
that generalizing the notion of "solving the halting problem" would
make any difference.

Certainly you haven't given any evidence that it makes any difference. 

--
Daryl McCullough
Ithaca, NY

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: Disproof of the Halting Problems Conclusion
    ... > statement of the Halting Problem. ... The state transition from qto ) indicates that the TM ... has determined that the program being analyzed will not halt. ... transition is equivalent to the halt analyzer returning its result to the ...
    (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 ...
    (sci.logic)
  • Re: simple and beauty strategy
    ... the halting problem is a decision problem ... Alan Turing proved in 1936 that a general algorithm to solve the ... the program will eventually halt when run with that input. ... undecidability of a problem in the lambda calculus had already been ...
    (rec.gambling.lottery)