Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Every sufficiently competent C programmer knows --- Very Stupid Mistake
Date: Wed, 12 Mar 2025 12:08:51 +0200
Organization: -
Lines: 167
Message-ID: <vqrmfj$2i561$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> <vqqnk5$28jtr$1@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:08:52 +0100 (CET)
Injection-Info: dont-email.me; posting-host="4800ed2580b521525ad65aa6595e0d98";
	logging-data="2692289"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/JwgIqYGXjtIrphZalo5sY"
User-Agent: Unison/2.2
Cancel-Lock: sha1:NxQdj1isXlUYqeafLIfIv3OreIE=

On 2025-03-12 01:22:13 +0000, olcott said:

> 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.

If HHH would do what a partial halt decider should do it would see that
it does not matter what value it returns so there is no need to simulate
the execution of HHH.

-- 
Mikko