Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail From: Richard Damon Newsgroups: comp.theory,sci.logic Subject: Re: Can you see that D correctly simulated by H remains stuck in recursive simulation? Date: Fri, 24 May 2024 19:20:58 -0400 Organization: i2pn2 (i2pn.org) Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 24 May 2024 23:20:58 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="2076346"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird Content-Language: en-US X-Spam-Checker-Version: SpamAssassin 4.0.0 In-Reply-To: Bytes: 6694 Lines: 125 On 5/24/24 6:20 PM, olcott wrote: > On 5/24/2024 4:39 PM, olcott wrote: >> On 5/24/2024 4:03 PM, Richard Damon wrote: >>> On 5/24/24 4:01 PM, olcott wrote: >>>> On 5/24/2024 12:25 PM, Richard Damon wrote: >>>>> On 5/24/24 1:10 PM, olcott wrote: >>>>>> On 5/24/2024 2:37 AM, Fred. Zwarts wrote: >>>>>>> Op 23.mei.2024 om 19:04 schreef olcott: >>>>>>>> typedef int (*ptr)();  // ptr is pointer to int function in C >>>>>>>> 00       int H(ptr p, ptr i); >>>>>>>> 01       int D(ptr p) >>>>>>>> 02       { >>>>>>>> 03         int Halt_Status = H(p, p); >>>>>>>> 04         if (Halt_Status) >>>>>>>> 05           HERE: goto HERE; >>>>>>>> 06         return Halt_Status; >>>>>>>> 07       } >>>>>>>> 08 >>>>>>>> 09       int main() >>>>>>>> 10       { >>>>>>>> 11         H(D,D); >>>>>>>> 12         return 0; >>>>>>>> 13       } >>>>>>>> >>>>>>>> The above template refers to an infinite set of H/D pairs where >>>>>>>> D is >>>>>>>> correctly simulated by pure function H. This was done because many >>>>>>>> reviewers used the shell game ploy to endlessly switch which H/D >>>>>>>> pair >>>>>>>> was being referred to. >>>>>>>> >>>>>>>> *Correct Simulation Defined* >>>>>>>>     This is provided because every reviewer had a different >>>>>>>> notion of >>>>>>>>     correct simulation that diverges from this notion. >>>>>>>> >>>>>>>>     A simulator is an x86 emulator that correctly emulates at >>>>>>>> least one >>>>>>>>     of the x86 instructions of D in the order specified by the x86 >>>>>>>>     instructions of D. >>>>>>>> >>>>>>>>     This may include correctly emulating the x86 instructions of >>>>>>>> H in >>>>>>>>     the order specified by the x86 instructions of H thus >>>>>>>> calling H(D,D) >>>>>>>>     in recursive simulation. >>>>>>>> >>>>>>>> *Execution Trace* >>>>>>>>     Line 11: main() invokes H(D,D); H(D,D) simulates lines 01, >>>>>>>> 02, and 03 >>>>>>>>     of D. This invokes H(D,D) again to repeat the process in >>>>>>>> endless >>>>>>>>     recursive simulation. >>>>>>>> >>>>>>> >>>>>>> Of course this depends very much on the exact meaning of 'correct >>>>>>> simulation', or 'correctly emulating'. >>>>>> >>>>>> Not when these are defined above. >>>>>> >>>>>>> E.g., take the call to H(p, p). If H recognizes that it is a call >>>>>>> to a H with the same algorithm as is it using itself, and it >>>>>>> knows that itself returns a certain integer value K, than it can >>>>>>> be argued that it is a correct emulation to substitute the call >>>>>>> to H with this integer value K, which is assigned to Halt_Status. >>>>>>> Then the simulation of D can proceed to line 04. >>>>>>> What we need is an exact definition of 'correct simulation', in this >>>>>> >>>>>> No, you simply need to pay complete attention to the fact that this >>>>>> has already been provided. >>>>>> >>>>>> I have been over the exact same issue with dozens and dozen of people >>>>>> though hundreds and hundreds of messages over two years. >>>>> >>>>> Excpet that we have two contradictory definitions present, >>>> >>>> Yes you have a definition of simulation where the x86 machine >>>> language of D is simulated incorrectly or in the wrong order. >>> >>> Nope. The UTM definition still simulates EVERY x86 machine language >>> instruction of D simulated correctly in the exact order. The added >>> requirement is that we look at a simulation that is never aborted. >> >> H is a pure function that always returns 56 at some point other >> than that H is isomorphic to a UTM. >> > > I have learned from decades as a software engineer that complexity > is only manageable when it is isolated and minimized. > > It is impossible to correctly understand termination analyzer H until > after one first has 100% perfectly complete and total understanding of > pure function simulator H/D pairs. > So, do you agree with my comments about what you actual definitons are, and what they imply? That you H, by just needing to be a "Pure Funtion" is not necessarily the computatinal eqivalent of a Turing Machine. That your definition of "Correct Simulation" differs from that used in Computation Theory, and thus the fact that H does abort its simulation means it is NOT a "UTM equivalent" and that your aborted correct simulation not reaching a final state is not =, by itself, proof that the machine represented by the input is non-halting. That you definition of "Correct Simulation" means that H actually simulated a call to H by going into H and looking at those instructions, and not switch to looking at the machine the simulation being simulated is simulating. I will also add, that you agree that if you get the agreement that if H can do this, then you will produce an actual H that meets the requirements, and not just claim that it must be trivial to write, and such example program actually gives the claimed answer. You agree that your funky "Infinite set of H/D pairs" is NOT what Linz or Sipser were using in their proof, and that you H and D are not built fully in conformance to the sample machines in the proofs. If you don't agree to these interpreations, a necessary precondition to coming to an agreement on what H sees, is to reach the agreement on what hte conditions imply and what those conditions actually are.