Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Subject | Re: Validating that a partial decider has made a correct decision on its input (V5) |
|---|---|
| Newsgroups | comp.theory |
| References | <8bCdnYKsMtn3_zDCnZ2dnUU7-TPNnZ2d@giganews.com> <JtWdnYkYppS4HzDCnZ2dnUU78V3NnZ2d@brightview.co.uk> <6bGdnY0cZNy-kDPCnZ2dnUU7-fXNnZ2d@giganews.com> <VOxrH.223635$BL.29254@fx16.iad> <Z6CdnVbxBphFLTPCnZ2dnUU7-cvNnZ2d@giganews.com> |
| From | Richard Damon <Richard@Damon-Family.org> |
| Message-ID | <eHyrH.110141$4d1.40470@fx09.iad> (permalink) |
| Organization | Forte - www.forteinc.com |
| Date | 2020-11-13 11:41 -0500 |
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!!!!!!
Your claim of 'but it needed to be aborted' is disproven by the
following (reordered to avoid forward references) and modified to TEST
the need to abort:
// Linz H with some of the ⊢* states shown
// Test parameter added to test the need to abort,
// if true will disable the abort
08 bool H(u32 P, u32 I, bool test) // Page 318
09 {
10 bool Halted = false;
11 bool Aborted = false;
12 while (!Halted && (test ||!Aborted))
13 {
14 Halted = DebugStep(P, I);
15 Aborted = Needs_To_Be_Aborted();
16 }
17 return !Aborted;
18 }
// Simplified Linz Ĥ (bottom of page 319)
01 void H_Hat(u32 P)
02 {
03 if (H(P, P, false)) // Add parameter to get old behavior
04 HERE: goto HERE;
05 else
06 HALT
07 }
19 int main()
20 {
21 H(H_Hat, H_Hat, false); // Get original answer
// Test if abort was needed (if it was this should not return)
H(H_Hat, H_Hat, true);
22 H_Hat(H_Hat);
23 }
You will note that with this very slightly modified version, that will
check if the abort that did occur was needed, we see that without that
abort, H will still complete, and return the answer now that
H_Hat(H_Hat) halts, which it does.
THUS, the H, as it was written by you is clearly flawed. Yes, we can't
just remove that abort, as then H does not terminate at all in this
case, thus failing to decide, this is NOT a proof that H_Hat has
infinite execution (non-halting behavior) but that H as designed doesn't
meet its requirements. This goes back the the fact that it is
classically known that emulation is NOT a good way to determine the
halting problem in general, it may work for many bounded problems, but
fails when we deal with unbounded problems (like this recursive situation)
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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