Re: Disproof of the Halting Problem's Conclusion

From: No Way (Not_at_real.com)
Date: 07/18/04 

Date: Sun, 18 Jul 2004 10:37:01 +0200

On Sat, 17 Jul 2004 18:29:33 GMT, "Peter Olcott"
<olcott@worldnet.att.net> wrote:

>http://home.att.net/~olcott/halting/index.html#objection02

It says: "The possibility of creating one or more instances of
WillHalt() that permit LoopIfHalts() to function does not refute this
method."

But it does. Your method is founded on the idea that LoopIfHalts
cannot be constructed. As soon as it is shown that that is possible,
your method breaks down.

"In other words defeating the security in less than every possible
case does not prove that this method does not work."

And you think the security wasn't broken in less than every possible
case? With any version of WillHalt you can come up with, I can come up
with a version of a LoopIfHalts (and thus a version of
LoopIfHaltsOnItself and thus a version of Impossible).

"One single case where the security is not circumvented proves that
the idea still works."

?

>> Since the code that determines what WillHalt will output on the input
>> is the same in both programs, the outcome of that piece of code will
>> be the same in both programs (if it weren't the piece of code wouldn't
>> do what it is supposed to do).
>
>http://home.att.net/~olcott/halting/example.html
>That is not true examine this page closely, and see for yourself.

First of all, why does the WillHalt function (in the 'original')
contain an 'unknown' option? That WillHalt should be like this:

bool WillHalt(string SourceCode, string InputData)
{
  if (TheProgramWillHalt(SourceCode, InputData))
    return TRUE;
  else
    return FALSE;
}
 
Secondly, in your new WillHalt system, why won't I be able to build
the following?

void LoopIfHalts(string SourceCode, string InputData)
{
  if (TheProgramWillHalt(SourceCode, InputData))
    while (TRUE);
  else
     return
}

BTW I'm beginning to wonder whether you even understood the basis of
the halting problem proof. You do understand what the outline of the
proof is, right?

* The existence of a WillHalt program (a program that correctly
predicts whether the input program halts or not on a certain input)
implies the existence of a LoopIfHalts program (a program that goes
into a loop if WillHalt would predict that the input program would
halt).
* The existence of a LoopIfHalts program implies the existence of a
LoopIfHaltsOnItself program.
* LoopIfHaltsOnItself cannot work properly because it will be unable
to work properly on itself (If LoopIfHaltsOnItself would halt, it
would have to go into a loop and vice versa).
* So LoopIfHaltOnItself cannot exist.
* Since the existence of LoopIfHalts implies the existence of
LoopIfHaltsOnItself, LoopIfHalts cannot exist.
* Since the existence of Willhalt implies the existence of
LoopIfHalt,Willhalt cannot exist either.

What you are trying to do, is find a way around the first step. You
want to make the existence of LoopIfHalts impossible. You try to do
this by adding a rule to the system. However by adding that rule, the
problem is no longer the 'halting problem'.

>> Which is rather interesting, because Turing Machines don't use
>> functions at all. If you think your situation is equivalent to the TM
>> situation, it must be possible to avoid functions.
>
>http://home.att.net/~olcott/halting/index.html#objection01
>See this link to see why any mention of Turing Machines
>is made moot.

You just saying that doesn't make it true. If your 'proof' is a way to
show that the conclusion of 'the halting problem' is incorrect in
general, it should also be able to be applied to Turing Machines.

>If it is a given that I can make access to the results of WillHalt()
>impossible for any specific program to access, then I have
>disproved the Halting Problem.

No, you will have changed the problem to something else by adding a
rule (No program is allowed to exist that disproves that WillHalt can
exist).

>The fact that you can decompile
>my method any make one instance of it no longer function does
>not in any way refute the general case.
> You would have to make
>every possible instance of my WillHalt() simultaneously not function
>in order to correctly refute my proof.

Why would I have to do that?

>> Explain to me why the decompile/recompile trick doesn't always work?
>I just did.

No, you didn't.

Relevant Pages