Disproof of the Halting Problem's Conclusion
From: Peter Olcott (olcott_at_att.net)
Date: 07/14/04
- Next message: Peter Olcott: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- Previous message: Kent Paul Dolan: "Re: Groupthink"
- Next in thread: Will Twentyman: "Re: Disproof of the Halting Problem's Conclusion"
- Reply: Will Twentyman: "Re: Disproof of the Halting Problem's Conclusion"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 13 Jul 2004 23:31:58 GMT
Most recently updated version of this informal proof will be posted on this
link:
http://home.att.net/~olcott/halts.html
The goal of this proof is to refute the Halting Problem's conclusion:
(paraphrase)
{It is impossible to construct a program that can determine if every program
halts.}
This informal proof depends upon the terminology of this link
http://www.netaxs.com/people/nerp/automata/halting2.html
to be understood.
This version of the Halting Problem is supposed to be analogous to every
other version, thus valid refutations of this version should equally apply
(with adaptation) to all other versions.
Process:
A running program in memory.
Static Program:
ASCII text that represents the source code of the program that can be edited
and compiled.
Assumptions:
(1) No process has any access to read the screen data.
(2) The WillHalt() process is located in protected memory, and any access to
this memory by other processes causes a memory protection fault error.
Body Of Proof
The basis of the original proof is a mechanism comparable to the
LoopIfHalts() function. If this basis could be disabled, then the original
proof would lose its basis, and fail.
The LoopIfHalts() function depends upon access to the return value of the
WillHalt() function. If every possible access to this return is completely
denied to every other program, then LoopIfHalts() can not possibly effect
the WillHalt() function. LoopIfHalts() would be unable to "loop if halts".
Simple Method
A simple way to eliminate access to the return value of WillHalt() is to
only put this return value on the screen, (and nowhere else) and not allow
any process read access to the screen data. This would of course also
require that the WillHalt() function not return a value to its caller.
Possible Bases For Refutation
It seems that the only possible way to refute this proof would have to take
the form of preventing my unmodified version of WillHalt() from working
correctly. Any changes made to the WillHalt() function will probably prove
fruitless for the following reasons:
Halting can be determined by my original unmodified version of Willhalt()
for every program, including those based on WillHalt(). The LoopIfHalts()
function is now bound to fail because WillHalt() does not return the boolean
value that it requires. Although changes can be make to WillHalt() such that
it can no longer determine if a program (including itself) will halt, my
original unmodified version would be able to correctly make this
determination for these programs.
- Next message: Peter Olcott: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- Previous message: Kent Paul Dolan: "Re: Groupthink"
- Next in thread: Will Twentyman: "Re: Disproof of the Halting Problem's Conclusion"
- Reply: Will Twentyman: "Re: Disproof of the Halting Problem's Conclusion"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
