Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.lang.c
Subject: Re: DD simulated by HHH cannot possibly halt (Halting Problem)
Date: Sat, 5 Apr 2025 08:42:41 +0100
Organization: Fix this later
Lines: 51
Message-ID: <vsqmth$1mglg$2@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 05 Apr 2025 09:42:42 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9ba5473c49a0346d8825952a0365662d";
	logging-data="1786544"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX193Pby1+08D6X4L2yTxgWoGj3TRHceO8QOR/VIdAYx0FQ=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:T4+KbbELb4nGint9iF5QgJ5UsKI=
Content-Language: en-GB
In-Reply-To: <vsqhov$1hl94$1@dont-email.me>
Bytes: 2876

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.

Your reasoning is that it has a good excuse and can be forgiven 
for failing. Fine, but it still fails. Calling an abort 'correct' 
doesn't stop it being an abort.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within