Re: Attempt to Refute the Halting Problem's Refutation

newstome_at_comcast.net
Date: 08/23/04 

Date: Mon, 23 Aug 2004 18:25:49 GMT

In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
> <newstome@comcast.net> wrote in message news:y17Wc.69114$TI1.60353@attbi_s52...
>> In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>
>> > I asked you to provide three examples that differ in substantial ways.
>> > I have not yet seen three cases that differ in substantial ways.
>> > If you already provided three cases that differ in substantial
>> > ways, then please provide the link to this message. Otherwise
>> > you still must provide three examples that differ in substantial
>> > ways. Examples that differ in trivial ways DO NOT COUNT!
>>
>> I did better than that. I described a technique by which you could
>> take any halt analyzer and construct an *INFINITE* family of inputs on
>
> That is not what I asked for. Three is much more comprehensible
> than infinity. Please provide me three if you can or admit that you
> can't. Providing infinity does not count as providing three.

OK, then start the process of generating the infinite family of
counterexamples, and stop after three. There you go -- three
counterexamples.

>> which any given halt analyzer will fail. Not three. Infinite. But
>> you obviously didn't understand that the first time, and I'm not
>> expecting you to now.
>>
>> Let's try this. I'm going to give you an exercise to try. Please
>> read all the way through it and try to understand it, and don't just
>> give a knee-jerk reaction after the first sentence or two. If you can
>> truly understand what this exercise asks you to understand, you'll at
>> least be a little closer to realizing why you've been barking up the
>> wrong tree all this time. I'm going to give you an argument that
>> looks at first glance like it's valid, but if you really think about
>> it you'll see why it's wrong. My challenge to you is to wrap your
>> head around this well enough to understand why this is wrong.
>>
>> OK, first, a reminder of the standard contradiction. Nothing new here
>> except "setting the stage". You've got WillHalt(machine,input), and
>> claim that it solves the halting problem. I construct
>>
>> void LoopIfHalts(machine) {
>> if (WillHalt(machine, machine))
>> while (true) ; // Loops forever
>> // Otherwise returns (i.e., halts)
>> }
>>
>> Now obviously WillHalt(LoopIfHalts, LoopIfHalts) gives the wrong
>> answer, so WillHalt does not work for all inputs. This is the classic
>> contradiction.
>
> Not true.

Excuse me????? How is this "not true"???

>> But wait, since that just constructs a contradiction using the
>> LoopIfHalts, I'll modify WillHalt to first see if the input machine
>> that it's analyzing is of this form. So you write a boolean function
>> bool isLoopIfHaltsForm(machine) -- you can certainly test if something
>> has been added of the form above. Now you create a function, which
>> we'll call WillHalt2 that looks something like this:
>>
>> bool WillHalt2(machine, input) {
>> if (isLoopIfHaltsForm(machine))
>> return ! WillHalt(machine, input);
>> else
>> return WillHalt(machine, input);
>> }
>>
>> So I've added a test to see if it's the "kind" of TM that I used to
>> trick the earlier WillHalt, and then negate the answer so that it will
>> be correct this time. So I've fixed that one bad case, right?
>>
>> Well consider this:
>>
>> void LoopIfHalts2(machine) {
>> if (WillHalt2(machine, machine))
>> while (true) ; // Loops forever
>> // Otherwise returns (i.e., halts)
>> }
>>
>> This is exactly the "bad form" that I'm testing for in WillHalt2, and
>> it is indeed detected properly by isLoopIfHaltsForm(machine), so now
>> I've "fixed" the result so that this will no longer fool us, right?
>>
>> Wrong. WillHalt2(LoopIfHalts2, LoopIfHalts2) *STILL* gets the wrong
>> answer.
>>
>> Do you follow this? Do you understand why this technique (testing if
>> a TM is of a certain bad "kind" and trying to fix the function based
>> on that) will *NEVER* work?
>
> It does not matter whether I accept this or not. I circumvented this
> whole line-of-reasoning for exactly these sorts of reasons. I already
> knew that trying to specifically identify exact cases such as LoopIfHalts
> might possibly be problematic, so I circumvented this whole scenario.

Well we started down this line of reasoning, and you wouldn't complete
it. You changed your terminology to talking about "the case" that the
Halting problem wouldn't work for.

