Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: wij Newsgroups: comp.theory Subject: Re: Incorrect requirements --- Computing the mapping from the input to HHH(DD) Date: Sat, 10 May 2025 12:51:21 +0800 Organization: A noiseless patient Spider Lines: 209 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" Content-Transfer-Encoding: quoted-printable Injection-Date: Sat, 10 May 2025 06:51:25 +0200 (CEST) Injection-Info: dont-email.me; posting-host="c665478d8699930ce63ac26f3a79e21a"; logging-data="3518251"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+kBkoQEibl88lvvEnvifBe" User-Agent: Evolution 3.54.3 (3.54.3-1.fc41) Cancel-Lock: sha1:cqwhep+wk04fO98DQ6LPHFE5ggw= In-Reply-To: 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. > > > > > > > > > > >=20 > > > > > > > > > > > DDD can't be correctly simulated by itself (which is = effectively > > > > > > > > > > > what you're trying to do when you fire up the simulat= ion from > > > > > > > > > > > inside DDD). > > > > > > > > > >=20 > > > > > > > > > > How the Hell did you twist my words to say that? > > > > > > > > > I haven't touched your words. What I have done is to obse= rve 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 nev= er regains > > > > > > > > > control after the first recursion. To return, it must abo= rt the > > > > > > > > > simulation, which means the simulation fails. > > > > > > > > >=20 > > > > > > > > > > void DDD() > > > > > > > > > > { > > > > > > > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 HHH(DDD); > > > > > > > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return; > > > > > > > > > > } > > > > > > > > > >=20 > > > > > > > > > > When 1 or more statements of DDD are correctly > > > > > > > > > > simulated by HHH then this correctly simulated > > > > > > > > > > DDD cannot possibly reach its own =E2=80=9Creturn state= ment=E2=80=9D. > > > > > > > > > On what grounds can you persuade an extraordinarily scept= ical > > > > > > > > > readership that HHH 'correctly simulated' DDD? > > > > > > > >=20 > > > > > > > > Any competent C programmer can see that > > > > > > > > the call from DDD to HHH(DDD) (its own simulator) > > > > > > > > is equivalent to infinite recursion. > > > > > > > >=20 > > > > > > > > On 5/8/2025 8:30 PM, Keith Thompson wrote: > > > > > > > > > Assuming that HHH(DDD) "correctly simulates" DDD, and ass= uming it > > > > > > > > > does nothing else, your code would be equivalent to this: > > > > > > > > >=20 > > > > > > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 void DDD(void)= { > > > > > > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0 DDD(); > > > > > > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0 return; > > > > > > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 } > > > > > > > > >=20 > > > > > > > > > Then the return statement (which is unnecessary anyway) w= ill never be > > > > > > > > > reached.=C2=A0 In practice, the program will likely crash= due to a stack > > > > > > > > > overflow, unless the compiler implements tail-call optimi= zation, in > > > > > > > > > which case the program might just run forever -- which al= so means the > > > > > > > > > unnecessary return statement will never be reached. > > > > > > >=20 > > > > > > > I had not intended to post again, but I feel the need to make > > > > > > > a clarification. > > > > > > >=20 > > > > > > > I acknowledged that the return statement would never be reach= ed > > > > > > > *given the assumption* that HHH correctly simulates DDD.=C2= =A0 Given > > > > > > > that assumption, a call to DDD() should be equivalent to a ca= ll > > > > > > > to HHH(DDD). > > > > > > >=20 > > > > > > > I did not address whether the assumption is valid.=C2=A0 I me= rely > > > > > > > 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 agai= nst > > > > > > > the ceiling in my house. > > > > > > >=20 > > > > > > > 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.=C2=A0 I als= o did not > > > > > > > address any issues of partial simulation, where olcott claims= that > > > > > > > HHH can "accurately simulate" only a few x86 instructions rat= her > > > > > > > than simulating its entire execution.=C2=A0 I did not partici= pate in > > > > > > > any discussion that would require knowledge of x86 machine or > > > > > > > assembly code.=C2=A0 (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.) > > > > > > >=20 > > > > > > > What I acknowledged was barely more than "if HHH correctly si= mulates > > > > > > > DDD, then HHH correctly simulates DDD".=C2=A0 (My understandi= ng from > > > > > > > posts by others, whom I presume to be sufficiently knowledgea= ble, > > > > > > > is that HHH logically cannot accurately simulate DDD.)=C2=A0 = 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 disc= ussed. > > > > > >=20 > > > > > > Don't know why you people stick on the 'simulation' stuff so lo= ng. > > > > > > The HP simply asks for such an H (in function form. POOH does n= ot > > > > > > resemble TM): > > > > > > =C2=A0=C2=A0=C2=A0 H(D)=3D1 if D() halt. > > > > > > =C2=A0=C2=A0=C2=A0 H(D)=3D0 if D() not halt. > > > > >=20 > > > > > 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. > > > > >=20 > > > > > All rebuttals are based on failing to compute > > > > > this mapping correctly. > > > > >=20 > > > >=20 > > > > What is the correct mapping? > > > >=20 > > >=20 > > > _DDD() > > > [00002172] 55=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 push eb= p=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ; housekeeping > > > [00002173] 8bec=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 mov ebp,esp=C2=A0= =C2=A0 ; housekeeping > > > [00002175] 6872210000 push 00002172 ; push DDD > > > [0000217a] e853f4ffff call 000015d2 ; call HHH(DDD) > > > [0000217f] 83c404=C2=A0=C2=A0=C2=A0=C2=A0 add esp,+04 > > > [00002182] 5d=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 pop ebp > > > [00002183] c3=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ret > > > Size in bytes:(0018) [00002183] > > >=20 > > > Computing the mapping of DDD emulated by HHH ========== REMAINDER OF ARTICLE TRUNCATED ==========