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


Groups > comp.theory > #25212

Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts)

From André G. Isaak <agisaak@gm.invalid>
Newsgroups comp.theory
Subject Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts)
Date 2020-11-13 01:22 -0700
Organization Christians and Atheists United Against Creeping Agnosticism
Message-ID <rolfok$l7u$1@dont-email.me> (permalink)
References (8 earlier) <1PadnXhiTNMWzzDCnZ2dnUU7-Q_NnZ2d@giganews.com> <rojs1q$rb2$1@dont-email.me> <6sKdnbsZcO6i4DDCnZ2dnUU7-b3NnZ2d@giganews.com> <rok18h$4lb$1@dont-email.me> <gZqdncfvF40HkjPCnZ2dnUU7-U_NnZ2d@giganews.com>

Show all headers | View raw


On 2020-11-12 21:46, olcott wrote:
> On 11/12/2020 1:09 PM, André G. Isaak wrote:
>> On 2020-11-12 11:21, olcott wrote:
>>> On 11/12/2020 11:40 AM, André G. Isaak wrote:
>>
>> <snippage>
>>
>>>> The following is a modified version of your code. As I stated, the 
>>>> only difference between this code and yours is that in this version 
>>>> the uppermost call to H *and only the uppermost call* to H has its 
>>>> abort code disabled.
>>>>
>>>> According to you, H, when called with (H_Hat, H_Hat) as its input 
>>>> *must* abort its input to prevent it from running forever, but the 
>>>> following does *not* run forever despite the fact that the uppermost 
>>>> H cannot abort its input.
>>>>
>>>> So your claim that this "computation would never halt unless the 
>>>> halt decider forces it to halt" is a "verified fact" is simply 
>>>> false. It is not a fact at all.
>>>>
>>>> int main()
>>>> {
>>>>    H(H_Hat, H_Hat, false);  // **** ADDED PARAMETER ****
>>>> }
>>>>
>>>> // Simplified version of Linz H_Hat DOES NOT copy itself
>>>> 01 void H_Hat(u32 P)  // (bottom of page 319)
>>>> 02 {
>>>> 03   if (H(P, P, true))  // **** ADDED PARAMETER ****
>>>> 04     HERE: goto HERE;
>>>> 05   else
>>>> 06     HALT
>>>> 07 }
>>>>
>>>> // Linz H with some of the ⊢* states shown
>>>> 08 bool H(u32 P, u32 I, bool UseAbortCode) // ** CHANGED LINE **
>>>> 09 {
>>>> 10   bool Halted  = false;
>>>> 11   bool Aborted = false;
>>>> 12   while (!Halted && !Aborted)
>>>> 13   {
>>>> 14     Halted  = DebugStep(P, I);
>>>> 14.5   if UseAbortCode // ***** ADDED LINE *****
>>>> 15         Aborted = Needs_To_Be_Aborted();
>>>> 16   }
>>>> 17   return !Aborted;
>>>> 18 }
>>>>
>>>> André
>>>>
>>>
>>> I am not completely certain exactly what that execution trace would do.
>>
>> Well, since it's a trivial modification of your own code, tracing 
>> shouldn't be too difficult.
>>
>> H emulates H_Hat(H_Hat), but with its abort code disabled so it cannot 
>> abort H_Hat(H_Hat).
>>
>> The outer H_Hat calls H again to emulate the Inner H_Hat.
>>
>> The H called by H_Hat aborts the inner H_Hat.
>>
>> That H then returns control to the outer H_Hat which terminates.
>>
>> Control returns to the uppermost H which then also terminates.
>>
>> The point is that H_Hat(H_Hat) *will* terminate on its own. Your claim 
>> that the uppermost H *had* to terminate H_Hat(H_Hat) is simply false. 
>> If your outermost H does not terminate it, it will not go into 
>> infinite execution; it will halt.
>>
>>> I am completely certain that unless one of the H_Hat invocations in 
>>> the otherwise infinitely recursive call chain is aborted that H_Hat() 
>>> continues to execute infinite recursion.
>>
>> Yes, but in your code it is the *wrong* instance of your H that is 
>> doing the aborting. The outermost H absolutely does not *have* to 
>> terminate its input, as the emulated H_Hat(H_Hat) *would* terminate 
>> without being aborted by the outer H.
>>
>> And that is fundamentally what the halting problems asks: does 
>> H_Hat(H_Hat) halt on its own? It does, except that your outermost H 
>> doesn't let it get that far, which means that your outermost H isn't 
>> correctly answering the question you claim it is answering, i.e. did I 
>> *have* to halt my input to prevent an infinite execution.
>>
>> André
>>
> 
> When-so-ever UTM halt decider H decides that:
> (1) its input (<P>,I) would never halt unless H stopped simulating it
>    and
> (2) its input (<P>,I) would never halt unless H stopped simulating it
> then H has made a correct not-halting decision on this input.

It's unclear to me what you hope to achieve by repeating this mantra. 
The point I make above is that clause (2) of your mantra is not met in 
this case, meaning that H has not made the correct decision on this input.

André

-- 
To email remove 'invalid' & replace 'gm' with well known Google mail 
service.

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


Thread

Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) olcott <NoOne@NoWhere.com> - 2020-11-11 08:45 -0600
  Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-11 15:23 +0000
    Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) olcott <NoOne@NoWhere.com> - 2020-11-11 09:26 -0600
  Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-11 17:29 +0000
    Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) olcott <NoOne@NoWhere.com> - 2020-11-11 17:13 -0600
      Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-12 01:06 +0000
        Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (tautology) olcott <NoOne@NoWhere.com> - 2020-11-11 19:20 -0600
          Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (tautology) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-12 02:08 +0000
            Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 00:09 -0600
              Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) André G. Isaak <agisaak@gm.invalid> - 2020-11-12 08:06 -0700
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 09:19 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) André G. Isaak <agisaak@gm.invalid> - 2020-11-12 10:40 -0700
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 12:21 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) André G. Isaak <agisaak@gm.invalid> - 2020-11-12 12:09 -0700
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 22:46 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) André G. Isaak <agisaak@gm.invalid> - 2020-11-13 01:22 -0700
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 07:55 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 07:57 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) André G. Isaak <agisaak@gm.invalid> - 2020-11-13 09:12 -0700
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 10:21 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 11:17 +0000
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 07:48 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 10:22 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 09:28 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 10:46 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 10:16 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 11:44 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 11:22 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 15:54 +0000
              Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-12 15:23 +0000
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 09:30 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-12 11:19 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 10:36 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-12 12:47 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-11-12 12:21 -0800
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 22:48 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 22:11 -0600

csiph-web