Path: ...!news.nobody.at!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: Sun, 19 May 2024 07:45:38 -0500
Organization: A noiseless patient Spider
Lines: 236
Message-ID: <v2cs9i$3cifp$3@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>
 <v2541i$1jo3l$2@dont-email.me> <v27674$241gv$1@dont-email.me>
 <v27uhu$28r3c$1@dont-email.me> <v29sln$2njtl$1@dont-email.me>
 <v2aec0$2qsgt$1@dont-email.me> <v2cl3r$3be9l$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 19 May 2024 14:45:39 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="8b2dd23db76027a1e88bd64b7a96c771";
	logging-data="3557881"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19Bd/sTuMEB4u7FrpeB9w56"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:vhGlXwQEbEaNZ/sWJ6efCcQkWWQ=
Content-Language: en-US
In-Reply-To: <v2cl3r$3be9l$1@dont-email.me>
Bytes: 10858

On 5/19/2024 5:43 AM, Mikko wrote:
> On 2024-05-18 14:35:43 +0000, olcott said:
> 
>> On 5/18/2024 4:33 AM, Mikko wrote:
>>> On 2024-05-17 15:53:33 +0000, olcott said:
>>>
>>>> On 5/17/2024 3:58 AM, Mikko wrote:
>>>>> On 2024-05-16 14:08:50 +0000, olcott said:
>>>>>
>>>>>> 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.
>>>>>
>>>>> That is a very restricted set of programs that are not very 
>>>>> interesting.
>>>>>
>>>>
>>>> If refuting the halting problem proofs is not very interesting then
>>>> what is interesting?
>>>>
>>>>> It is not sufficient that an answer must be given. There must be a
>>>>> proof that the wrong answer is never given. For programs outside of
>>>>> the domain and non-programs given as programs an answer that is
>>>>> neither "yes" or "no" is permitted.
>>>>>
>>>>
========== REMAINDER OF ARTICLE TRUNCATED ==========