Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory,comp.lang.c,comp.lang.c++
Subject: Re: Every sufficiently competent C programmer knows --- Very Stupid
 Mistake
Followup-To: comp.theory
Date: Tue, 11 Mar 2025 20:22:13 -0500
Organization: A noiseless patient Spider
Lines: 163
Message-ID: <vqqnk5$28jtr$1@dont-email.me>
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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 12 Mar 2025 02:22:14 +0100 (CET)
Injection-Info: dont-email.me; posting-host="da28212957632e1bc35b68d4fbc88507";
	logging-data="2379707"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/LPilRgD8gchOW5va7GdHj"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:BHopzK6YKksmm8RvraFzvHSY1qI=
In-Reply-To: <E6mcnWv3nMa66036nZ2dnZfqnPWdnZ2d@brightview.co.uk>
X-Antivirus: Norton (VPS 250311-4, 3/11/2025), Outbound message
X-Antivirus-Status: Clean
Content-Language: en-US
Bytes: 8517

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.  

This is a very stupid mistake:
> (Even though it demonstrably DOES halt if not aborted and simulated further.  

void DDD()
{
   HHH(DDD);
   return;
}

DDD correctly simulated by HHH never reaches its
own "return" instruction and terminates normally
in any finite or infinite number of correctly
simulated steps.

-- 
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer