Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: Termination analyzer defined ---RICHARD IS WRONG !!!
Date: Tue, 14 May 2024 09:10:47 -0500
Organization: A noiseless patient Spider
Lines: 127
Message-ID: <v1vrd9$7577$1@dont-email.me>
References: <v1me7i$1l6ut$1@dont-email.me> <v1nec4$1vb8i$1@dont-email.me>
 <v1o6p5$24f4c$2@dont-email.me> <v1pvj0$2knal$1@dont-email.me>
 <v1qi01$2on4q$2@dont-email.me> <v1qn4o$2pts6$1@dont-email.me>
 <v1qt92$2rdui$1@dont-email.me> <v1sl6o$3cg5n$1@dont-email.me>
 <v1t8rt$3gu9t$2@dont-email.me> <v1varv$39j3$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 14 May 2024 16:10:49 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e9b15de5cbd4b611ca4438a3f5fabf94";
	logging-data="234727"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/zYrmD3d/qIgJSk7B/0kSE"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:GxRpnwTk3bsaEYdXPjG2yRFKhW0=
Content-Language: en-US
In-Reply-To: <v1varv$39j3$1@dont-email.me>
Bytes: 5990

On 5/14/2024 4:28 AM, Mikko wrote:
> On 2024-05-13 14:42:05 +0000, olcott said:
> 
>> On 5/13/2024 4:06 AM, Mikko wrote:
>>> On 2024-05-12 17:12:00 +0000, olcott said:
>>>
>>>> On 5/12/2024 10:27 AM, Mikko wrote:
>>>>> On 2024-05-12 13:59:28 +0000, olcott said:
>>>>>
>>>>>> On 5/12/2024 3:45 AM, Mikko wrote:
>>>>>>> On 2024-05-11 16:35:48 +0000, olcott said:
>>>>>>>
>>>>>>>> On 5/11/2024 4:39 AM, Mikko wrote:
>>>>>>>>> On 2024-05-11 00:30:40 +0000, olcott said:
>>>>>>>>>
>>>>>>>>>> A termination analyzer is different than a halt decider in 
>>>>>>>>>> that it need
>>>>>>>>>> not correctly determine the halt status of every input. For 
>>>>>>>>>> the purposes
>>>>>>>>>> of this paper a termination analyzer only needs to correctly 
>>>>>>>>>> determine
>>>>>>>>>> the halt status of one terminating input and one 
>>>>>>>>>> non-terminating input.
>>>>>>>>>> The computer science equivalent would be a halt decider with a 
>>>>>>>>>> limited
>>>>>>>>>> domain that includes at least one halting and one non-halting 
>>>>>>>>>> input.
>>>>>>>>>
>>>>>>>>> From https://www.google.fi/search?q=termination+analysis and
>>>>>>>>> https://en.wikipedia.org/wiki/Termination_analysis :
>>>>>>>>>
>>>>>>>>> "In computer science, termination analysis is program analysis 
>>>>>>>>> which attempts to determine whether the evaluation of a given 
>>>>>>>>> program halts for each input. This means to determine whether 
>>>>>>>>> the input program computes a total function."
>>>>>>>>>
>>>>>>>>> So the term "termination analysis" is already defined. The 
>>>>>>>>> derived term
>>>>>>>>> "termination analyzer" means a performer of termination 
>>>>>>>>> analysis. That
>>>>>>>>> does not agree with the propsed defintion above so a differnt term
>>>>>>>>> should be used.
>>>>>>>>>
>>>>>>>>> That "termination analysis" is a know term that need not be 
>>>>>>>>> defined
>>>>>>>>> is demostrated e.g. by
>>>>>>>>>
>>>>>>>>>    https://arxiv.org/pdf/2101.09783
>>>>>>>>>
>>>>>>>>> which simply assumes that readers know (at least approximately) 
>>>>>>>>> what
>>>>>>>>> the term means.
>>>>>>>>>
>>>>>>>>
>>>>>>>> You are doing a great job performing an honest review!
>>>>>>>> So every time that Richard referred to a {termination analyzer} 
>>>>>>>> that
>>>>>>>> ignores its inputs *Richard was WRONG*
>>>>>>>
>>>>>>> More important is that you are wrong whenever you use "termination
>>>>>>> analyser" for something that by the conventional meaning isn't.
>>>>>>>
>>>>>>
>>>>>> A conventional termination analyzer is free to use any algorithm
>>>>>> as long as it analyzes termination.
>>>>>
>>>>> It is not sufficient to analyse something about termination. The
>>>>> conventional meaning is that a termination analyser does not say
>>>>> "yes" unless the analysed program terminates with every possible
>>>>> input.
>>>>>
>>>>
>>>> A specific program halts with every input is not at all the same
>>>> thing as correctly analyzing every program with every input.
>>>
>>> If you can't find out whether a program halts with every input even
>>> after analyzing it with every input your analysis is not really
>>> good enough for the purpose.
>>>
>>> Anyway, if an analyzer can never tell whether a program terminates
>>> with every possible input then it is not a termination analyzer.
>>>
>>
>> My simple termination analyzer easily determines whether or not
>> the limited class of programs that are in its domain halt on
>> every input. For example D() only has three classes of inputs
>> (a) Inputs that halt
>> (b) Inputs that do not halt
>> (c) itself.
> 
> If you can prove that it never gives a wrong "yes" answer
> you can call it a "termination analyzer". Even better if
> you can prove that it never gives a "yes" answer for an
> invalid input.
> 
> However, it is not useful if it does not say "yes" about any useful
> or interesting program.
> 
>> Because it is a termination analyzer it need not work for
>> all programs. A partial halt decider with a limited domain
>> seems to be the equivalent theory of computation terminology.
> 
> A partial halt decider is not a termination analyzer. Their input
> spaces are distinct.
> 

It correctly determines the halt status YES or NO
for a specific limited set of programs and ALL of
the inputs to this limited infinite set of programs.

void Infinite_Recursion(u32 N)
{
   Infinite_Recursion(N);
}

int factorial(int n)
{
   if (n >= 1)
     return n*factorial(n-1);
   else
     return 1;
}

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