Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: Termination analyzer defined ---RICHARD IS WRONG !!! Date: Thu, 16 May 2024 12:59:05 +0300 Organization: - Lines: 125 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Thu, 16 May 2024 11:59:06 +0200 (CEST) Injection-Info: dont-email.me; posting-host="1042f681036333a040f7e702dbbd055b"; logging-data="1587233"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+Eia2Sl1NbinBx3HXbu+Ra" User-Agent: Unison/2.2 Cancel-Lock: sha1:xhZC8UFXYcNdAGyCFLTaEOjhF4g= Bytes: 6717 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. > 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, 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. -- Mikko