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


Groups > comp.theory > #25204

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-12 12:09 -0700
Organization Christians and Atheists United Against Creeping Agnosticism
Message-ID <rok18h$4lb$1@dont-email.me> (permalink)
References (6 earlier) <D5idnX7ICPwJTDHCnZ2dnUU7-KHNnZ2d@giganews.com> <rojj2h$jl2$1@dont-email.me> <1PadnXhiTNMWzzDCnZ2dnUU7-Q_NnZ2d@giganews.com> <rojs1q$rb2$1@dont-email.me> <6sKdnbsZcO6i4DDCnZ2dnUU7-b3NnZ2d@giganews.com>

Show all headers | View raw


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é

-- 
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