Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: Incorrect requirements --- Computing the mapping from the input to HHH(DD) Date: Sat, 10 May 2025 08:36:15 -0400 Organization: A noiseless patient Spider Lines: 189 Message-ID: References: <87msbmeo3b.fsf@nosuchdomain.example.com> <87ecwyekg2.fsf@nosuchdomain.example.com> <87bjs2cyj6.fsf@nosuchdomain.example.com> <87r00xchn5.fsf@nosuchdomain.example.com> <23a27379d226b7b3b9f8c303a492f66edc9019ff.camel@gmail.com> <1020d30c2c5b5a7cce584777131d5ce414b480ea.camel@gmail.com> <0323d5ca6d757a1e35d7e4cf5eb4fc8f41bc866a.camel@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 10 May 2025 14:36:15 +0200 (CEST) Injection-Info: dont-email.me; posting-host="ceabab99a32dd3b60042c0bcdabf6faa"; logging-data="3715402"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19AVRy5HTngPUYDovetX58j" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:ezFniOsF8B6dsF6f0eRDB+UKydE= In-Reply-To: Content-Language: en-US On 5/10/2025 1:06 AM, olcott wrote: > On 5/9/2025 11:51 PM, wij wrote: >> On Fri, 2025-05-09 at 23:44 -0500, olcott wrote: >>> On 5/9/2025 11:32 PM, wij wrote: >>>> On Fri, 2025-05-09 at 23:18 -0500, olcott wrote: >>>>> On 5/9/2025 10:43 PM, wij wrote: >>>>>> On Fri, 2025-05-09 at 22:24 -0500, olcott wrote: >>>>>>> On 5/9/2025 10:13 PM, wij wrote: >>>>>>>> On Fri, 2025-05-09 at 19:40 -0700, Keith Thompson wrote: >>>>>>>>> olcott writes: >>>>>>>>>> On 5/9/2025 4:40 PM, Richard Heathfield wrote: >>>>>>>>>>> On 09/05/2025 21:15, olcott wrote: >>>>>>>>>>>> On 5/9/2025 3:07 PM, Richard Heathfield wrote: >>>>>>>>>>>>> On 09/05/2025 20:46, olcott wrote: >>>>>>>>>>>>>> We have not begun to get into any of those points. >>>>>>>>>>>>>> We are only asking can DDD correctly simulated >>>>>>>>>>>>>> by any HHH that can exist ever reach its own >>>>>>>>>>>>>> "return" instruction. >>>>>>>>>>>>> >>>>>>>>>>>>> DDD can't be correctly simulated by itself (which is >>>>>>>>>>>>> effectively >>>>>>>>>>>>> what you're trying to do when you fire up the simulation from >>>>>>>>>>>>> inside DDD). >>>>>>>>>>>> >>>>>>>>>>>> How the Hell did you twist my words to say that? >>>>>>>>>>> I haven't touched your words. What I have done is to observe >>>>>>>>>>> that >>>>>>>>>>> DDD's /only/ action is to call a simulator. Since DDD isn't >>>>>>>>>>> itself a >>>>>>>>>>> simulator, there is nothing to simulate except a call to a >>>>>>>>>>> simulator. >>>>>>>>>>> It's recursion without a base case - a rookie error. >>>>>>>>>>> HHH cannot successfully complete its task, because it never >>>>>>>>>>> regains >>>>>>>>>>> control after the first recursion. To return, it must abort the >>>>>>>>>>> simulation, which means the simulation fails. >>>>>>>>>>> >>>>>>>>>>>> void DDD() >>>>>>>>>>>> { >>>>>>>>>>>>        HHH(DDD); >>>>>>>>>>>>        return; >>>>>>>>>>>> } >>>>>>>>>>>> >>>>>>>>>>>> When 1 or more statements of DDD are correctly >>>>>>>>>>>> simulated by HHH then this correctly simulated >>>>>>>>>>>> DDD cannot possibly reach its own “return statement”. >>>>>>>>>>> On what grounds can you persuade an extraordinarily sceptical >>>>>>>>>>> readership that HHH 'correctly simulated' DDD? >>>>>>>>>> >>>>>>>>>> Any competent C programmer can see that >>>>>>>>>> the call from DDD to HHH(DDD) (its own simulator) >>>>>>>>>> is equivalent to infinite recursion. >>>>>>>>>> >>>>>>>>>> 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. >>>>>>>>> >>>>>>>>> I had not intended to post again, but I feel the need to make >>>>>>>>> a clarification. >>>>>>>>> >>>>>>>>> I acknowledged that the return statement would never be reached >>>>>>>>> *given the assumption* that HHH correctly simulates DDD.  Given >>>>>>>>> that assumption, a call to DDD() should be equivalent to a call >>>>>>>>> to HHH(DDD). >>>>>>>>> >>>>>>>>> I did not address whether the assumption is valid.  I merely >>>>>>>>> temporarily accepted it for the sake of discussion, just as I >>>>>>>>> would >>>>>>>>> accept that if I were ten feet tall I would bump my head against >>>>>>>>> the ceiling in my house. >>>>>>>>> >>>>>>>>> The discussion I had with olcott did not reach the point of >>>>>>>>> discussing *how* HHH could correctly simulate DDD, or whether it >>>>>>>>> would even be logically possible for it to do so.  I also did not >>>>>>>>> address any issues of partial simulation, where olcott claims that >>>>>>>>> HHH can "accurately simulate" only a few x86 instructions rather >>>>>>>>> than simulating its entire execution.  I did not participate in >>>>>>>>> any discussion that would require knowledge of x86 machine or >>>>>>>>> assembly code.  (I have no doubt that I could learn x86 machine >>>>>>>>> and assembly code reasonably well if motivated to do so, but I am >>>>>>>>> not so motivated.) >>>>>>>>> >>>>>>>>> What I acknowledged was barely more than "if HHH correctly >>>>>>>>> simulates >>>>>>>>> DDD, then HHH correctly simulates DDD".  (My understanding from >>>>>>>>> posts by others, whom I presume to be sufficiently knowledgeable, >>>>>>>>> is that HHH logically cannot accurately simulate DDD.)  I would >>>>>>>>> prefer that olcott refrain from using my words to support any of >>>>>>>>> his arguments beyond the scope of what he and I directly >>>>>>>>> discussed. >>>>>>>> >>>>>>>> Don't know why you people stick on the 'simulation' stuff so long. >>>>>>>> The HP simply asks for such an H (in function form. POOH does not >>>>>>>> resemble TM): >>>>>>>>      H(D)=1 if D() halt. >>>>>>>>      H(D)=0 if D() not halt. >>>>>>> >>>>>>> My invention of a simulating termination >>>>>>> analyzer shows exactly how to compute the >>>>>>> mapping that the input that HHH(DD) specifies >>>>>>> into a correct answer for the halting problem's >>>>>>> otherwise impossible input. >>>>>>> >>>>>>> All rebuttals are based on failing to compute >>>>>>> this mapping correctly. >>>>>>> >>>>>> >>>>>> What is the correct mapping? >>>>>> >>>>> >>>>> _DDD() >>>>> [00002172] 55         push ebp      ; housekeeping >>>>> [00002173] 8bec       mov ebp,esp   ; housekeeping >>>>> [00002175] 6872210000 push 00002172 ; push DDD >>>>> [0000217a] e853f4ffff call 000015d2 ; call HHH(DDD) >>>>> [0000217f] 83c404     add esp,+04 >>>>> [00002182] 5d         pop ebp >>>>> [00002183] c3         ret >>>>> Size in bytes:(0018) [00002183] >>>>> >>>>> Computing the mapping of DDD emulated by HHH >>>>> according the the rules of the x86 language >>>>> to its behavior by HHH actually emulating DDD. >>>> >>>> The above says you have no idea what the mapping is. >>>> >>>>>> If POOH are not talking about the mapping: >>>>>> >>>>>>      H(D)=1 if D() halt. >>>>>>      H(D)=0 if D() not halt. >>>>>> >>>>> >>>>> The way that simulating termination analyzers process >>>>> their input by showing all of the steps of how the mapping >>>>> must be computed refutes the above simplistic view. >>>> >>>> No (real) problem with that. But the HP asks: >>>> >>>> H(D)=1 if D() halt. >>>> H(D)=0 if D() not halt. >>>> >>>> You still evade the question: Is POO H anything to do with the HP? >>>> >>> >>> I have recently proven that the above requirements are incorrect. >> it that correct? ========== REMAINDER OF ARTICLE TRUNCATED ==========