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 D simulated by H terminate normally? --- Message_ID Provided Date: Mon, 20 May 2024 20:57:39 -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: Tue, 21 May 2024 00:57:39 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="1722705"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird Content-Language: en-US In-Reply-To: X-Spam-Checker-Version: SpamAssassin 4.0.0 Bytes: 10980 Lines: 234 On 5/20/24 2:17 PM, olcott wrote: > On 5/20/2024 6:24 AM, Richard Damon wrote: >> On 5/20/24 1:17 AM, olcott wrote: >>> On 5/19/2024 11:37 PM, immibis wrote: >>>> On 19/05/24 15:06, olcott wrote: >>>>> On 5/19/2024 7:16 AM, immibis wrote: >>>>>> 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". >>>>> >>>>> pages 4-5 (of a paper that I published 2021-09-26 09:39 AM) >>>>> Show H simulating P and H simulating itself simulating P. >>>>> >>>>> The 395 pages of the execution trace of the simulated H are >>>>> screened out. No one here could ever understand the half page >>>>> trace so embedding that in 395 more pages would not help. ========== REMAINDER OF ARTICLE TRUNCATED ==========