Deutsch English Français Italiano |
<ut24hv$2dnbk$1@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: Proof that H(D,D) meets its abort criteria Date: Fri, 15 Mar 2024 19:37:51 +0100 Organization: A noiseless patient Spider Lines: 78 Message-ID: <ut24hv$2dnbk$1@dont-email.me> References: <ut1sgk$2buev$2@dont-email.me> <ut1v81$2cfjp$3@dont-email.me> <ut2067$2c29l$19@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 15 Mar 2024 18:37:51 -0000 (UTC) Injection-Info: dont-email.me; posting-host="915653ff9a2abee92136c653333d21b4"; logging-data="2547060"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+Ml6WVtR8XKVYBTHsfIxJM" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:tZ47a0iye9VRNkZm+mxeZ7S79Rk= In-Reply-To: <ut2067$2c29l$19@dont-email.me> Content-Language: en-US Bytes: 4611 On 15/03/24 18:23, olcott wrote: > 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. > It is true that D(D) would never stop running unless the SIMULATED H(D,D) aborts its simulation or does not run a simulation or the simulation halts.