Re: Disproof of the Halting Problem's Conclusion

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

Date: 24 Jul 2004 23:04:38 +0800

>>>>> "Peter" == Peter Olcott <olcott@worldnet.att.net> writes:

    Peter> Let's make a little analogy here. You can't ever make a
    Peter> program that runs correctly because it is trivial to smash
    Peter> the computer making the program not run correctly.

Smashing into a computer change the interpretation of the answers of
the computer. The modifications we talked about doesn't.

    Peter> Exactly how does the fact that you can corrupt one program
    Peter> in any way effect the capability of the original
    Peter> uncorrupted program?

Your whole point is that "if you modify my halting solver to return a
boolean value, then your result about my halting solver can't exists
does not carry to my program, because it's a different program." This
would be correct if my modification make the programs answer
differently---i.e., some input that the original program would answer
"yes", say on the screen, would cause the modified program to return
"no"; or vice-versa.

But as long as you modify your program correctly, this is not the
case. That is, if your program has a reasonable notion of "printing
to the screen and terminate" to answer whether the input is a halting
instance. You simply modify any location of your program that prints
to screen to check what you are printing, and if it is "yes" then you
instead cause the WillHalt function return 1 using whatever mechanism
available, and if it is "no" then you makes it return 0. Then the
modified program can be proved to have equivalent behaviour to yours,
except that while your program would output to screen, the modified
program return boolean.

Then your whole argument breaks down. I don't have to attack your
program directly, but instead attack the modified version of your
program. Assume your program really exists, then the modified version
must also exist, and the modified program is proved to behave exactly
the same as your program apart from the way it outputs. Since I can
show you that the no program would exhibit that behaviour, this leads
to a contradiction. So your program cannot exist either.

This is the whole strategy of the proof of the impossibility of
Halting problem: once you know that the halting problem of Turing
machines cannot be solved in Turing machines itself, you also know
that the halting problem for any Turing equivalent machine (or
"Turing-capable" machine, i.e., able to express the computation of a
Turing machine) cannot be solved using anything with no stronger power
than a Turing machine.

Regards,
Isaac.

Relevant Pages

  • Re: Disproof of the Halting Problems Conclusion
    ... Peter> the computer making the program not run correctly. ... But as long as you modify your program correctly, ... Halting problem: once you know that the halting problem of Turing ... Turing machine) cannot be solved using anything with no stronger power ...
    (sci.logic)
  • Re: Disproof of the Halting Problems Conclusion
    ... Peter> the program being analyzed. ... The halting problem for any type of machine capable of expressing ... machine that the Turing machine is capable of expressing. ... context of "Random Access Machine" (RAM), i.e., a machine similar to a ...
    (comp.theory)
  • Re: Disproof of the Halting Problems Conclusion
    ... Peter> the program being analyzed. ... The halting problem for any type of machine capable of expressing ... machine that the Turing machine is capable of expressing. ... context of "Random Access Machine" (RAM), i.e., a machine similar to a ...
    (sci.logic)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (sci.logic)