Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.lang.c++,comp.lang.c Subject: D correctly simulated by H never halts Date: Mon, 27 May 2024 09:00:50 -0500 Organization: A noiseless patient Spider Lines: 173 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 27 May 2024 16:00:51 +0200 (CEST) Injection-Info: dont-email.me; posting-host="458305845cd025bf1a433877c96321fe"; logging-data="75565"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19IO/XaoIuch1CtjZCop3/q" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:F4Rv9IUhHbUQeyzT3tXh+c8YPDY= In-Reply-To: Content-Language: en-US Bytes: 8141 On 5/27/2024 3:57 AM, Fred. Zwarts wrote: > Op 26.mei.2024 om 17:42 schreef olcott: >> On 5/26/2024 9:43 AM, Fred. Zwarts wrote: >>> Op 26.mei.2024 om 15:20 schreef olcott: >>>> On 5/26/2024 6:01 AM, Fred. Zwarts wrote: >>>>> Op 26.mei.2024 om 06:19 schreef olcott: >>>>>> On 5/25/2024 2:32 AM, Fred. Zwarts wrote: >>>>>>> Op 23.mei.2024 om 18:52 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 >>>>>>>> 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. >>>>>>>> >>>>>>>> In the above case 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. >>>>>>>> >>>>>>> >>>>>>> Olcott's own words are that the simulation of D never reaches >>>>>>> past line 03. So the lines following line 03 do not play a role >>>>>>> and, therefore, can be removed without changing the claim. This >>>>>>> leads to: >>>>>>> >>>>>>> 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         return H(p, p); >>>>>>> 04       } >>>>>>> 05 >>>>>>> 06       int main() >>>>>>> 07       { >>>>>>> 08         H(D,D); >>>>>>> 09         return 0; >>>>>>> 10       } >>>>>>> >>>>>>> >>>>>>> What we see is that the only property of D that is used is that >>>>>>> it is a parameter duplicator. (Is that why it is called D?). H >>>>>>> needs 2 parameters, but it can be given only one input parameter, >>>>>>> so the parameter duplicator is required to allow H to decide >>>>>>> about itself. >>>>>>> >>>>>>> >>>>>>> >>>>>>> Of the infinite set of H that simulate at least one step, none of >>>>>>> them, when simulated by H, halts, because none of them reaches >>>>>>> its final state. Olcott's claim is equivalent to the claim of >>>>>>> non-halting behaviour of H. >>>>>>> This means that a simulating halt-decider is a bad idea, because >>>>>>> the decider itself does not halt. >>>>>> >>>>>> Not at all. >>>>>>     A simulator is an x86 emulator that correctly emulates 1 to N >>>>>> of the >>>>>>     x86 instructions of D in the order specified by the x86 >>>>>> instructions >>>>>>     of D. This may include M recursive emulations of H emulating >>>>>> itself >>>>>>     emulating D. >>>>>> >>>>>>     This means that D cannot possibly reach its own line 06 and halt >>>>>>     in any finite steps of correct simulation. H is free to halt at >>>>>>     any time after these N finite steps of correct simulation. >>>>>> >>>>>> >>>>> >>>>> D does not reach it own line 04 because the simulation of H does >>>>> not return to D. So, it shows that the simulation of H does not >>>>> reach it final state, which proves that H does not halt. >>>> >>>> Your transformation would have been acceptable if you retained the >>>> fact that H is a pure function that always halts and returns some >>>> value. >>>> >>> >>> Since H is required to halt, but H shows that H does not halt >>> (because the simulation of H never reaches its final state), the >>> conclusion must be that there is no such H. >> >>  > >> >> When D correctly simulated by pure simulator H remains stuck in infinite >> recursive simulation then we also know that D never reaches its own line >> 06 and halts in less than an infinite number of correctly simulated >> steps. >> >> This is what I had in mind all along. Because I am a relatively terrible >> communicator it takes me a very long time to translate my intuitions >> into simple words. >> >> > 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         return H(p, p); > 04       } > 05 > 06       int main() > 07       { > 08         H(D,D); > 09         return 0; > 10       } > > We see that the requirements for H are contradictory. *Not at all, I just did not explain us clearly enough* When we hypothesize that H is a pure simulator we see that D correctly simulated by pure simulator H remains stuck in recursive simulation thus never reaches its own simulated final state at its line 06 and halts. In this case H does not halt, thus is neither a pure function nor a decider. From this we correctly conclude that D correctly simulated by pure function H never reaches its simulated final state at its own line 06 and halts in Less than an infinite (AKA finite) number of simulated steps. Here is a concrete example of that: https://en.wikipedia.org/wiki/Googolplex When pure function H correctly simulates a Googolplex ^ Googolplex number of steps of D, then D never reaches its simulated final state at its own line 06 and halts. Pure function H halts after this finite number of steps of correct simulation. In other words when the *INPUT* to H(D,D) is correctly simulated by either pure simulator H or pure function H this correctly simulated *INPUT* never halts no matter what, thus the INPUT to H(D,D) is definitely non halting. *This is STEP ONE of my four step proof* -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer