Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| 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.
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
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