Re: Disproof of the Halting Problem's Conclusion

From: Isaac To (iketo2_at_netscape.net)
Date: 07/22/04 

Date: 22 Jul 2004 21:08:10 +0800

>>>>> "Daryl" == Daryl McCullough <daryl@atc-nycorp.com> writes:

    Daryl> There are two possibilities here: (1) Your hypothetical
    Daryl> void WillHalt can be simulated by a Turing Machine, or (2)
    Daryl> It can't.

    Daryl> In case (1), your program has no relevance to Turing's
    Daryl> proof, since he was proving that no *Turing* machine
    Daryl> program can solve the halting problem. In case (2), your
    Daryl> program fails; it can't solve the halting problem any
    Daryl> better than bool WillHalt() can.

Nope. If his hypothetical void WillHalt() cannot be simulated by a
Turing Machine (i.e., we cannot show that its power is limited by the
power of a Turing machine), then all bets are off. Indeed, in that
case even if the function is bool WillHalt(), the proof of the halting
problem breaks down. The proof says that "there is no Turing machine
capable of solving the halting problem for Turing machines". It says
nothing about machines that are more capable than Turing machines
(i.e., there might be more powerful machines that solve the halting
problem for Turing machines). The proof breaks down---since the
Halting solver is more powerful than Turing machines, and because the
Halting solver is only required to take Turing machines (rather than
the stronger machines which the Halting solver is implemented), you
cannot modify it to a Turing machine so as to pass it to the Halting
solver itself.

Of course, in Peter's case, his machine is weaker than a Turing
machine, so your next paragraph still makes perfect sense.

Regards,
Isaac.

Relevant Pages

  • Re: Disproof of the Halting Problems Conclusion
    ... this would be the same text in which Lintz proves that the Halting ... >> language version of the Halting Problem on which it makes sense to talk ... it does not define what a Turing machine is. ... refer to a string, but then talks about "Turing machine M". ...
    (sci.logic)
  • Re: Disproof of the Halting Problems Conclusion
    ... >> void WillHalt can be simulated by a Turing Machine, ... >> machine program can solve the halting problem. ... >> the halting problem any better than bool WillHaltcan. ...
    (sci.logic)
  • Re: Disproof of the Halting Problems Conclusion
    ... >> Peter Olcott says... ... >> void WillHalt can be simulated by a Turing Machine, ... >> the halting problem any better than bool WillHaltcan. ...
    (sci.logic)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... Disproving the Halting Problem ... the only way to construct a halt analyzer, ... another Turing Machine, or invoked independently of any other Turing ...
    (sci.logic)
  • Re: Peter Olcotts Source of Confusion
    ... If you would, please express the Halting ... the definition is one reason people think you really ... State the Halting problem. ... >Given a description of a Turing machine M and an input w, does M, ...
    (sci.logic)