Path: eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Termination analyzer defined ---RICHARD IS WRONG !!!
Date: Fri, 17 May 2024 11:58:12 +0300
Organization: -
Lines: 154
Message-ID: <v27674$241gv$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> <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 17 May 2024 10:58:13 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="a22dcd17c78d043803e93f5ba133f190";
	logging-data="2229791"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/o1G3Abb5y7E53lvnV/+nY"
User-Agent: Unison/2.2
Cancel-Lock: sha1:KMrDLLFBT2CtUaUQTNLWFOpwqXo=

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.

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.

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

Your "received view" seems to disagree with everyting everybody else
has said about the topic.

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

That every Turing machine fails as a halt decider is sufficient to
infer that every simulating Turing machine fails as a halt decider.

-- 
Mikko