Path: ...!weretis.net!feeder8.news.weretis.net!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: Thu, 16 May 2024 09:08:50 -0500
Organization: A noiseless patient Spider
Lines: 159
Message-ID: <v2541i$1jo3l$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>
 <v1t8rt$3gu9t$2@dont-email.me> <v1varv$39j3$1@dont-email.me>
 <v1vrd9$7577$1@dont-email.me> <v21pla$ojrm$1@dont-email.me>
 <v22i6i$u8pk$1@dont-email.me> <v24ld9$1ge11$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 16 May 2024 16:08:51 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="4dc0119aaf775edb7bf006f6d2fcc2e1";
	logging-data="1695861"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19IXLqRsVZ/XLp9jiYikBkZ"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:02XBu6NfVFHFff5DrL4xBEbJfgc=
In-Reply-To: <v24ld9$1ge11$1@dont-email.me>
Content-Language: en-US
Bytes: 7990

On 5/16/2024 4:59 AM, Mikko wrote:
> On 2024-05-15 14:52:01 +0000, olcott said:
> 
>> On 5/15/2024 2:53 AM, Mikko wrote:
>>> On 2024-05-14 14:10:47 +0000, olcott said:
>>>
>>>> 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.
>>>
>>> The important difference is that a partial halting decider takes
>>> a pair (progam, input) for input but a halting analyzer takes
>>> a singlet (program).
>>>
>>
>> One can analyze whether a specific program will halt with a specific
>> input.
> 
> However, there is no way to ensure that the answer is ever found.
> 

For the C version and the Turing machine version of the halting problem
template an answer <is> found.

>> This is especially important when the received view is that a
>> specific program cannot possibly handle a specific input correctly.
> 
> It is easy to try a specifc program with a specific input and see
> what happens, 

*The prior answer from the "received view" has always been no one knows*

It has always been the case in the "received view" that because the
pathological input D was defined to contradict every value that its
termination analyzer H returns that both YES and NO are the wrong
answer from H.

It never occurred to anyone that the simulated input cannot possibly
ever receive a return value to contradict. Simulation has always
previously been rejected out-of-hand without review.

> at least if the program terminates in a reasonble time.
> Of course, if a program runs many years before it answers its correctness
> is harder to determine.
> 

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