Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2)

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.theory
Subject	Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2)
Date	2021-07-21 01:28 +0100
Organization	A noiseless patient Spider
Message-ID	<87pmvcldbo.fsf@bsb.me.uk> (permalink)
References	<aoGdnZthSvke2279nZ2dnUU7-KnNnZ2d@giganews.com> <8735scl50x.fsf@bsb.me.uk> <K-6dneCZO-mkDGj9nZ2dnUU7-Y-dnZ2d@giganews.com> <87a6mhizzg.fsf@bsb.me.uk> <CPidnZCdsdkERGv9nZ2dnUU7-IXNnZ2d@giganews.com>

Show all headers | View raw

olcott <NoOne@NoWhere.com> writes:

> On 7/19/2021 7:35 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> void P(u32 x)
>>> {
>>>    if (H(x, x))
>>>      HERE: goto HERE;
>>> }
>>>
>>> int main()
>>> {
>>>    P((u32)P);
>>> }
>>>
>>> The fact is that the above computation never ever halts unless...
>> The fact is that P(P) halts (according to you).  H(P,P) == 0 (according
>> to you).  That is wrong.  You know it's wrong:
>> Me: Every computation that halts, for whatever reason, is a halting
>>      computation.
>> You: OK
>
> The halt decider is only required to correctly decide the halt status
> of its input.

H(P, I) is required to correctly determine whether P(I) halts or not.
P(P) halts (according to you).  H(P, P) == 0 (according to you).  That
is wrong.

> Anyone the knows the x86 language well enough
> (apparently not you) can see that the code of P provides no escape
> from its infinitely nested simulation.

You don't dispute about the two key facts (because they come from you):
P(P) halts and H(P, P) == 0.  Waffle all you like, but unless you
retract one or both of these, then H is wrong about the one case you
care about.

> Simulating partial halt decider H correctly decides that P(P) never
> halts

P(P) halts (according to you).  H incorrectly decides it does not.

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Simulating halt decider H correctly decides halt status of pathological inputs (V2) olcott <NoOne@NoWhere.com> - 2021-07-17 16:07 -0500
  Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-18 03:39 +0100
    Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) olcott <NoOne@NoWhere.com> - 2021-07-19 09:50 -0500
      Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 01:35 +0100
        Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) olcott <NoOne@NoWhere.com> - 2021-07-20 09:11 -0500
          Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 11:32 -0700
          Re: Simulating halt decider H correctly decides halt status of pathological inputs (V2) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-21 01:28 +0100

csiph-web