Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #25240

Re: Validating that a partial decider has made a correct decision on its input (V5)

Subject Re: Validating that a partial decider has made a correct decision on its input (V5)
Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng
References (1 earlier) <JtWdnYkYppS4HzDCnZ2dnUU78V3NnZ2d@brightview.co.uk> <6bGdnY0cZNy-kDPCnZ2dnUU7-fXNnZ2d@giganews.com> <VOxrH.223635$BL.29254@fx16.iad> <Z6CdnVbxBphFLTPCnZ2dnUU7-cvNnZ2d@giganews.com> <eHyrH.110141$4d1.40470@fx09.iad>
From olcott <NoOne@NoWhere.com>
Date 2020-11-13 10:43 -0600
Message-ID <xsKdnfXzZrpfKjPCnZ2dnUU7-R2dnZ2d@giganews.com> (permalink)

Cross-posted to 3 groups.

Show all headers | View raw


On 11/13/2020 10:41 AM, Richard Damon wrote:
> On 11/13/20 11:14 AM, olcott wrote:
>> On 11/13/2020 9:41 AM, Richard Damon wrote:
>>> On 11/12/20 11:35 PM, olcott wrote:
>>>>
>>>> All black cats are black.
>>>>
>>>> When-so-ever the UTM halt decider H decides that
>>>> its input (<P>,I) would never terminate unless H stopped simulating it
>>>> and
>>>> its input (<P>,I) would never terminate unless H stopped simulating it
>>>>
>>>> then this decision by this decider is true by logical necessity.
>>>
>>> Except that it HAS been shown that for cases where your decider has said
>>> that its input would not stop, that if you remove the stop condition
>>> from the decider (but leave the program under test unchanged, its tests
>>> do not change) that the UTM will come to a halt.
>>
>>
>> // Simplified Linz Ĥ (bottom of page 319)
>> 01 void H_Hat(u32 P)
>> 02 {
>> 03   if (H(P, P))
>> 04     HERE: goto HERE;
>> 05   else
>> 06     HALT
>> 07 }
>>
>> // Linz H with some of the ⊢* states shown
>> 08 bool H(u32 P, u32 I)  // Page 318
>> 09 {
>> 10   bool Halted  = false;
>> 11   bool Aborted = false;
>> 12   while (!Halted && !Aborted)
>> 13   {
>> 14     Halted  = DebugStep(P, I);
>> 15     Aborted = Needs_To_Be_Aborted();
>> 16   }
>> 17   return !Aborted;
>> 18 }
>>
>> 19 int main()
>> 20 {
>> 21   H(H_Hat, H_Hat);
>> 22   H_Hat(H_Hat);
>> 23 }
>>
>> That you are trying to get away with double-talk is made obvious by the
>> fact that lines 21 and 22 never halt when line 15 is removed from H.
>>
> 
> Yes, run that, H will say (from your definitions) that H_Hat(H_Hat) will
> have non-halting behavior, but then you run H_Hat(H_Hat) and it halts,
> so H was WRONG!!!!!!
> 
When we remove line 15 all of the inputs that would have been decided to 
be not halting prove that they are indeed not halting by the fact that 
they fail to ever halt when line 15 is removed.


-- 
Copyright 2020 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

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


Thread

Validating that a partial decider has made a correct decision on its input (V3) olcott <NoOne@NoWhere.com> - 2020-11-12 10:27 -0600
  Re: Validating that a partial decider has made a correct decision on its input (V3) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-12 18:42 +0000
    Re: Validating that a partial decider has made a correct decision on its input (V5) olcott <NoOne@NoWhere.com> - 2020-11-12 22:35 -0600
      Re: Validating that a partial decider has made a correct decision on its input (V5) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-13 15:25 +0000
        Re: Validating that a partial decider has made a correct decision on its input (V5) olcott <NoOne@NoWhere.com> - 2020-11-13 09:32 -0600
      Re: Validating that a partial decider has made a correct decision on its input (V5) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 10:41 -0500
        Re: Validating that a partial decider has made a correct decision on its input (V5) olcott <NoOne@NoWhere.com> - 2020-11-13 10:14 -0600
          Re: Validating that a partial decider has made a correct decision on its input (V5) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 11:41 -0500
            Re: Validating that a partial decider has made a correct decision on its input (V5) olcott <NoOne@NoWhere.com> - 2020-11-13 10:43 -0600
              Re: Validating that a partial decider has made a correct decision on its input (V5) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 14:00 -0500
                Re: Validating that a partial decider has made a correct decision on its input (V5) olcott <NoOne@NoWhere.com> - 2020-11-13 13:11 -0600
                Re: Validating that a partial decider has made a correct decision on its input (V5) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 15:17 -0500

csiph-web