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: Proving the: Simulating termination analyzer Principle
Date: Sun, 6 Apr 2025 02:03:42 +0100
Organization: Fix this later
Lines: 70
Message-ID: <vssjtf$3gd7d$5@dont-email.me>
References: <vss56v$375du$2@dont-email.me> <vss6ie$389d8$3@dont-email.me>
 <vss7av$375du$8@dont-email.me> <vss7em$389d8$5@dont-email.me>
 <vssa6p$3b2j0$2@dont-email.me> <vssdo7$3evdr$3@dont-email.me>
 <vssdsl$389d8$10@dont-email.me> <vssi9t$3ipb5$4@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 06 Apr 2025 03:03:43 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="dbe7ec1ac8ffd7a60b5ada94cfd55d95";
	logging-data="3683565"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1++S3Py9j8PQjAfIvi1fH+TtX8weKqvKosvW5K37hOR0Q=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:JM/+JewZpL2qwDJkxUg75rK4oEQ=
Content-Language: en-GB
In-Reply-To: <vssi9t$3ipb5$4@dont-email.me>
Bytes: 3522

On 06/04/2025 01:36, olcott wrote:
> On 4/5/2025 6:20 PM, dbush wrote:
>> On 4/5/2025 7:18 PM, olcott wrote:
>>> On 4/5/2025 5:18 PM, Richard Heathfield wrote:
>>>> On 05/04/2025 22:31, dbush wrote:
>>>>> On 4/5/2025 5:29 PM, olcott wrote:
>>>>>> On 4/5/2025 4:15 PM, dbush wrote:
>>>>>>> On 4/5/2025 4:52 PM, 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.
>>>>>>>>
>>>>>>>> void DDD()
>>>>>>>> {
>>>>>>>>     HHH(DDD);
>>>>>>>>     return;
>>>>>>>> }
>>>>>>>
>>>>>>> Except when doing so would change the input, as is the 
>>>>>>> case with HHH and DDD.
>>>>>>>
>>>>>>> Changing the input is not allowed.
>>>>>>
>>>>>> You may disagree that the above definition
>>>>>> of simulating termination analyzer is correct.
>>>>>>
>>>>>> It is self-evident that HHH must stop simulating
>>>>>> DDD to prevent its own non-termination.
>>>>>>
>>>>>
>>>>> Changing the input is not allowed.
>>>>
>>>> You're right, but it doesn't matter very much as long as 
>>>> terminates() *always* gets the answer right for any arbitrary 
>>>> program tape and any data tape. Mr Olcott's fails to do that.
>>>>
>>>
>>> Termination analyzers are not required to be infallible.
>>>
>>
>>
>> But they must still generate the required mapping for the input 
>> they claim to answer correctly:
>>
>>
>> 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
>>
> 
> Exactly the opposite, they are only allowed to report
> on what they see.

A solution is required to take into account all parts of the 
program that affect its termination status. It is not allowed to 
guess.

-- 
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