Path: 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: Fri, 17 May 2024 11:58:12 +0300 Organization: - Lines: 154 Message-ID: References: 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 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