Deutsch English Français Italiano |
<v2cqii$3cek2$2@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: immibis <news@immibis.com> Newsgroups: comp.theory,sci.logic Subject: Re: Can D simulated by H terminate normally? --- Message_ID Provided Date: Sun, 19 May 2024 14:16:17 +0200 Organization: A noiseless patient Spider Lines: 138 Message-ID: <v2cqii$3cek2$2@dont-email.me> References: <v0k4jc$laej$1@dont-email.me> <v0loq2$2g493$1@i2pn2.org> <v0lq7d$14579$2@dont-email.me> <v0ls98$2g492$7@i2pn2.org> <v0m29q$166o1$1@dont-email.me> <v0m37e$2gl1e$1@i2pn2.org> <v0m3v5$16k3h$1@dont-email.me> <v0m55t$2gl1f$3@i2pn2.org> <v0m5sn$172p4$1@dont-email.me> <v0m7em$2gl1f$5@i2pn2.org> <v0m7tq$17dpv$1@dont-email.me> <v0m8g9$2gl1e$6@i2pn2.org> <v0m978$17k7o$3@dont-email.me> <v0mko6$2hf3s$2@i2pn2.org> <v0n59h$1h98e$1@dont-email.me> <v0o037$2j1tu$3@i2pn2.org> <v0oc65$1q3aq$3@dont-email.me> <v0p9ts$2ki5r$6@i2pn2.org> <v0q1rk$2a3u1$1@dont-email.me> <v0qkti$2m1nf$1@i2pn2.org> <v0r4a3$2hb7o$6@dont-email.me> <v0rsbr$2m1nf$6@i2pn2.org> <v0segm$2v4oq$1@dont-email.me> <v0t8o9$2p3ri$2@i2pn2.org> <v0tpjf$3881i$5@dont-email.me> <v0ulma$2qov4$1@i2pn2.org> <v2b179$2u8oi$2@dont-email.me> <v2b1g3$1ct7p$17@i2pn2.org> <v2bb0g$308qd$1@dont-email.me> <v2bc8u$1ecj9$4@i2pn2.org> <v2bdaj$30o5r$1@dont-email.me> <v2be6g$1ecja$2@i2pn2.org> <v2btfr$36vvc$3@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sun, 19 May 2024 14:16:18 +0200 (CEST) Injection-Info: dont-email.me; posting-host="affc6b15e969cbfd037554ff7cd72692"; logging-data="3553922"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/Cwt/YsrOpk9/v27ZST5hj" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:rBr6pYLME1r/J9GFxatoPp4oCDc= Content-Language: en-US In-Reply-To: <v2btfr$36vvc$3@dont-email.me> Bytes: 6629 On 19/05/24 05:59, olcott wrote: > On 5/18/2024 6:38 PM, Richard Damon wrote: >> On 5/18/24 7:24 PM, olcott wrote: >>> On 5/18/2024 6:06 PM, Richard Damon wrote: >>>> On 5/18/24 6:44 PM, olcott wrote: >>>>> On 5/18/2024 3:02 PM, Richard Damon wrote: >>>>>> On 5/18/24 3:57 PM, olcott wrote: >>>>>>> On 5/1/2024 7:10 PM, Richard Damon wrote: >>>>>>>> The second method uses the fact that you have not restricted >>>>>>>> what H is allowed to do, and thus H can remember that it is >>>>>>>> simulating, and if a call to H shows that it is currently doing >>>>>>>> a simulation, just immediately return 0. >>>>>>> >>>>>>> Nice try but this has no effect on any D correctly simulated by H. >>>>>>> When the directly executed H aborts its simulation it only returns >>>>>>> to whatever directly executed it. >>>>>> >>>>>> Why? My H does correctly simulate the D it was given. >>>>>> >>>>>> You don't seem to understand how the C code actually works. >>>>>> >>>>>>> >>>>>>> If the directly executed outermost H does not abort then none of >>>>>>> the inner simulated ones abort because they are the exact same code. >>>>>>> When the directly executed outermost H does abort it can only return >>>>>>> to its own caller. >>>>>> >>>>>> WHAT inner simulatioin? >>>>>> >>>>>> >>>>>> My H begins as: >>>>>> >>>>>> int H(ptr x, ptr y) { >>>>>> static int flag = 0; >>>>>> if(flag) return 0; >>>>>> flag = 1; >>>>>> >>>>>> followed by essentially your code for H, except that you need to >>>>>> disable the hack that doesn't simulate the call to H, but just let >>>>>> it continue into H where it will immediately return to D and D >>>>>> will then return. >>>>>> >>>>>> >>>>>> Thus, your claim is shown to be wrong. >>>>>> >>>>> >>>>> We are talking about every element of an infinite set where >>>>> H correctly simulates 1 to ∞ steps of D thus including 0 to ∞ >>>>> recursive simulations of H simulating itself simulating D. >>>>> >>>>> *At whatever point the directly executed H(D,D) stops simulating* >>>>> *its input it cannot possibly return to any simulated input* >>>> >>>> And my H never stops simulating, so that doesn't apply. It will >>>> reach the final state. >>> >>> *Show the error in my execution trace that I empirically* >>> *proved has no error by H correctly simulating D to the* >>> *point where H correctly simulates itself simulating D* >>> (Fully operational empirically code proved this) >> >> See below: >> >> >>> >>> typedef int (*ptr)(); // ptr is pointer to int function >>> 00 int H(ptr x, ptr y); >>> 01 int D(ptr x) >>> 02 { >>> 03 int Halt_Status = H(x, x); >>> 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 } >> >> For Reference >> >> 14 int H(ptr x, ptr y) >> 15 { >> 16 static int flag = 0 >> 17 if (flag) >> 18 return 0 >> 19 ... continuation of H that simulates its input >> >>> >>> 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); >>> >>> keeps repeating (unless aborted) >>> Line 01 >>> Line 02 >>> Line 03: simulated D(D) invokes simulated H(D,D) that simulates D(D) >> >> Line 03: Calls H (line 14) >> Line 16: Static already inited, so not changed. >> Line 17: Flag is 1, so >> Line 18: Return 0 >> Line 03: Set Halt_Status to 0 >> Line 04: if (Halt_Status) halts status is 0, so skip >> Line 06: return Halt_Status >> >> Simulation completed, program halted. >> >> >>> >>> Simulation invariant: >>> D correctly simulated by H cannot possibly reach past its own line 03. >>> >>> >> >> Nope. Not for this H >> >> > > (a) That idea might work yet you did not say it correctly. > For example line 11 is the first one invoked. > (b) Computable functions cannot alter their behavior this way. > > (1) the function return values are identical for identical arguments (no > variation with local static variables, non-local variables, mutable > reference arguments or input streams, i.e., referential transparency), and Your function H works like Richard's function H. You just called the variable "execution trace" instead of "flag".