Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.theory
Subject: Re: Could H correctly decide that P never halts? [ already agreed ]
Date: Mon, 05 Jul 2021 03:14:03 +0100
Organization: A noiseless patient Spider
Lines: 73
Message-ID: <87fswtbj84.fsf@bsb.me.uk>
References: <hKudnUFx1oVw4n39nZ2dnUU7-aPNnZ2d@giganews.com> <87bl7jfjpa.fsf@bsb.me.uk> <INydnVdkv8OZCH39nZ2dnUU7-I_NnZ2d@giganews.com> <87im1rdu8s.fsf@bsb.me.uk> <mL-dnUBUU5d7SX39nZ2dnUU7-U_NnZ2d@giganews.com> <875yxrdj0o.fsf@bsb.me.uk> <yf2dnc-On5-7nHz9nZ2dnUU7-ffNnZ2d@giganews.com> <877di6c9ii.fsf@bsb.me.uk> <NrGdnXPuYcSG-n_9nZ2dnUU7-XednZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="70c6db9135c38e0959c01bebe7c472dd"; logging-data="2760"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18cIWjeuXhC7EsDTcvMjfFcFv2+NwJaWW8="
Cancel-Lock: sha1:ug2AL6d/SgEkXVCPaYOmS5JruvQ= sha1:fkAFAWYszQOg/677LUQ3HwB8Zyo=
X-BSB-Auth: 1.35270c81860f4636cc39.20210705031403BST.87fswtbj84.fsf@bsb.me.uk
Xref: csiph.com comp.theory:35714

olcott <NoOne@NoWhere.com> writes:

> On 7/4/2021 11:46 AM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> On 7/3/2021 7:23 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 7/3/2021 3:20 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 7/3/2021 11:25 AM, Ben Bacarisse wrote:
>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>>         void P(u32 x)
>>>>>>>>>         {
>>>>>>>>>           u32 Input_Halts = H(x, x);
>>>>>>>>>           if (Input_Halts)
>>>>>>>>>             HERE: goto HERE;
>>>>>>>>>         }
>>>>>>>> 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.
>>>>>>>
>>>>>>> Superficially it may seem that way until you realize (as you have
>>>>>>> already realized) that the halt criteria must be adapted for a
>>>>>>> simulating halt decider.
>>>>>>>
>>>>>> The two criteria I gave are for the halting problem.  No one is
>>>>>> interested in your "other kind of halting".  It seems you agree that H
>>>>>> is wrong about the input given above as far as the criterion of actual
>>>>>> halting goes.
>>>>>
>>>>> Because a simulating halt decider must always abort the simulation of
>>>>> every input that never halts its halt deciding criteria must be
>>>>> adapted.
>>>> If you "adapted" the criterion for being a prime number you could
>>>> "refute" many more theorems.
>>>
>>> You already agreed that this adaptation of the halt status criteria is
>>> correct:
>> A halting computation is one that halts.  There is no other criterion.
>> I can't believe this needs to be said.
>> 
>
> void Infinite_Loop()
> {
>   HERE: goto HERE;
> }
>
> int main()
> {
>   u32 Input_Would_Halt2 = H((u32)Infinite_Loop, (u32)Infinite_Loop);
>   Output("Input_Would_Halt2 = ", Input_Would_Halt2);
> }
>
> Then Infinite_Loop() is a halting computation on the basis that H
> aborts its simulation of Infinite_Loop().

I think you've lost the plot.  Infinite_Loop() is a not a halting
computation.  H(Infinite_Loop, Infinite_Loop) must halt if there is to
be a result, but Infinite_Loop(Infinite_Loop) (technically the
computation represented by the arguments to H) is not a halting
computation.

Your H(P,P) == 0 is wrong because P(P) halts.  There is only one
definition of halting and it is not your "adapted" one.

-- 
Ben.