Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: DD simulated by HHH cannot possibly halt (Halting Problem)
Date: Sat, 5 Apr 2025 16:38:02 -0500
Organization: A noiseless patient Spider
Lines: 92
Message-ID: <vss7rq$375du$9@dont-email.me>
References: <vsnchj$23nrb$2@dont-email.me> <vsngo6$26agq$1@dont-email.me>
 <vsnh44$26c94$3@dont-email.me> <vsnht7$26agq$2@dont-email.me>
 <vsnlvv$2h8pt$1@dont-email.me> <vsnnb5$2g4cd$2@dont-email.me>
 <vsnnug$2h8pt$2@dont-email.me> <vsnou2$2g4cd$5@dont-email.me>
 <vspqmt$o89d$1@dont-email.me> <vsq97g$19eo9$1@dont-email.me>
 <vsqhov$1hl94$1@dont-email.me> <vsqmth$1mglg$2@dont-email.me>
 <vsrk17$2le7u$1@dont-email.me> <vsrlh7$2n0kg$1@dont-email.me>
 <vsrpr2$2r7hk$1@dont-email.me> <vss6bi$389d8$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 05 Apr 2025 23:38:03 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="553bf603fba0ab686689915e3400961c";
	logging-data="3380670"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+Nir/Hf0JqiRGOPKE8DfM2"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:XjnemTJn8T1z0tBWki6b9fR9K1E=
X-Antivirus-Status: Clean
Content-Language: en-US
X-Antivirus: Norton (VPS 250405-6, 4/5/2025), Outbound message
In-Reply-To: <vss6bi$389d8$1@dont-email.me>
Bytes: 5030

On 4/5/2025 4:12 PM, dbush wrote:
> On 4/5/2025 1:38 PM, olcott wrote:
>> On 4/5/2025 11:25 AM, dbush wrote:
>>> On 4/5/2025 11:59 AM, olcott wrote:
>>>> On 4/5/2025 2:42 AM, Richard Heathfield wrote:
>>>>> On 05/04/2025 07:14, olcott wrote:
>>>>>> On 4/4/2025 10:49 PM, Richard Heathfield wrote:
>>>>>>> On 05/04/2025 00:41, olcott wrote:
>>>>>>>> *Simulating termination analyzer Principle*
>>>>>>>> It is always correct for any simulating termination
>>>>>>>> analyzer to stop simulating and reject any input that
>>>>>>>> would otherwise prevent its own termination. The
>>>>>>>> only rebuttal to this is rejecting the notion that
>>>>>>>> deciders must always halt.
>>>>>>>
>>>>>>
>>>>>> typedef void (*ptr)();
>>>>>> int HHH(ptr P);
>>>>>>
>>>>>> int DD()
>>>>>> {
>>>>>>    int Halt_Status = HHH(DD);
>>>>>>    if (Halt_Status)
>>>>>>      HERE: goto HERE;
>>>>>>    return Halt_Status;
>>>>>> }
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>>    HHH(DD);
>>>>>> }
>>>>>>
>>>>>>> In other words, you operate on the principle that deciders don't 
>>>>>>> have to (and indeed can't) always make a correct decision on 
>>>>>>> whether an input program halts.
>>>>>>>
>>>>>>
>>>>>> The termination analyzer HHH would be correct
>>>>>> to determine that it must stop simulating DD to
>>>>>> prevent its own non-termination
>>>>>
>>>>> Fine, but then it fails to do its job. What you are learning 
>>>>> (albeit slowly) is that the termination analyser HHH can't analyse 
>>>>> whether DD terminates. It is therefore not a general purpose 
>>>>> termination analyser.
>>>>>
>>>>
>>>> Introduction to the Theory of Computation 3rd Edition
>>>> by Michael Sipser (Author) (best selling textbook)
>>>>
>>>> <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>
>>>
>>> But not what you think he agreed to:
>>>
>>
>> Paraphrased as this:
>>
>> *Simulating termination analyzer Principle*
>> It is always correct for any simulating termination
>> analyzer to stop simulating and reject any input that
>> would otherwise prevent its own termination. The
>> only rebuttal to this is rejecting the notion that
>> deciders must always halt.
>>
> 
> Which Sipser doesn't agree with:
> 
> 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.
>  >
> 

That was long before I formulated the
*Simulating termination analyzer Principle*

Of course it would be obvious that professor Sipser
would not agree that I defeated the halting problem
proofs prior to seeing and fully understanding the
above paraphrase: *Simulating termination analyzer Principle*

-- 
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer