Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: Why I need to cross-post to comp.lang.c --- CORRECTLY REFUTED Date: Mon, 12 May 2025 10:45:24 +0300 Organization: - Lines: 113 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 12 May 2025 09:45:25 +0200 (CEST) Injection-Info: dont-email.me; posting-host="d66022cf12555db523e1c5ad57a06eab"; logging-data="1046587"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18o199dgFc/Y2Y+Inf4iuhe" User-Agent: Unison/2.2 Cancel-Lock: sha1:1LwhYD3AO8ZVagDisnUovc0LWmE= On 2025-05-11 16:03:29 +0000, olcott said: > On 5/11/2025 4:12 AM, Mikko wrote: >> On 2025-05-10 15:13:32 +0000, olcott said: >> >>> On 5/10/2025 2:15 AM, Mikko wrote: >>>> On 2025-05-09 03:01:40 +0000, olcott said: >>>> >>>>> On 5/8/2025 9:23 PM, Keith Thompson wrote: >>>>>> Richard Damon writes: >>>>>>> On 5/8/25 7:53 PM, olcott wrote: >>>>>> [...] >>>>>>>> void DDD() >>>>>>>> { >>>>>>>>   HHH(DDD); >>>>>>>>   return; >>>>>>>> } >>>>>>>> We don't need to look at any of my code for me >>>>>>>> to totally prove my point. For example when >>>>>>>> the above DDD is correctly simulated by HHH >>>>>>>> this simulated DDD cannot possibly reach its own >>>>>>>> "return" instruction. >>>>>>> >>>>>>> And thus not correctly simulatd. >>>>>>> >>>>>>> Sorry, there is no "OS Exemption" to correct simulaiton;. >>>>>> >>>>>> Perhaps I've missed something.  I don't see anything in the above that >>>>>> implies that HHH does not correctly simulate DDD.  Richard, you've read >>>>>> far more of olcott's posts than I have, so perhaps you can clarify. >>>>>> >>>>>> If we assume that HHH correctly simulates DDD, then the above code is >>>>>> equivalent to: >>>>>> >>>>>> void DDD() >>>>>> { >>>>>> DDD(); >>>>>> return; >>>>>> } >>>>>> >>>>>> which is a trivial case of infinite recursion.  As far as I can tell, >>>>>> assuming that DDD() is actually called at some point, neither the >>>>>> outer execution of DDD nor the nested (simulated) execution of DDD >>>>>> can reach the return statement.  Infinite recursion might either >>>>>> cause a stack overflow and a probable program crash, or an unending >>>>>> loop if the compiler implements tail call optimization. >>>>>> >>>>>> I see no contradiction, just an uninteresting case of infinite >>>>>> recursion, something that's well understood by anyone with a >>>>>> reasonable level of programming experience.  (And it has nothing to >>>>>> do with the halting problem as far as I can tell, though of course >>>>>> olcott has discussed the halting problem elsewhere.) >>>>>> >>>>>> Richard, what am I missing? >>>>>> >>>>> ***** >>>>> Now you are seeing what I was talking about. >>>>> Now you are seeing why I needed to cross post >>>>> to comp.lang.c >>>> >>>> What were you told in comp.lang.c that you were not told in comp.theory? >>> >>> void DDD() >>> { >>>    HHH(DDD); >>>    return; >>> } >>> >>> People quickly realize that when DDD is correctly >>> simulated by HHH that DDD cannot possibly reach >>> its "return" statement (final halt state). >>> >>> Once you know this then you can see that the >>> same thing applies to DD. >>> >>> int DD() >>> { >>>    int Halt_Status = HHH(DD); >>>    if (Halt_Status) >>>      HERE: goto HERE; >>>    return Halt_Status; >>> } >>> >>> Once you know this then you know that the halting >>> problem's otherwise "impossible" input is non-halting. >>> >>> Once you know this then you know that the halting >>> problem proof has been correctly refuted. >> >> You are lying again. Nothing above was told you in comp.lang.c. > > On 5/8/2025 8:30 PM, Keith Thompson wrote: > > 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; > > } > > > > Then the return statement (which is unnecessary anyway) will never be > > reached. 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. > > What he says is true. However, the assumptions that HHH does a correct simulation and that it does nothing else are not. -- Mikko