Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: How the requirements that Professor Sipser agreed to are exactly met Date: Mon, 12 May 2025 17:39:41 -0400 Organization: A noiseless patient Spider Lines: 98 Message-ID: References:

MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 12 May 2025 23:39:42 +0200 (CEST) Injection-Info: dont-email.me; posting-host="d587ba6f088c47ed8fd2ad250ebfd646"; logging-data="1393502"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19vxtWtgkA0X23DAPZHjDhT" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:PPj3UC3HmHKFKD+BjzNNOx6j8vU= Content-Language: en-US In-Reply-To: On 5/12/2025 5:12 PM, olcott wrote: > On 5/12/2025 3:29 PM, dbush wrote: >> On 5/12/2025 4:17 PM, olcott wrote: >>> On 5/12/2025 2:53 PM, dbush wrote: >>>> On 5/12/2025 2:27 PM, olcott wrote: >>>>> On 5/12/2025 1:20 PM, dbush wrote: >>>>>> On 5/12/2025 2:17 PM, olcott wrote: >>>>>>> Introduction to the Theory of Computation 3rd Edition >>>>>>> by Michael Sipser (Author) >>>>>>> 4.4 out of 5 stars 568 rating >>>>>>> >>>>>>> https://www.amazon.com/Introduction-Theory-Computation-Michael- >>>>>>> Sipser/ dp/113318779X >>>>>>> >>>>>>> int DD() >>>>>>> { >>>>>>> int Halt_Status = HHH(DD); >>>>>>> if (Halt_Status) >>>>>>> HERE: goto HERE; >>>>>>> return Halt_Status; >>>>>>> } >>>>>>> >>>>>>> DD correctly simulated by any pure simulator >>>>>>> named HHH cannot possibly terminate thus proving >>>>>>> that this criteria has been met: >>>>>>> >>>>>>> >>>>>> 10/13/2022> >>>>>>> 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 >>>>>>> >>>>>>> H can abort its simulation of D and correctly report that D >>>>>>> specifies a non-halting sequence of configurations. >>>>>>> >>>>>> 10/13/2022> >>>>>>> >>>>>> >>>>>> Which is not what you thought he agreed to: >>>>>> >>>>>> >>>>>> On Monday, March 6, 2023 at 2:41:27 PM UTC-5, Ben Bacarisse wrote: >>>>>> > I exchanged emails with him about this. He does not agree with >>>>>> anything >>>>>> > substantive that PO has written. I won't quote him, as I don't >>>>>> have >>>>>> > permission, but he was, let's say... forthright, in his reply >>>>>> to me. >>>>>> >>>>> >>>>> *Ben already acknowledged that the requirements have been met* >>>>> >>>>> On 10/17/2022 10:23 AM, Ben Bacarisse wrote: >>>>> > ...D(D) would not halt unless H stops the simulation. >>>>> > H /can/ correctly determine this silly criterion (in this one >>>>> case)... >>>>> >>>>> >>>> >>>> Which is not what Sipser agreed to, as stated above. >>>> >>>> He agreed, as all others would, that H must determine if UTM(D) halts. >>> >>> That is not what Ben's words mean. >>> >>> On 10/14/2022 7:44 PM, Ben BacaFrisse wrote: >>> > I don't think that is the shell game. PO really /has/ an H >>> > (it's trivial to do for this one case) that correctly determines >>> > that P(P) *would* never stop running *unless* aborted. >>> >>> >>> H correctly determines that its simulated D >>> would never stop running unless aborted... >>> >>> *its simulated D* >>> >> >> Which Sipser (and everyone else) takes to mean UTM(D), > > *its simulated D* cannot be *correctly* understood > to mean a D simulated by anything else other than > a hypothetical H that never aborts. False. It cannot be *correctly* understood to be anything else but the algorithm D simulated completely by a UTM, because that is the only thing equivalent to direct execution which is what is being asked about: Given any algorithm (i.e. a fixed immutable sequence of instructions) X described as with input Y: A solution to the halting problem is an algorithm H that computes the following mapping: (,Y) maps to 1 if and only if X(Y) halts when executed directly (,Y) maps to 0 if and only if X(Y) does not halt when executed directly