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.theory,sci.logic Subject: Re: Proof that H(D,D) meets its abort criteria Date: Fri, 15 Mar 2024 12:23:18 -0500 Organization: A noiseless patient Spider Lines: 78 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 15 Mar 2024 17:23:19 -0000 (UTC) Injection-Info: dont-email.me; posting-host="628c0b780d2c261756f82ddadd066eb3"; logging-data="2492725"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19R3BnoEX6OOEGi9XQsujeU" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:U4XBNusLn7hEkUB86S/CODuw9bA= In-Reply-To: Content-Language: en-US Bytes: 4480 On 3/15/2024 12:07 PM, immibis wrote: > On 15/03/24 17:20, olcott wrote: >> Best selling author of Theory of Computation textbooks: >> *Introduction To The Theory Of Computation 3RD, by sipser* >> https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295/ >> >> Date 10/13/2022 11:29:23 AM >> *MIT Professor Michael Sipser agreed this verbatim paragraph is correct* >> (He has neither reviewed nor agreed to anything else in this paper) >> (a) If simulating halt decider H correctly simulates its input D until >> H correctly determines that its simulated D would never stop running >> unless aborted then >> (b) H can abort its simulation of D and correctly report that D >> specifies a non-halting sequence of configurations. >> >> *When we apply the abort criteria* (elaborated above) >> Will you halt if you never abort your simulation? >> *Then H(D,D) is proven to meet this criteria* >> >> *Proof that H(D,D) meets its abort criteria* >> >> int D(int (*x)()) >> { >>    int Halt_Status = H(x, x); >>    if (Halt_Status) >>      HERE: goto HERE; >>    return Halt_Status; >> } >> >> int main() >> { >>    Output("Input_Halts = ", H(D,D)); >> } >> >>   machine   stack     stack     machine    assembly >>   address   address   data      code       language >>   ========  ========  ========  =========  ============= >> [00001d22][00102fc9][00000000] 55         push ebp      ; begin main() >> [00001d23][00102fc9][00000000] 8bec       mov ebp,esp >> [00001d25][00102fc5][00001cf2] 68f21c0000 push 00001cf2 ; push DD >> [00001d2a][00102fc1][00001cf2] 68f21c0000 push 00001cf2 ; push D >> [00001d2f][00102fbd][00001d34] e8eef7ffff call 00001522 ; call H(D,D) >> >> H: Begin Simulation   Execution Trace Stored at:113075 >> Address_of_H:1522 >> [00001cf2][00113061][00113065] 55         push ebp       ; enter D(D) >> [00001cf3][00113061][00113065] 8bec       mov ebp,esp >> [00001cf5][0011305d][00103031] 51         push ecx >> [00001cf6][0011305d][00103031] 8b4508     mov eax,[ebp+08] >> [00001cf9][00113059][00001cf2] 50         push eax       ; push D >> [00001cfa][00113059][00001cf2] 8b4d08     mov ecx,[ebp+08] >> [00001cfd][00113055][00001cf2] 51         push ecx       ; push D >> [00001cfe][00113051][00001d03] e81ff8ffff call 00001522  ; call H(D,D) >> H: Recursive Simulation Detected Simulation Stopped >>                            H(D,D) returns 0 to main() >> >> *That was proof that H(D,D) meets its abort criteria* >> H(D,D) correctly determines that itself is being called with its same >> inputs and there are no conditional branch instructions between the >> invocation of D(D) and its call to H(D,D). >> >> > > There are conditional branch instructions inside H(D,D). This is > obvious. Why do you keep lying? (a) If simulating halt decider H correctly simulates its input D until H correctly determines that its simulated D would never stop running unless aborted then It is true that D(D) would never stop running unless the outermost H(D,D) aborts its simulation thus meeting the above criteria. -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer