Path: ...!Xl.tags.giganews.com!local-3.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 11 Mar 2025 21:07:19 +0000
Subject: Re: Every sufficiently competent C programmer knows --- Stupid
 Mistake?
Newsgroups: comp.theory
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>
 <vqq339$24m6v$3@dont-email.me>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Tue, 11 Mar 2025 21:07:08 +0000
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
MIME-Version: 1.0
In-Reply-To: <vqq339$24m6v$3@dont-email.me>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <4bOdnXt2KfOaO036nZ2dnZfqn_qdnZ2d@brightview.co.uk>
Lines: 162
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-YoBCFeSkgpJ5Kdp9zKOkQ2cdUgIAlnApSVqJUueN5DpXxHtnQRJMMr7DjxlIxisb0O2jtChWwIdV8vF!/1JpGFr4ZkID9uHK3RUl9SXAC6xFQUTTWb80rHOsBouuus3wtbRBBW6QzPdR+B6o5YUtX5bcyw6y!/iKQhm9/CYDT/t6x1FoVKtETBwM=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 9077

On 11/03/2025 19:31, 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. 
> 
> void DDD()
> {
>    HHH(DDD);
>    return;
> }
> 
> _DDD()
> [00002172] 55         push ebp      ; housekeeping
> [00002173] 8bec       mov ebp,esp   ; housekeeping
> [00002175] 6872210000 push 00002172 ; push DDD
> [0000217a] e853f4ffff call 000015d2 ; call HHH(DDD)
> [0000217f] 83c404     add esp,+04
> [00002182] 5d         pop ebp
> [00002183] c3         ret
> Size in bytes:(0018) [00002183]
> 
> I am shocked that you would make such a stupid
> mistake and say that:
> 
> N steps of DDD correctly emulated by HHH can
> possibly reach its own “return” instruction
> and terminate normally when:

As usual, you are totally clueless about what was actually said by other people.

I didn't say any of the stuff you are claiming as my "stupid mistake".

Mike.


> 
> It is also stipulated that HHH can and does
> correctly emulate itself emulating DDD.
>