Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
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: <vvtpqu$1agqu$1@dont-email.me>
References: <vvte01$14pca$29@dont-email.me> <vvte62$15ceh$18@dont-email.me>
 <vvtej1$181kg$1@dont-email.me> <vvtjj8$15ceh$19@dont-email.me>
 <vvtl1g$19cvp$1@dont-email.me> <vvtlmm$15ceh$20@dont-email.me>
 <vvto7c$1a1pf$1@dont-email.me>
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: <vvto7c$1a1pf$1@dont-email.me>

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:
>>>>>>>
>>>>>>> <MIT Professor Sipser agreed to ONLY these verbatim words 
>>>>>>> 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.
>>>>>>>   </MIT Professor Sipser agreed to ONLY these verbatim words 
>>>>>>> 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.
>>>
>>> <MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
>>>      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 <X> with input Y:

A solution to the halting problem is an algorithm H that computes the 
following mapping:

(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly