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: From: Mike Terry 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: 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. >