Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Keith Thompson Newsgroups: comp.theory Subject: Re: Incorrect requirements --- Computing the mapping from the input to HHH(DD) Date: Thu, 08 May 2025 22:31:05 -0700 Organization: None to speak of Lines: 176 Message-ID: <87frhebbae.fsf@nosuchdomain.example.com> References: <87msbmeo3b.fsf@nosuchdomain.example.com> <87a57mek8r.fsf@nosuchdomain.example.com> <87seled0zy.fsf@nosuchdomain.example.com> <87zffmbeyt.fsf@nosuchdomain.example.com> MIME-Version: 1.0 Content-Type: text/plain Injection-Date: Fri, 09 May 2025 07:31:06 +0200 (CEST) Injection-Info: dont-email.me; posting-host="302a6dd640940106301f9e87fdade96e"; logging-data="2680540"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19eqlqiN9CYaFYzkIzuoNeA" User-Agent: Gnus/5.13 (Gnus v5.13) Cancel-Lock: sha1:jOFs4UuoPkbI1LGtYlVWKd2YX1o= sha1:n91F4xIqGk00TGlNb+eyis/tYs0= Bytes: 9161 olcott writes: > On 5/8/2025 11:11 PM, Keith Thompson wrote: >> olcott writes: >>> On 5/8/2025 8:30 PM, Keith Thompson wrote: >>>> olcott writes: >>>>> On 5/8/2025 6:49 PM, Keith Thompson wrote: >>>>>> olcott writes: >>>>>> [...] >>>>>>> void DDD() >>>>>>> { >>>>>>> HHH(DDD); >>>>>>> return; >>>>>>> } >>>>>>> >>>>>>> If you are a competent C programmer then you >>>>>>> know that DDD correctly simulated by HHH cannot >>>>>>> possibly each its own "return" instruction. >>>>>> "cannot possibly each"? >>>>>> I am a competent C programmer (and I don't believe you can make >>>>>> the same claim). I don't know what HHH is. The name "HHH" tells >>>>>> me nothing about what it's supposed to do. Without knowing what >>>>>> HHH is, I can't say much about your code (or is it pseudo-code?). >>>>>> >>>>> >>>>> For the purpose of this discussion HHH is exactly >>>>> what I said it is. It correctly simulates DDD. >>>> Does HHH correctly simulate DDD *and do nothing else*? >>>> Does HHH correctly simulate *every* function whose address is passed >>>> to it? Must the passed function be one that takes no arguments >>>> and does not return a value? >>>> Can HHH just *call* the function whose address is passed to it? >>>> If it's a correct simulation, there should be no difference between >>>> calling the function and "correctly simulating" it. >>>> My knowledge of C tells me nothing about *how* HHH might simulate >>>> DDD. >>> >>> HHH can only simulate a function that take no arguments >>> and has no return value. HHH also simulates the entire >>> chain of functions that this function calls. These can >>> take arguments or not and have return values or not. >>> >>> Thus HHH ends up simulating itself (and everything >>> that HHH calls) simulating DDD in an infinite >>> sequence of recursive emulation until OOM error. >>> >>>>> We need not know anything else about HHH to >>>>> know that DDD correctly simulated by HHH cannot >>>>> possibly REACH its own "return" instruction. >>>> Assuming that HHH(DDD) "correctly simulates" DDD, and assuming it >>>> does nothing else, your code would be equivalent to this: >>>> void DDD(void) { >>>> DDD(); >>>> return; >>>> } >>> >>> Exactly. None of these people on comp.theory could >>> get that even after three years. >> I find that difficult to believe. >> >>>> Then the return statement (which is unnecessary anyway) will never be >>>> reached. >>> >>> It is only there to mark a final halt state. >> The closing "}" does that equally well. >> >>>> In practice, the program will likely crash due to a stack >>>> overflow, unless the compiler implements tail-call optimization, in >>>> which case the program might just run forever -- which also means the >>>> unnecessary return statement will never be reached. >>>> >>> >>> Yes you totally have this correctly. >>> None of the dozens of comp.theory people could >>> ever achieve that level of understanding even >>> after three years. That is why I needed to post >>> on comp.lang.c. >> I'll note that I've posted in comp.theory, not in comp.lang.c. >> I never see anything you post in comp.lang.c. >> >>>> This conclusion relies on my understanding of what you've said about >>>> your code, which I consider to be unreliable. >>> >>> I am not even talking about my code. I am >>> talking about the purely hypothetical code >>> that you just agreed to. >> Do not overestimate what I've agreed to. I must still consider the >> possibility that I've been led into a logical trap of some sort, >> and that I've missed some subtle flaw. >> >>>> No doubt you believe that there is some significance to the >>>> apparent fact that the return statement will never be reached, >>>> assuming that's a correct and relevant conclusion. I don't know >>>> what that significance might be. >>> >>> I will tell you that later after you understand >>> some prerequisite ideas first. >>> >>> int DD() >>> { >>> int Halt_Status = HHH(DD); >>> if (Halt_Status) >>> HERE: goto HERE; >>> return Halt_Status; >>> } >> So now HHH returns an int result, and you store that result >> in a variable named "Halt_Status". You haven't said here what >> the meaning of that result might be, and I decline to make any >> assumptions based on what you've called it. You could rename >> "Halt_Status" to "Foo" and have effectively identical code. >> Previously DDD would "correctly simulate" the function whose address >> is >> passed to it. Now it does that and returns an int result. >> If you want to say anything about the meaning of the result returned >> by HHH, feel free to say it. >> >>> The same thing that applied to DDD equally >>> applies to the more complicated DD. >>> >>> When 1 or more instructions of DD are correctly >>> simulated by HHH the correctly simulated DD >>> cannot possibly get past its call to HHH(DD). >>> Thus DD also never reaches its "return" instruction. >> Now you're talking about simulating "1 or more instructions" >> of DD. I thought that HHH was supposed to "accurately simulate" >> the function whose argument is passed to it. Emulating just "1 or >> more instructions" is not accurate simulation. >> If HHH *fully* simulates the execution of DD, then your code above >> exhibits endless recursion, > > In computer science "halting" is not merely stopping running. > "Halting" is reaching a final halt state such as the "return" > instruction. I fail to see either the truth or the relevance of that statement. We weren't even talking about halting. You did use the C identifier "Halt_Status", but I already told you that the spelling of an identifier implies nothing about its meaning. I said that you hadn't said anything about the meaning of Halt_Status. You declined to explain. You continue to use the term "return instruction". There is no such thing in C. There is a return *statement*. Do you have some reason to insist on using incorrect terminology? >> which is not particularly interesting, >> and it never reaches the "if (Halt_Status)". (DD calls HHH, which >> simulates DD; HHH, in simulating DD, must do the equivalent of >> calling HHH, and so on.) > > It turns out to be very interesting you merely need > to grok a few details first. It's unlikely I'll continue paying attention long enough for it to get interesting. >> You've introduced the idea of simulating only some finite number >> of instructions of the simulated functions, but you haven't really >> said how that happens (except perhaps in some x86 code that I >> don't understand). You've implied that a sufficient knowledge of C >> would let someone understand your arguments, but part of what you're >> saying seems to depend on x86 assembly and/or machine code (which I'm >> not going to learn for the sake of this discussion). >> If I would need to understand x86 code to understand your claims, >> then >> let's just stop here. ========== REMAINDER OF ARTICLE TRUNCATED ==========