Path: ...!news.snarked.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: DDD simulated by HHH cannot possibly halt (Halting Problem)
Date: Tue, 8 Apr 2025 21:00:49 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <b09fcb5d7c869d00c6d599b6e9cf7ca58f17a56b@i2pn2.org>
References: <vsnchj$23nrb$2@dont-email.me> <vso4a5$302lq$1@dont-email.me>
 <vsqhuu$1hl94$2@dont-email.me> <vsqknb$1ldpa$1@dont-email.me>
 <vsrmn8$2o2f2$1@dont-email.me> <vstku7$p4u7$1@dont-email.me>
 <vsu95l$1c5kt$1@dont-email.me> <vt01l0$39kn7$1@dont-email.me>
 <vt28vk$1fe7a$1@dont-email.me> <vt2k6t$1onvt$1@dont-email.me>
 <vt3ef4$2flgf$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 9 Apr 2025 01:31:42 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3734740"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
X-Spam-Checker-Version: SpamAssassin 4.0.0
In-Reply-To: <vt3ef4$2flgf$1@dont-email.me>
Content-Language: en-US
Bytes: 5901
Lines: 140

On 4/8/25 11:13 AM, olcott wrote:
> On 4/8/2025 2:45 AM, Fred. Zwarts wrote:
>> Op 08.apr.2025 om 06:33 schreef olcott:
>>> On 4/7/2025 3:16 AM, Mikko wrote:
>>>> On 2025-04-06 16:12:36 +0000, olcott said:
>>>>
>>>>> On 4/6/2025 5:27 AM, Mikko wrote:
>>>>>> On 2025-04-05 16:45:28 +0000, olcott said:
>>>>>>
>>>>>>> On 4/5/2025 2:05 AM, Mikko wrote:
>>>>>>>> On 2025-04-05 06:18:06 +0000, olcott said:
>>>>>>>>
>>>>>>>>> On 4/4/2025 3:12 AM, Mikko wrote:
>>>>>>>>>> On 2025-04-04 01:27:15 +0000, olcott said:
>>>>>>>>>>
>>>>>>>>>>> void DDD()
>>>>>>>>>>> {
>>>>>>>>>>>     HHH(DDD);
>>>>>>>>>>>     return;
>>>>>>>>>>> }
>>>>>>>>>>>
>>>>>>>>>>> Do you really think that anyone knowing the C
>>>>>>>>>>> programming language is too stupid to see that
>>>>>>>>>>> DDD simulated by HHH cannot possibly return?
>>>>>>>>>>
>>>>>>>>>> Anyone knowing the C language can see that if DDD() does not halt
>>>>>>>>>> it means that HHH(DDD) does not halt. The knowledge that that
>>>>>>>>>> means that HHH is not a decider is possible but not required.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> *Perpetually ignoring this is not any actual rebuttal at all*
>>>>>>>>>
>>>>>>>>> *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.
>>>>>>>>
>>>>>>>> Wrong, because a termination analyzer is not required to halt.
>>>>>>>
>>>>>>> Why say things that you know are untrue?
>>>>>>
>>>>>> The term "termination analyzer" is used about programs that do not 
>>>>>> halt
>>>>>> on every input. There is no strict derfiniton of the term so there is
>>>>>> no requirement about halting.
>>>>>>
>>>>>> On the first page of https://www.cs.princeton.edu/~zkincaid/pub/ 
>>>>>> pldi21.pdf
>>>>>> in the first parapgraph of Introduction:
>>>>>>
>>>>>>    For example, termination analyzers may themselves fail to 
>>>>>> terminate on
>>>>>>    some input programs, or ...
>>>>>>
>>>>>>> A termination analyzer that doesn't halt
>>>>>>> would flunk every proof of total program correctness.
>>>>>>
>>>>>> There are no total termination analyzers.
>>>>>
>>>>> Total proof of correctness does not require a halt
>>>>> decider, it only requires a termination analyzer
>>>>> with inputs in its domain.
>>>>
>>>> Depends on what one wants to prove correct.
>>>>
>>>> Often there is no way to determine whether a pariticular termination
>>>> analyser can determine about a particular program.
>>>>
>>>
>>> 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);
>>> }
>>>
>>> *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.
>>
>>
>> In this case there is nothing to prevent, because the finite string 
>> specifies a program that halts. 
> 
> int DD()
> {
>    int Halt_Status = HHH(DD);
>    if (Halt_Status)
>      HERE: goto HERE;
>    return Halt_Status;
> }
> 
> This stuff is simply over-your-head.
> HHH(DD) meets the above: *Simulating termination analyzer Principle*
> Anyone with sufficient competence with the C programming language
> will understand this.
> 

NO, because either:

DD isn't a program, and thus HHH can't decide if it halts as it can't be 
simulated by a pure function, which you admit is a requirement for a 
proper decider, or

DD includes the code for the HHH that it calls, and thus the fact that 
this HHH *WILL* abort its simulation and return (since you claim that is 
what the outer simulating HHH, at the same memory address does) and thus 
HHH can't say that it DD doesn't halt by itself.

Note, you can't actually change the HHH at that address, or you are just 
admitting to changing the input, and thus admitting you are working on a 
strawman.

>> Olcott does not understand that. If the simulation would not stop, it 
>> would reach the end.
>>
>>>
>>> Rational minds would agree that the above principle
>>> is correct and directly applies to HHH(DD) rejecting
>>> its input.
>>>
>>
>> HHH correctly reports that it could not reach the end of the 
>> simulation of a halting program.
>>
> 
>