Re: Attempt to Refute the Halting Problem's Refutation

• Previous message: Will Twentyman: "Re: Yet another Attempt at Disproving the Halting Problem"
• In reply to: Peter Olcott: "Re: Attempt to Refute the Halting Problem's Refutation"
• Next in thread: Peter Olcott: "Re: Attempt to Refute the Halting Problem's Refutation"
• Reply: Peter Olcott: "Re: Attempt to Refute the Halting Problem's Refutation"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Tue, 17 Aug 2004 13:19:32 GMT

In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>
> <newstome@comcast.net> wrote in message news:MyeUc.307761$JR4.122277@attbi_s54...
>> In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:

>> >> If your statement is that Turing proved that there is one specific
>> >> case that a halt analyzer will fail for, and you want to show that you
>> >> can get around one specific case, then I won't accept that since it
>> >> starts from a false premise.
>> >
>> > Try and show any difference of consequence, and you will either
>> > succeed or fail.
>>
>> Difference in what? You're certainly not claiming that there's no
>
> Try to show three different kinds of programs that can not be correctly
> processed by a halt analyzer. At this point I am estimating that you won't
> be able to do this. It might help you to know that all of my comments
> that are placed below one of your paragraphs are to be taken within the
> context of your paragraph.

I don't know what you mean by "kinds of programs" (you just love those
vague phrases), but I can certainly show you how any halt analyzer
which returns a value will fail on an infinite set of inputs:

To stick with earlier notation, but adding a number to denote
different functions, let's say you provide "WillHalt1(machine,input)"
and claim that it solves the halting problem (returning a value).
Then define (as has been done many times here):

   void LoopIfHalts1(machine,input) {
      if (WillHalt1(machine,input)) return;
      else while (1) ;
   }

Now obviously "WillHalt1(LoopIfHalts1,<LoopIfHalts1,LoopIfHalts1>)"
will get the wrong answer.

But wait! you say. If it gets the wrong answer in that case, then
let's just check for that one case and define:

   WillHalt2(machine,input) {
     if ((machine==LoopIfHalts1) && (input==<LoopIfHalts1,LoopIfHalts1>))
         return !WillHalt1(machine,input);
     else
         return WillHalt1(machine,input);
   }

This function now returns the correct value for the input we
identified as being incorrect for WillHalt1, and still returns the
same value in all those other correct cases.

But wait! I say. Now I'll write LoopIfHalts2 which uses WillHalt2 in
the same way that LoopIfHalts1 used WillHalt1. Now calling
WillHalt2(LoopIfHalts2,<LoopIfHalts2,LoopIfHalts2>) gets the wrong
answer. Notice that this means that
WillHalt1(LoopIfHalts2,<LoopIfHalts2,LoopIfHalts2>) also gets the
wrong answer.

Now you make WillHalt3 and I make LoopIfHalts3. You make WillHalt4
and LoopIfHalts4. This keeps going forever, making the longest
discussion thread in the history of comp.theory, and making Kent so
upset that he wets his pants.

But the point is that this is a "mechanical process" that can be
carried out indefinitely, and WillHalt1 will fail on ALL of the inputs
using LoopIfHalts1, LoopIfHalts2, LoopIfHalts3, LoopIfHalts4, etc.

Therefore, WillHalt1 (which was just an arbitrary program claiming to
solve the halting problem) will fail on an infinite set of inputs.

>> "difference of consequence" between a program that fails on a single
>> input versus one that fails on infinitely many inputs, are you? (Any
>> halt analyzer will fail on infinitely many inputs.)
>>
>> > In any case we can not proceed until you do this.
>>
>> No, if this is an irreconcilable difference, then we simply ignore it.
>
> I have disproven the one and only case where the halting problem
> has been shown to be impossible to solve. If you still think that
> there are infinitely many cases, then you must first provide three
> of these infinitely many before I am willing to proceed.

We can go either way you like. If you want me to show that any halt
analyzer which returns a value will fail on an infinite set of inputs,
see above. If you want to show that your idea of a halt analyzer
(that doesn't "return a value") fails from basic principles (without
reference to any statement about what Turing proved), then that's fine
too.

-- 
That's News To Me!
newstome@comcast.net

• Previous message: Will Twentyman: "Re: Yet another Attempt at Disproving the Halting Problem"
• In reply to: Peter Olcott: "Re: Attempt to Refute the Halting Problem's Refutation"
• Next in thread: Peter Olcott: "Re: Attempt to Refute the Halting Problem's Refutation"
• Reply: Peter Olcott: "Re: Attempt to Refute the Halting Problem's Refutation"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]