Re: Solution to the halting Problem?
From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 07/23/04
- Next message: David Hilsee: "Re: Solution to the halting Problem?"
- Previous message: Shailesh Humbad: "simple memory question"
- In reply to: David Hilsee: "Re: Solution to the halting Problem?"
- Next in thread: David Hilsee: "Re: Solution to the halting Problem?"
- Reply: David Hilsee: "Re: Solution to the halting Problem?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Fri, 23 Jul 2004 00:01:06 GMT
"David Hilsee" <davidhilseenews@yahoo.com> wrote in message news:s8ydnRxVJq220p3cRVn-vA@comcast.com...
> "Peter Olcott" <olcott@worldnet.att.net> wrote in message
> news:ynXLc.305496$Gx4.283037@bgtnsc04-news.ops.worldnet.att.net...
>
> > > You already said that it does not work for a specific instance, so it
> does
> >
> > It works for all inputs. It does not work in all instances such as
> destroying
> > the machine that is is running on.
>
> I think I get what you're saying now. That paragraph (which has now changed
> to provide better wording) claiming that one can make a LoopIfHalts that
> fails is not about creating new input source, it is about modifying (on the
> page, it is referred to as "corrupting") the example so it no longer works.
> Originally, it sounded like the claim was that a modified version of the
> source you provided is somehow invalid input and can be ignored.
All syntactically correct programs are valid input.
In theory I could also include syntactically incorrect
programs, and then output compiler error messages.
> For example, I thought you were saying that the following program "doesn't
> count."
>
> // Some source taken from http://www.cgl.uwaterloo.ca/~csk/halt/
>
> int WillHaltWithReturnValue(string SourceCode, string InputData) {
> if (TheProgramWillHalt(SourceCode, InputData))
> return TRUE;
> else if (TheProgramWillNotHalt(SourceCode, InputData))
> return FALSE;
> else
> return UNKNOWN;
> }
>
> bool stops_on_self( char * program ) {
> return WillHaltWithReturnValue( program, program ) == TRUE;
> }
>
> bool bobs_yer_uncle( char * program ) {
> if( stops_on_self( program ) ) {
> while( 1 ) {}
> return false;
> } else {
> return false;
> }
> }
>
> Now you can apply the same reasoning from the link I provided to show that
> your program does not work for this case, because the new
> WillHaltWithReturnValue function does the same exact thing that your
> WillHalt() does except it returns the conclusion. If
Nope. Its not like that. My void WillHalt() does determine that the
above sequence of programs will halt. The corrupted version can't
determine whether or not the above sequence will halt, but my
version can always make this determination correctly.
My void WillHalt() is not locked into the double-bind as the
corrupted version is. My version can determine that the corrupted
version will halt, and not have this used to negate the result.
> WillHaltWithReturnValue() can be proven to not work (and it can, as shown in
> the link I provided), then that means that WillHalt() does not work because
> the modifications made do not affect the conclusion that the function
> reaches. This code was partially inspired by tom_usenet's comment that
This is the tricky part. It actually does modify the conclusion that it
reaches. If everything else is the same, except in one case you return
the result to the caller, and in the other case you do not return the result
to the caller, the result differs. The reason that the result differs is that
in one case the result is fed back to the program that you are analyzing,
and in the other case this result is not fed back. This changes the way that
the analyzed program behaves, thus chaning the result of your analysis.
> "*If* a solution to the halting problem exists, *then* it *must* be possible
> to write WillHalt such that it returns to a caller whether the passed
> program halts or not."
No sorry that is merely a false statement.
> Throughout the discussion, I thought you had already
> considered the above source as an input, but for some reason you were
> refusing to accept it as valid. Tom's comment triggered a thought that this
> might not be the case, so I decided to explain his statement in more detail.
>
> --
> David Hilsee
>
>
- Next message: David Hilsee: "Re: Solution to the halting Problem?"
- Previous message: Shailesh Humbad: "simple memory question"
- In reply to: David Hilsee: "Re: Solution to the halting Problem?"
- Next in thread: David Hilsee: "Re: Solution to the halting Problem?"
- Reply: David Hilsee: "Re: Solution to the halting Problem?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
