Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail From: Richard Damon Newsgroups: comp.theory Subject: Re: Incorrect requirements --- Computing the mapping from the input to HHH(DD) Date: Fri, 9 May 2025 07:21:09 -0400 Organization: i2pn2 (i2pn.org) Message-ID: <1ffb883a3b414946707ff9cd9e09dcde21948764@i2pn2.org> References: <87msbmeo3b.fsf@nosuchdomain.example.com> <87a57mek8r.fsf@nosuchdomain.example.com> <87seled0zy.fsf@nosuchdomain.example.com> <87zffmbeyt.fsf@nosuchdomain.example.com> <87frhebbae.fsf@nosuchdomain.example.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 9 May 2025 11:25:37 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="3792716"; 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 On 5/9/25 1:49 AM, olcott wrote: > On 5/9/2025 12:31 AM, Keith Thompson wrote: >> 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. > > The "return" instruction marks the final halt state. Which just shows that you are not reading what he is saying. > The actual basis for halting: Reaching a Final Halt State > The halting problem proofs have very specific specific parameters. Which points out that you are not talking about the C language, but are just trying to abuse that connection. > >> >> 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 ========== REMAINDER OF ARTICLE TRUNCATED ==========