Re: Attempt to Refute the Halting Problem's Refutation

newstome_at_comcast.net
Date: 08/24/04 

Date: Tue, 24 Aug 2004 00:19:19 GMT

In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>
> <newstome@comcast.net> wrote in message news:NEqWc.171014$8_6.146612@attbi_s04...
>> 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.
>
> This looks like a ploy that someone that doesn't know the answer
> would try to bluff with.
>
> *** NOTE *** I did not cut his reply, he did not make a reply.
> He said There you go -- three counterexamples, and that's all
> that he said. Click on the message header at the top of this
> message to see his original message.

Yes indeed. That's exactly what I said, and it answered your question
quite fully. The process for creating the infinite family of inputs
on which any halt analyzer will fail is given in a previous posting,
with message-id <EBnUc.311306$JR4.214408@attbi_s54>. Now you only
want three counterexamples, so just use the first three that this
gives. In what way does that not precisely meet your challenge of
providing three different inputs on which any halt analyzer will fail?

>> >> 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"???
>
> Any one of three of my methods make this not true.
> www.halting-problem.com
>
>> >> 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."
>
> Whether or not it is more powerful that a Turing Machine ignores
> the fact that Undecidability has been correctly refuted. It does not
> challenge this fact, it merely changes the subject.

Wrong. If you can solve the halting problem with such a model, it
would clearly be *more* power than a Turing machine, since a Turing
machine can *NOT* solve the halting problem. I can show you very
directly that no solution using your "write-only output" model can
solve the halting problem. But you don't seem interested in that, and
would rather spout nonsense about how "undeciability has been
correctly refuted."

>> 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,
>
> Since this model can be fully contructed using nothing more than a
> conventional TM you are wrong that it does not apply to this model.

Ah, then you're agreeing that the halting problem can't be solved in
this model, and you see that you were wrong earlier. Great. We're
making progress.

>> 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."
>
> Whether or not it is more powerful that a Turing Machine ignores
> the fact that Undecidability has been correctly refuted. It does not
> challenge this fact, it merely changes the subject.

Wrong again. Nothing has been refuted.

>> ----
>>
>> 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.
>
> I specifically asked you to try to prove this point and the best that
> you did was bluff.

No, I answered completely and precisely.

>> ----
>>
>> 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.
>
> I will not proceed one micro step further until you specifically provide
> three cases that are explicitly numbered of the infinite set that you keep
> referring to but failing to validate.

Been done. Not going back there. If you provide a WillHalt function
that you claim solves the halting problem, it will *fail* on inputs
LoopIfHalts1, LoopIfHalts2, and LoopIfHalts3 -- three different
inputs. I have no idea what "failing to validate" means here. WillHalt
will fail on all these inputs because of the way they are
constructed. It's a very straight-forward contradiction, so there's
nothing to "validate."

>> 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*.
>
> That is merely false presumption.

No, it's something that's been *proved*. That makes it a correct
theorem, not a presumption.

> If you would have said forall TMs
> that must always return a value you might be closer.

Actually, that's what I did say. I said "TMs which return a value",
which means they always return a value (for every input).

> You still would
> not be there though, because this value can be encoded with a private
> key.

Actually, it makes no difference at all if it's encoded with a private
key or not. But the way standard TMs are required to present their
result it is not "encoded with a private key." But if it makes you
feel better we'll change it to

forall "TMs which always return a value for every input, that value
being 1 or 0 for halts and doesn't halt" there exists "an input <m,x>"
such that the TM does not correctly answer the halting problem for
input <m,x>

It was clear precisely what it meant the first time, and I have no
need to throw in extra language just for the hell of it. I'm sure
everyone else but you knew precisely what I meant too, but don't let
that get in the way of going off on irrelevant tangents.

> So then you would have to say forall TM's that always provide
> and value, that is not encoded with a private key... Thus your forall
> is becoming a whole lot less than forall TMs.

And again, it doesn't matter if the result is "encoded with a private
key" or "written to a write-only output" or "only provided if the halt
analyzer is run by itself." *NONE* of that matters because in *NONE*
of those models is the halting problem solvable. If you could settle
on a single model and not keep changing your claims, we could
establish this. 

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

Relevant Pages