Re: Could H correctly decide that P never halts? [ already agreed ]

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.theory
Subject	Re: Could H correctly decide that P never halts? [ already agreed ]
Date	2021-07-06 13:23 +0100
Organization	A noiseless patient Spider
Message-ID	<871r8baawn.fsf@bsb.me.uk> (permalink)
References	(10 earlier) <bJCdnQAh7eLG83_9nZ2dnUU7-cfNnZ2d@giganews.com> <87tul89xms.fsf@bsb.me.uk> <v7KdnXhXO_0xNH79nZ2dnUU7-KvNnZ2d@giganews.com> <87czrw9nku.fsf@bsb.me.uk> <NI-dnRbkTs3YU379nZ2dnUU7-bXNnZ2d@giganews.com>

Show all headers | View raw

olcott <NoOne@NoWhere.com> writes:

> On 7/5/2021 9:35 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> On 7/5/2021 5:58 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>> |    void P(u32 x)
>>>> |    {
>>>> |      u32 Input_Halts = H(x, x);
>>>> |      if (Input_Halts)
>>>> |	 HERE: goto HERE;
>>>> |    }
>>>>
>>>>> Every computation that would never halt unless its simulation is
>>>>> aborted is equally not a halting computation.
>>>>
>>>> For H(P,P) to be correct one of these must apply:
>>>>          H(P,P) == 0 and P(P) does not halt, or
>>>>          H(P,P) != 0 and P(P) halts.
>>>> Neither is the case.  Simple facts that you deny.

> H(P,P) == 0 is axiomatically correct thus impossibly incorrect.

H(P,P) == 0 may well be the correct POOH answer.  Since you get to
define the PO "Other-Halting" problem, you get to state what the correct
answers are.  In that sense it's axiomatic.  My only objection can be
that no one cares about the POOH problem.

H is clearly not computing the halting function as it returns 0 for a
halting computation.  You don't get to "adjust" (as you so
euphemistically say) the definition of halting.

> Once you understand that H(P,P) == 0 is axiomatically correct thus
> impossibly incorrect, then you see that the fact that P(P) halts
> cannot possibly be a contradiction.

I have never challenged your right to define a new decision problem.
What the correct answers are is then entirely up to you, and though I'd
call them definitions rather than axioms they can only be challenged as
being silly or not interesting (and they are both).

> The view that H(P,P) == 0 is not correct requires the view that in
> some cases where UTM(P,I) never halts P(I) does halt.

UTM(P,P) halts because P(P) halts.

> Because we can see that the execution trace of P on input P...

... halts, we know that H is not a halt decider because it is wrong
about the P(P) case.  H may well be a POOH decider.  You get to define
what the right answers are for a POOH decider.

-- 
Ben.

Thread

csiph-web