Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory,sci.logic
Subject: Re: Termination analyzer defined ---RICHARD IS WRONG !!!
Date: Mon, 13 May 2024 09:42:05 -0500
Organization: A noiseless patient Spider
Lines: 112
Message-ID: <v1t8rt$3gu9t$2@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 13 May 2024 16:42:06 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="822a7b45c10435b9354ed3bfb60d5b64";
	logging-data="3701053"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/VfiBQrwfCuw/7j6vdRPcK"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:fmiVxZ9Ut926Pflr1lfaCYHuz5o=
In-Reply-To: <v1sl6o$3cg5n$1@dont-email.me>
Content-Language: en-US
Bytes: 5496

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.

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.

>> Termination analyzers are allowed to be quite dumb so that they
>> handle very few programs.
> 
> True, but the more the better. But they must not report "yes" if
> the program may fail to terminate.
> 

So they are not answering the question:
Does this program halt?

Instead they are answering the question:
Does this program not halt?

>> One of the best termination analyzers could not handle any
>> recursive programs at all for quite a few years.
> 
> In many context recursive programs are prohibited anyway so that
> is not always a serious restriction.
> 

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