Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: "Fred. Zwarts" Newsgroups: comp.theory Subject: Re: Incorrect requirements --- Computing the mapping from the input to HHH(DD) Date: Sat, 10 May 2025 10:18:57 +0200 Organization: A noiseless patient Spider Lines: 132 Message-ID: References: <87msbmeo3b.fsf@nosuchdomain.example.com> <87ecwyekg2.fsf@nosuchdomain.example.com> <87bjs2cyj6.fsf@nosuchdomain.example.com> <87r00xchn5.fsf@nosuchdomain.example.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 10 May 2025 10:18:58 +0200 (CEST) Injection-Info: dont-email.me; posting-host="6132ef5c9a5712f5fb4e052234097a74"; logging-data="3603725"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19N3uYEe4FHi5W77Db7/Yep" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:l/aaG0v/t40hz7wku6jNYpJmfrM= Content-Language: nl, en-GB In-Reply-To: Op 10.mei.2025 om 05:13 schreef olcott: > On 5/9/2025 9:40 PM, 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). >> > > Yes and then I moved on the next tiny incremental> step of my proof. Correctly simulated less than > an infinite number of instructions does not help > the simulated DDD to reach its "return statement" > final halt state. The word 'tiny' is misleading. It is a fundamental change. Now HHH does no longer do a correct simulation, because it ignores the input part of the input that specifies that HHH simulates only a *finite* number of steps. > >> 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. > > Right this takes a glimmering of understanding of > the x86 language. The x86 language it needed to > get an exactly precise understanding of the control > flow of DDD as directed graph state transition > diagram. Yes and it takes into account that the input contains x86 instruction to abort and halt. > >> 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". > > No much more than this you acknowledged that > when DDD is correctly simulated by HHH that > the simulated DDD cannot possibly reach its > own "return statement" (final halt state) But when that HHH ignores an important part of its input, it is no longer correct. > > This is very important to computer science because > non-termination is entirely measured by the impossibility > of reaching a final halt state. > > From all of the we know that when HHH(DDD) reports > on the behavior of its correct simulation of its input > that it can correctly reject this input as not > specifying a sequence of configurations that halts. It can only report that it aborted the simulation prematurely, without analysing the full input.