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


Groups > comp.theory > #34374

Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width test)

Subject Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width test)
Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng, sci.math.symbolic
References <DY6dnRZxEsEfey79nZ2dnUU7-QvNnZ2d@giganews.com> <Goudnd3FYMUXai79nZ2dnUU7-c_NnZ2d@giganews.com> <IvGdnVf-6Kn2myj9nZ2dnUU78QPNnZ2d@brightview.co.uk>
From olcott <NoOne@NoWhere.com>
Date 2021-05-31 12:52 -0500
Message-ID <Ttedne4noOb3vyj9nZ2dnUU7-R3NnZ2d@giganews.com> (permalink)

Cross-posted to 4 groups.

Show all headers | View raw


On 5/31/2021 10:53 AM, Mike Terry wrote:
> On 30/05/2021 21:37, olcott wrote:
>> On 5/30/2021 2:24 PM, olcott wrote:
>>>
>>> https://www.researchgate.net/publication/351947980_Refutation_of_Halting_Problem_Diagonalization_Argument 
>>>
> 
> tldr;  just the usual "PO totally failing to understand what he is 
> reading, and as a result confidently spouting nonsense as a result"...
> 
> FTR, PO is pretty much incapable of following abstract reasoning or 
> understanding abstact concepts.  "Arguing" with him is totally 
> pointless.  Do not assume that because he replies to a post and nobody 
> responds, that means he has said anything coherent or logical, or that 
> anybody else implicitly agrees with what he said.
> 
>>>
>> Refuting the Halting Problem Diagonalization Argument
>>
>> Every machine that halts in a reject state is a halting computation. 
>> At least two proofs ignore this when constructing Sipser's Figure 4.5. 
>> Because these two proofs ignore this when they insert machine D into 
>> Sipser's Figure 4.5 they do so incorrectly.
> 
> Dude... Sipser explicitly says blank entries are "either non-halting or 
> reject" entries.  He is not ignoring anything.  You just can't follow 
> his argument.
> 
> I think you are confused at what you're looking at in Sipser. You 
> reference Sipser's Theorem 4.9, and it's clear you think that is a proof 
> of the undecidability of the Halting Problem.  IT IS NOT - it's a proof 
> of the undecidability of the *Accepting* TM problem.  The clue for you 
> should have been in the name ATM (rather than HTM).  Didn't you wonder 
> What the A stood for?

Ah, so then we are back to this, when we translate the abstraction into 
concrete code then nothing slips through the cracks unnoticed:

#define u32 uint32_t

int Simulate(u32 P, u32 I)
{
   ((void(*)(u32))P)(I);
   return 1;
}

// When D attempts to return a value that is the opposite of
// the value that H returns, it still gets stuck in infinitely
// nested simulation.
int D(u32 P)   // P is a machine address
{
   if ( H(P, P) )
     return 0   // reject when H accepts
   return 1;    // accept when H rejects
}

int main()
{
   H((u32)D, (u32)D);
}


If H is not a simulating halt decider if it is a simulating acceptance 
decider then both H and D get stuck in infinitely nested simulation.

If H is a simulating halt decider then H must stop simulating its input 
because if H did not stop simulating its input then D would have the 
same halting behavior as if D called Simulate instead of H.

The above analysis is confirmed by actual execution of the above 
function in the x86utm operating system. H detects an infinitely 
repeating non-halting pattern that never reaches the second line of D.


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

Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width test) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-05-31 16:53 +0100
  Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width text) Richard Damon <Richard@Damon-Family.org> - 2021-05-31 13:15 -0400
    Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width text) olcott <NoOne@NoWhere.com> - 2021-05-31 12:31 -0500
      Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width text) Richard Damon <Richard@Damon-Family.org> - 2021-05-31 14:10 -0400
    Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width text) Jeff Barnett <jbb@notatt.com> - 2021-05-31 12:14 -0600
  Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width test) Richard Damon <Richard@Damon-Family.org> - 2021-05-31 14:17 -0400
    Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width test) olcott <NoOne@NoWhere.com> - 2021-05-31 14:19 -0500
  Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width text) olcott <NoOne@NoWhere.com> - 2021-05-31 11:21 -0500
  Re: Refuting the Halting Problem Diagonalization Argument (requires fixed width test) olcott <NoOne@NoWhere.com> - 2021-05-31 12:52 -0500
  Refuting the Sipser Halting Problem Diagonalization Conclusion olcott <NoOne@NoWhere.com> - 2021-05-31 20:07 -0500
    Re: Refuting the Sipser Halting Problem Diagonalization Conclusion Richard Damon <Richard@Damon-Family.org> - 2021-05-31 21:57 -0400

csiph-web