Re: Yet another Attempt at Disproving the Halting Problem
From: Owen Jacobson (angstrom_at_lionsanctuary.net)
Date: 07/31/04
- Next message: Craig Franck: "Re: Ethical Relativism (Cultural Differences Argument)"
- Previous message: Mitch Harris: "Re: Why should -1 multiplied by -1 be plus 1 and not -1"
- Maybe in reply to: Anonymous: "Re: Yet another Attempt at Disproving the Halting Problem"
- Next in thread: Peter Olcott: "Re: Yet another Attempt at Disproving the Halting Problem"
- Reply: Peter Olcott: "Re: Yet another Attempt at Disproving the Halting Problem"
- Messages sorted by: [ date ] [ thread ]
Date: Sat, 31 Jul 2004 19:28:53 GMT
On Sat, 31 Jul 2004 03:03:09 +0000, Peter Olcott wrote:
> "Howard" <alicebt@hotmail.com> wrote:
>>
>> A WillHalt algorithm that does not report its results is totally useless,
>> and determines exactly nothing.
>
> SEE RIGHT HERE IS ANOTHER EXAMPLE! I ONLY SAID NOT
> TO REPORT THE RESULT TO THE FUNCTION BEING ANALYZED,
> AND YOU LEAP TO THE STUPID CONCLUSION WITHOUT
> EVER PAYING ANY ATTENTION TO WHAT I AM SAYING!
> I HAVE POSTED EXACTLY WHAT I MEAN BY THIS FOR
> SEVERAL WEEKS. THE ADDRESS IS NOT HARD TO REMEMBER
> ITS WWW.HALTING-PROBLEM.COM HOW THE HELL DO
> YOU EXPECT TO REFUTE ME IF YOU DON'T EVEN KNOW
> WHAT I AM SAYING ???
No. What he is saying is that, in order to be of interest, a program
to determine if (program, input) pairs halt must leave the machine in a
state where it is possible to find out what that result was. In your
terms, "in order to be of interest the Halts(M, x) function must return a
value."
Quoth Peter Olcott @ <http://www.halting-problem.com/>[0]:
"A simple way to eliminate access to the return value of WillHalt() is
to simply not return this value to the caller."
Your proposed construction of Halt(M, x) is useless, as it does not
provide any information about whether the given (program, input) pair
halts. Furthermore, we *must* necessarily be able to take the steps
involved in Halts(M, x) and use them in another function, modifying it in
provably-correct ways to "return".
Halts(M, x) has no way of determining whether the input program is the
same as the "calling" program -- it merely determines if the given
program would halt on the given input.
Given this, it *must* be true that we can build arbitrary, valid programs
that "call" Halts(M, x) and operate on the "returned" value. Given this,
it *must* be possible to construct Turing's proof, which describes a
(program, input) pair that Halts(M, x) *cannot* correctly analyze.
[0] There's a bit of entertaining madness on Peter's "program trace", too:
**************************************************************
**************** Solved Halting Problem **********************
**************************************************************
void WillHalt(string SourceCode, string InputData)
{
if (TheProgramWillHalt(SourceCode, InputData))
^^^^^^^^^^^^^^^^^^
SecureOutput("The Program Will Halt");
...
The underlined function is Halts(M, x). The given "WillHalt" function is
NOT Halts(M, x), but rather a function constructed using Halts(M, x).
-- Some say the Wired doesn't have political borders like the real world, but there are far too many nonsense-spouting anarchists or idiots who think that pranks are a revolution.
- Next message: Craig Franck: "Re: Ethical Relativism (Cultural Differences Argument)"
- Previous message: Mitch Harris: "Re: Why should -1 multiplied by -1 be plus 1 and not -1"
- Maybe in reply to: Anonymous: "Re: Yet another Attempt at Disproving the Halting Problem"
- Next in thread: Peter Olcott: "Re: Yet another Attempt at Disproving the Halting Problem"
- Reply: Peter Olcott: "Re: Yet another Attempt at Disproving the Halting Problem"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
