Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail From: Richard Damon Newsgroups: comp.theory Subject: Re: Every sufficiently competent C programmer knows --- Freaking Nitwit Date: Wed, 12 Mar 2025 23:56:11 -0400 Organization: i2pn2 (i2pn.org) Message-ID: <578a4ea6c399db6bd12ed3ed8b173b642b8e06aa@i2pn2.org> References: <5429f6c8b8a8a79e06b4aeefe677cc54a2a636bf@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Thu, 13 Mar 2025 03:56:11 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="4126778"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird Content-Language: en-US In-Reply-To: X-Spam-Checker-Version: SpamAssassin 4.0.0 Bytes: 10851 Lines: 212 On 3/12/25 8:41 PM, olcott wrote: > On 3/12/2025 5:47 PM, Richard Damon wrote: >> On 3/12/25 9:37 AM, 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. >>> >>> >>> This is Mike's very stupid mistake: >>> I always thought that Mike was much smarter than this (he usually is) >>>> (Even though it demonstrably DOES halt if not aborted and simulated >>>> further. >>> >>> void DDD() >>> { >>>    HHH(DDD); >>>    return; >>> } >>> >>> Every competent C programmer knows when any N steps of DDD >>> are correctly emulated by x86 emulator HHH (that can emulate >>> itself emulating DDD) that DDD never reaches its own "return" >>> instruction in any finite (or infinite) number of steps. >>> >>> As a matter of actual verified fact HHH emulates the >>> first four instructions of the x86 machine code of DDD >>> which call itself to repeat this process. >> ========== REMAINDER OF ARTICLE TRUNCATED ==========