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

Groups > comp.software-eng > #3204

Re: Halting Problem Solved? ( H(P,P)==0 is correct )

Cross-posted to 4 groups.

Show all headers | View raw

On 7/20/2021 10:26 PM, André G. Isaak wrote:
> On 2021-07-20 21:06, olcott wrote:
>> On 7/20/2021 9:24 PM, André G. Isaak wrote:
>>> On 2021-07-20 20:04, olcott wrote:
>>>> On 7/20/2021 7:34 PM, André G. Isaak wrote:
>>>>> On 2021-07-20 17:20, olcott wrote:
>>>>>> On 7/20/2021 5:27 PM, André G. Isaak wrote:
>>>>>>> On 2021-07-20 16:14, olcott wrote:
>>>>>>>> On 7/20/2021 2:49 PM, André G. Isaak wrote:
>>>>>>>>> On 2021-07-20 13:04, olcott wrote:
>>>>>>>>>> On 7/20/2021 1:53 PM, Alan Mackenzie wrote:
>>>>>>>>>>> [ Malicious cross posting removed ]
>>>>>>>>>>>
>>>>>>>>>>> In comp.theory olcott <NoOne@nowhere.com> wrote:
>>>>>>>>>>>> On 7/20/2021 12:35 PM, Alan Mackenzie wrote:
>>>>>>>>>>>>> [ Malicious cross posting removed ]
>>>>>>>>>>>
>>>>>>>>>>>>> In comp.theory olcott <NoOne@nowhere.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>> [ .... ]
>>>>>>>>>>>
>>>>>>>>>>>>>> I show all the steps of exactly how H(P,P)==0 is derived.
>>>>>>>>>>>
>>>>>>>>>>>>> You don't.  You haven't yet published the source code of an 
>>>>>>>>>>>>> alleged H.
>>>>>>>>>>>
>>>>>>>>>>>>>> That you simply ignore these steps and claim that I am 
>>>>>>>>>>>>>> incorrect is
>>>>>>>>>>>>>> simply dishonest.
>>>>>>>>>>>
>>>>>>>>>>>>> No, it's being dishonest to indulge you with the suggestion 
>>>>>>>>>>>>> that what
>>>>>>>>>>>>> you are doing has any possible validity.  It is unimportant 
>>>>>>>>>>>>> and
>>>>>>>>>>>>> uninteresting why H(P,P)==0, if it actually is.  It has no 
>>>>>>>>>>>>> bearing on
>>>>>>>>>>>>> the halting theorem proofs, which work regardless of the 
>>>>>>>>>>>>> nature of any
>>>>>>>>>>>>> purported halting decider.  Seeing as how you can't 
>>>>>>>>>>>>> disprove these
>>>>>>>>>>>>> proofs honestly, you resort to falsehoods and obfuscation. 
>>>>>>>>>>>>> Even so,
>>>>>>>>>>>>> the other posters on this newsgroup have seen through it 
>>>>>>>>>>>>> and exposed
>>>>>>>>>>>>> it.  When is all this nonsense going to end?
>>>>>>>>>>>
>>>>>>>>>>> [ .... ]
>>>>>>>>>>>
>>>>>>>>>>>> All of the proofs conclusively prove that H cannot possibly 
>>>>>>>>>>>> return a
>>>>>>>>>>>> Boolean value corresponding to the actual halt status of P 
>>>>>>>>>>>> to P in the
>>>>>>>>>>>> above computation.
>>>>>>>>>>>
>>>>>>>>>>> Wow!
>>>>>>>>>>>
>>>>>>>>>>>> None of the proofs bother to examine whether or not 
>>>>>>>>>>>> returning a correct
>>>>>>>>>>>> halt status from H to P in the above computation is 
>>>>>>>>>>>> required, they
>>>>>>>>>>>> simply assume that it is required. *That is their error*
>>>>>>>>>>>
>>>>>>>>>>> For crying out loud!  It is an error to require what is 
>>>>>>>>>>> required by the
>>>>>>>>>>> statement of the problem?  The central element of the halting 
>>>>>>>>>>> problem is
>>>>>>>>>>> a *UNIVERSAL* halting decider.  And you're saying insisting 
>>>>>>>>>>> upon this
>>>>>>>>>>> *universality* is an error?
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I universal halt decider is one thing.
>>>>>>>>>>
>>>>>>>>>> A universal halt decider that must return a correct halt 
>>>>>>>>>> status to an input that does the opposite of whatever it 
>>>>>>>>>> decides is a much narrower specification.
>>>>>>>>>
>>>>>>>>> 'Universal' means it decides all Turing Machines. The latter 
>>>>>>>>> would case would be included in 'universal'. so if it cannot 
>>>>>>>>> return the correct decision in that case it is not universal.
>>>>>>>>>
>>>>>>>>
>>>>>>>> It is not strictly necessary for a halt decider to return any 
>>>>>>>> value to its input. This is merely a false assumption. H in 
>>>>>>>> main() aborts the simulation of P before the simulation of H in 
>>>>>>>> P ever returns any value to P. All of P including the simulation 
>>>>>>>> of H in P is strictly controlled by the H in main():
>>>>>>>
>>>>>>> But it is your contention that your 'decider' *only* aborts an 
>>>>>>> input if that input would not otherwise halt. 
>>>>>>
>>>>>> It took me several days to verify (many months before I began 
>>>>>> posting about it) yet it is confirmed that if the outermost H does 
>>>>>> not abort its input then no other H ever will.
>>>>>
>>>>> But what does the outermost H do *after* it aborts its input? When 
>>>>> P(P) is run independently, neither the outermost P nor the H which 
>>>>> it contains are being simulated so they cannot be aborted. So what 
>>>>> value does the H inside the outermost P return to P?
>>>>>
>>>>
>>>> void P(u32 x)
>>>> {
>>>>    if (H(x, x))
>>>>      HERE: goto HERE;
>>>> }
>>>>
>>>> int main()
>>>> {
>>>>    P((u32)P);
>>>> }
>>>>
>>>> P(P) does specify infinitely nested simulation that must be aborted 
>>>> or it will never stop running. Invoking P(P) in main() merely 
>>>> postpones the inevitable.
>>>
>>> P(P) specifies a computation which at some point starts a series of 
>>> simulations, but the outermost P isn't part of that series of 
>>> simulations.
>>>
>>>>>>> If you are forced to abort some instance of H you are therefore 
>>>>>>> claiming that that instance does not halt on its input, which 
>>>>>>> means that you are acknowledging that your H cannot decide all 
>>>>>>> possible inputs. Therefore H is not a universal decider.
>>>>>>>
>>>>>>> Moreover, when P(P) is run independently, neither the uppermost P 
>>>>>>> nor the H inside the uppermost P are under the controller of a 
>>>>>>> simulator 
>>>>>>
>>>>>> The H that is executed rather than simulating by another H is 
>>>>>> always in control of its whole simulation chain.
>>>>>
>>>>> When P(P) is executed independently, the outermost P isn't part of 
>>>>> any simulation chain and is outside the scope of any H.
>>>>>
>>>>
>>>> When the outermost P stops running this does not count as halting 
>>>> every element of the P(P) invocation chain specifies infinitely 
>>>> nested simulation.
>>>
>>> Of course it counts as halting. The outermost P isn't being 
>>> simulated, so it can't be aborted.
>>>
>>> I've agreed that when you abort a simulation that doesn't entail that 
>>> the *simulation* halted, because the simulation never reaches one of 
>>> its final states.
>>>
>>> But the outermost P *isn't* (and can't be) aborted. It halts by 
>>> reaching one of its final states. That is what it means to halt *by 
>>> definition*. That definitely counts as halting.
>>>
>>>>>>> since they are not being simulated. Therefore, the H inside the 
>>>>>>> uppermost P *must* return a value to the uppermost P since there 
>>>>>>> is no way for that H to be aborted. So which value does it return?
>>>>>>>
>>>>>>> André
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> None-the-less by logical necessity whenever H aborts its input it 
>>>>>> is always correct because its input would never ever stop running 
>>>>>> unless aborted.
>>>>>
>>>>> That doesn't answer my question. Which value does the H contained 
>>>>> in the outermost P (the one that isn't emulated) return to P?
>>>>
>>>> The question is whether or not H decides its input correctly.
>>>> We know that H does decide its input correctly by logical necessity.
>>>
>>> So why not actually answer the question? If H decides its input 
>>> correctly, what answer does the H contained in the outermost P return 
>>> to the outermost P?
>>>
>>
>> We know that the input to H does not halt on its input by logical 
>> necessity: We can verify that the input to H never every halts unless 
>> H aborts its simulation of its input:(P, P).
> 
> There's no 'logical necessity' involved here. The definition of 
> 'halting' is clear and unambiguous. A computation halts when it reaches 
> one of its final states.
> 
> If the H contained in the outermost P of P(P) returns 'false', then the 
> outermost P *will* reach one of its final states, which means that P(P) 
> *does* halt. This clearly and unambiguously demonstrates that whatever 
> 'logic' your H is using to decide that P(P) doesn't halt is simply wrong.
> 

This would be a contradiction proving that whatever logic that H uses is 
wrong except that the logic that H used is verifiably infallible.

This is why I phrased this case as [What if a cat barks?]

If you verify that H did decide that its input never halts correctly and 
then a very similar computation does halt, then this is just like 
verifying that an animal is a cat by its DNA and then this cat barks.

It is absolutely certain that the input to H(P,P) cannot possibly stop 
running unless H aborts its simulation of its input. We verified that 
the animal has cat DNA.

When we run int main() { P(P); } P reaches its final state c3f.
The cat barks.

> There is absolutely no way around this fact. You can't simply declare 
> that some instances of halting 'don't count' to justify your answer. 
> Halting is well-defined. There is absolutely no doubt as to the fact 
> that P(P) halts. To claim otherwise is simply delusional.
> 
>> This proves that H does decide its input (P,P) correctly. The halting 
>> problem proofs that claim to prove this is impossible are wrong.
>>
>>> Does it return 'halts', thereby forcing the outermost P into an 
>>> infinite loop, thereby contradicting the answer given by H, or does 
>>> it return 'doesn't halt', thereby causing the outermost P to *HALT*, 
>>> also contradicting the answer given by H?
> 
> And once again you refused to *directly* answer a simply question, 
> presumably because you know that a direct answer would demonstrate how 
> wrong your reasoning is.
> 
> André
> 
>>> It has to be one or the other.
>>>
>>>> Any other question unrelated to this question is the dishonest dodge 
>>>> kind of fake rebuttal.
>>>
>>> You're the one who appears to be dodging the question. What does the 
>>> H that *isn't* being simulated return to the P that *isn't* being 
>>> simulated?
>>>
>>> Neither of those can be aborted, and if H is truly a decider, it 
>>> *must* return an answer to the outermost P.
>>>
>>> André
>>>
>>
>>
> 
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

Back to comp.software-eng | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 11:17 -0500
  Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 15:19 -0500
    Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 16:48 -0500
      Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-19 08:58 -0500
        Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-20 08:25 -0500
          Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 13:26 -0500
            Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 14:04 -0500
              Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 18:20 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 21:04 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 22:06 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 22:53 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 23:24 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ DOES NOT HOLD ] olcott <NoOne@NoWhere.com> - 2021-07-21 09:11 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 11:45 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] olcott <NoOne@NoWhere.com> - 2021-07-21 12:23 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] olcott <NoOne@NoWhere.com> - 2021-07-21 16:29 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 12:51 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 13:49 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 14:43 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ][ADD] olcott <NoOne@NoWhere.com> - 2021-07-21 16:07 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ][ADD] olcott <NoOne@NoWhere.com> - 2021-07-21 16:50 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 16:22 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 17:21 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 20:21 -0500
                Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 15:29 -0500

csiph-web