> If I simply know for sure that zero functions of any possible kind have
> called Halt, then I can know with complete certainty that no functions
> such as LoopIfHalts have called Halt.

Yep -- and if you require "Halt" to return an answer this *still*
doesn't work. The argument is the same as above, which is why I
challenged you to try to understand that. If you change to a model in
which "Halt" can express its answer in a non-conventional way, then
it's a more interesting question, but you cut off this line of
argument when I tried to make it. Here are three distinct arguments
you've made, and I'll go ahead and put my answer to each one -- if you
want to pursue any of these any more, let me know: 

----
Peter's Argument Number 1:  Turing's proof only works for halt
analyzers that are required to return an answer in a way that can be
used by another function, so we'll simply have the halt analyzer
output to a write-only output.
My Answer:  Interesting claim, and the original proof doesn't apply to
this model, but it's also not very difficult to prove that this model
is no more powerful than the original model in which the halt analyzer
must always return its answer.  I could easily show you this, but you
cut off this argument and decided that you'd rather move on to
"Peter's Argument Number 2."
----
Peter's Argument Number 2:  Turing's proof only works for halt
analyzers that are required to return an answer in a way that can be
used by another function, so we'll simply have the halt analyzer
run on a modified UTM that will tell the halt analyzer whether it is
running alone or not.
My Answer:  Interesting claim, and the original proof doesn't apply to
this model, but it's also not very difficult to prove that this model
is no more powerful than the original model in which the halt analyzer
must always return its answer.  I could easily show you this, but you
cut off this argument and decided that you'd rather move on to
"Peter's Argument Number 3."
----
Peter's Argument Number 3: "I have correctly refuted the one case that
defined the undecidability of the Halting Problem."
My Answer:  I put that in quotes so that I could use your own words.
I have no idea how to paraphrase it, since on the face of it the
statement is simply nonsense.  There is *NO* "one case that defined the
undecidability of the Halting Problem."  To say that simply shows that
you have a fundamental misunderstanding of that proof.  From this
standpoint I can't give an immediate rebutal to what you say, because
you haven't said something coherent enough to rebut.  I could try to
explain the existing proof to you, but as you've apparently blithely
dismissed the challenge I gave you in the previous posting, I have
little hope that you'd make any progress on this.
----
So there you have it -- the evolving world of Peter Olcott.  If you
want to work on arguments number 1 or 2, I'm game.  If you want to
stick to "argument number 3", then you'll have to actually make a
coherent and sensible statement.  The first step would be to
completely banish the nonsense about "one case", as that's completely
and totally bogus.  One last try to explain that to you:  here's what
the proof of the halting problem shows, logically:
forall "TMs which return a value" there exists "an input <m,x>" such that
the TM does not correctly answer the halting problem for input <m,x>
It's a for *ALL*.  Not a "for all except those which can inspect their
own programs".  It's not a "for this one type of TM".  It's not even
"for all except those that Peter Olcott designs".  For *ALL* even
includes you in the impossiblity.
-- 
That's News To Me!
newstome@comcast.net

Relevant Pages

  • Re: What is the Result from Invoking this Halt Function?
    ... > Peter Olcott wrote: ... >> It looks like the error is in its application to the Halting Problem. ... analyzer that always returns a correct result back to the program being ... constructing a halt analyzer that works correctly for all input is impossible. ...
    (comp.theory)
  • Re: What is the Result from Invoking this Halt Function?
    ... > Peter Olcott wrote: ... >> It looks like the error is in its application to the Halting Problem. ... analyzer that always returns a correct result back to the program being ... constructing a halt analyzer that works correctly for all input is impossible. ...
    (sci.logic)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... providing three different inputs on which any halt analyzer will fail? ... If you can solve the halting problem with such a model, ... it makes no difference at all if it's encoded with a private ... But the way standard TMs are required to present their ...
    (comp.theory)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... providing three different inputs on which any halt analyzer will fail? ... If you can solve the halting problem with such a model, ... it makes no difference at all if it's encoded with a private ... But the way standard TMs are required to present their ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... >> done by reduction ad absurdum rather than actual ... produce a halt analyzer that returns a correct ... The problem of construction of a Halting Problem ...
    (comp.theory)