Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Every sufficiently competent C programmer knows ---
 Counter-Factual ERROR
Date: Wed, 12 Mar 2025 07:25:39 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <cf81ec66956dff34f33af86f95a720a3f01df3b8@i2pn2.org>
References: <vqntaq$1jut5$1@dont-email.me> <vqp388$1tvqa$1@dont-email.me>
 <vqpdv9$202b2$2@dont-email.me> <vqperb$20c9k$2@dont-email.me>
 <E6mcnWv3nMa66036nZ2dnZfqnPWdnZ2d@brightview.co.uk>
 <vqqf28$27b1g$1@dont-email.me>
 <2d96ca85f669c5798af817ae63320fae806c6e95@i2pn2.org>
 <vqquag$29meg$8@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 12 Mar 2025 11:25:40 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="4020583"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
Content-Language: en-US
In-Reply-To: <vqquag$29meg$8@dont-email.me>
X-Spam-Checker-Version: SpamAssassin 4.0.0

On 3/11/25 11:16 PM, olcott wrote:
> On 3/11/2025 10:04 PM, Richard Damon wrote:
>> On 3/11/25 6:56 PM, olcott wrote:
>>> On 3/11/2025 12:42 PM, Mike Terry wrote:
>>>> On 11/03/2025 13:46, Richard Heathfield wrote:
>>>>> On 11/03/2025 13:31, olcott wrote:
>>>>>> On 3/11/2025 5:28 AM, Mikko wrote:
>>>>>>> On 2025-03-10 23:41:13 +0000, olcott said:
>>>>>>>
>>>>>>>> typedef void (*ptr)();
>>>>>>>> int HHH(ptr P);
>>>>>>>>
>>>>>>>> void Infinite_Loop()
>>>>>>>> {
>>>>>>>>    HERE: goto HERE;
>>>>>>>>    return;
>>>>>>>> }
>>>>>>>>
>>>>>>>> void Infinite_Recursion()
>>>>>>>> {
>>>>>>>>    Infinite_Recursion();
>>>>>>>>    return;
>>>>>>>> }
>>>>>>>>
>>>>>>>> void DDD()
>>>>>>>> {
>>>>>>>>    HHH(DDD);
>>>>>>>>    return;
>>>>>>>> }
>>>>>>>>
>>>>>>>> int DD()
>>>>>>>> {
>>>>>>>>    int Halt_Status = HHH(DD);
>>>>>>>>    if (Halt_Status)
>>>>>>>>      HERE: goto HERE;
>>>>>>>>    return Halt_Status;
>>>>>>>> }
>>>>>>>>
>>>>>>>> That when HHH correctly emulates N steps of the
>>>>>>>> above functions that none of these functions can
>>>>>>>> possibly reach their own "return" instruction
>>>>>>>> and terminate normally.
>>>>>>>
>>>>>>> Every competent programmer knows that the information given is
>>>>>>> insufficient to determine whether HHH emulates at all, and whether
>>>>>>> it emulates correctly if it does.
>>>>>>>
>>>>>>>> Since HHH does see that same pattern that competent
>>>>>>>> C programmers see it correctly aborts its emulation
>>>>>>>> and rejects these inputs as non terminating.
>>>>>>>
>>>>>>> Whether HHH does see those patterns cannot be inferred from the 
>>>>>>> information
>>>>>>> given. Only about DDD one can see that it halts if HHH returns. 
>>>>>>> In addition,
>>>>>>> the given information does not tell whether HHH can see patterns 
>>>>>>> that are
>>>>>>> not there.
>>>>>>>
>>>>>>> How many competent programmers you have asked?
>>>>>>>
>>>>>>
>>>>>> Two C programmers with masters degrees in computer science
>>>>>> agree that DDD correctly emulated by HHH cannot possibly
>>>>>> reach its own "return" instruction and terminate normally.
>>>>>
>>>>> Bring 'em on. Perhaps /they/ have the source to HHH, because 
>>>>> without it you don't have anything. (And btw whatever it is you 
>>>>> claim to have is far from clear, because all I've seen so far is an 
>>>>> attempt to express the Halting Problem in C and pseuodocode, where 
>>>>> the pseudocode reads: HHH(){ magic happens }
>>>>
>>>> It takes newcommers a while to understand the context behind what PO 
>>>> is saying, and he never bothers to properly explain it himself, and 
>>>> is incapable of doing so in any rigorous fashion.
>>>>
>>>> So I'll explain for you my interpretation.
>>>>
>>>> His HHH is a C function called by DDD, which will "simulate" DDD(). 
>>>> The simulation consists of simulating the individual x86 
>>>> instructions of DDD [and functions it calls] sequentially, and may 
>>>> only be a / partial/ simulation, because HHH also contains logic to 
>>>> analyse the progress of the simulation, and it may decide at some 
>>>> point to simply stop simulating.  (This being referred to as HHH 
>>>> "aborting" its simulation.)
>>>>
>>>> Of course, we expect that the (partial) simulation of DDD will 
>>>> exactly track the direct execution of DDD, up to the point where HHH 
>>>> aborts the simulation.  [This is NOT what PO's actual HHH code does, 
>>>> due to bugs/ design errors/misunderstandings etc., but for the 
>>>> purpose of PO's current point, you might consider this to be what 
>>>> happens.]
>>>>
>>>> So if we imagine HHH never aborts, then HHH simulates DDD(), which 
>>>> calls HHH, and (simulated) HHH will again simulate DDD() - a nested 
>>>> simulation.  (PO calls this recursive simulation.)  This continues, 
>>>> and such an HHH will obviously never terminate - in particular THE 
>>>> SIMULATION by outer HHH will never proceed as far as DDD's final ret 
>>>> instruction.  (This is genuine "infinitely recursive simulation")
>>>>
>>>> OTOH if HHH logic aborts the simulation at some point, regardless of 
>>>> how many nested levels of simulation have built up, it will be the / 
>>>> outer/ HHH that aborts, because the outer HHH is ahead of all the 
>>>> simulated HHH's in its progress and will reach its abort criterion 
>>>> first.  At the point where it aborts, the DDD it is simulating will 
>>>> clearly not have reached its final ret instruction, as then its 
>>>> simulation would have ended "normally" rather than aborting.
>>>>
>>>> So whatever HHH's exact logic and abort criteria, it will not be the 
>>>> case that its *simulation of DDD* progresses as far as DDD's final 
>>>> ret instruction:  either HHH never aborts so never terminates, or if 
>>>> it does abort, the (outer) HHH simulating it will abort DDD before 
>>>> it gets to the final ret instruction.
>>>>
>>>> The key point here is that we are not talking about whether DDD() 
>>>> halts!  We are only talking about whether HHH's /simulation/ of DDD 
>>>> proceeds as far as simulating the final DDD ret instruction.  So at 
>>>> this point we are not talking about the Halting Problem, as that is 
>>>> concerned with whether DDD() halts, not whether some partial 
>>>> simulation of DDD() simulates as far as the ret instruction.
>>>>
>>>> Given that HHH is free to stop simulating DDD *whenever it wants*, 
>>>> you might consider it rather banal to be arguing for several months 
>>>> over whether it actually simulates as far as DDD's return. After 
>>>> all, it could simulate one instruction and then give up, so it 
>>>> didn't get as far as DDD returning - but SO WHAT!?  Why is PO even 
>>>> considering such a question?
>>>>
>>>> [PO would say something like "/however far/ HHH simulates this 
>>>> remains the case", misunderstanding the fact that here he is talking 
>>>> about multiple different HHHs, each with their own distinct DDDs. 
>>>> (Yes, none of those different HHHs simulate their corresponding DDD 
>>>> to completion, but all of those DDD halt [if run directly], assuming 
>>>> their HHH aborts the simulation at some point.  We can see this just 
>>>> from the given code of DDD: if HHH returns, DDD returns...)]
>>>>
>>>> But if you think PO properly understands this you would be vastly 
>>>> overestimating his reasoning powers and his capacity for abstract 
>>>> thought.  Even if you "agree" that HHH (however coded) will not 
>>>> simulate DDD to completion, you would not really be "agreeing" with 
>>>> PO as such, because that would imply you understand PO's 
>>>> understanding of all that's been said, and that there is a shared 
>>>> agreement on the meaning of what's been said and its consequences 
>>>> etc., and we can guarantee that will NOT be the case!  We could say 
>>>> PO "fractally" misunderstands every technical concept needed to 
>>>> properly discuss the halting problem (or any other technical topic).
>>>>
>>>> PO's "understanding" will entail some idea that the situation means 
>>>> that DDD "actually" doesn't halt, or that HHH is "correct" to say 
>>>> that DDD doesn't halt. 
>>>
>>>
>>>> (Even though it demonstrably DOES halt if not aborted and simulated 
>>>> further. 
>>>
>>> DDD correctly simulated by HHH never reaches its
>>> own "return" instruction and terminates normally
>>> in any finite or infinite number of correctly
>>> simulated steps.
>>>
>>>
>>
>> And HHH that correctly simulated its input DD 
> 
> You did not even bother to notice that I changed the subject
> to DDD because DD beyond everyone's skill level.
> 

Same applies to both.

Are you so stupid you need to change to deceptive tacktics?

For DDD, we don't even need to figure out what HHH needs to return to 
see that DDD will halt if HHH returns an answer, which it does if it is 
========== REMAINDER OF ARTICLE TRUNCATED ==========