Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory,comp.lang.c,comp.lang.c++ Subject: Re: Every sufficiently competent C programmer knows --- Counter-Factual ERROR Followup-To: comp.theory Date: Tue, 11 Mar 2025 17:56:06 -0500 Organization: A noiseless patient Spider Lines: 159 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 11 Mar 2025 23:56:09 +0100 (CET) Injection-Info: dont-email.me; posting-host="ec8ee61485d3eccfb61af570452d4324"; logging-data="2337840"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/fbXzkYUTvOYkyzT7Xs8k+" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:pEVjHyVekGga50B0OBJdpa3qu44= X-Antivirus-Status: Clean Content-Language: en-US In-Reply-To: X-Antivirus: Norton (VPS 250311-4, 3/11/2025), Outbound message Bytes: 8449 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. 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