Path: ...!eternal-september.org!feeder3.eternal-september.org!i2pn.org!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: Mon, 7 Apr 2025 06:51:35 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <5f02e42cab16cdc56b3aedb3d12649417ad54172@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>
 <35492cbd39104f784a92c0afc366d73e39d34ea8@i2pn2.org>
 <vsvk8o$2r125$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 7 Apr 2025 10:51:35 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3503691"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <vsvk8o$2r125$2@dont-email.me>
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 4600
Lines: 89

On 4/7/25 12:28 AM, olcott wrote:
> On 4/6/2025 11:25 AM, Richard Damon wrote:
>> On 4/6/25 12:12 PM, olcott wrote:
>>> 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.
>>>
>>
>> WRONG.
>>
>> To prove Turing wrong, 
> 
> Is not what a proof of total correctness means.
> 
> Only requires proving that a software function derives
> values corresponding to its input for its domain of
> inputs AND  this software function halts for every
> input.
> 

First, you don't understand what "correctness" means, as it needs to 
derives a CORRECT value corresponding to its input, not just any old value.

And, to be able to show that it halts for every input, you need to first 
prove Turing wrong, as he shows that operation to be impossible in general.

Note, this doesn't say that proving a specific program is correct is 
impossible, because we can correctly show that many programs are 
halting, and even show them to always terminate. The limitation is that 
no analyzer will be correct for ALL inputs.

OF course, your claim that a correct program only needs to return some 
value corresponding to its input, and not a correct value, opens your 
crack for it to use a wrong correspondence, like your straw-man 
relationship.