Deutsch English Français Italiano |
<v2aepq$1ct7p$6@i2pn2.org> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail From: Richard Damon <richard@damon-family.org> Newsgroups: comp.theory Subject: Re: Termination analyzer defined ---RICHARD IS WRONG !!! Date: Sat, 18 May 2024 10:43:06 -0400 Organization: i2pn2 (i2pn.org) Message-ID: <v2aepq$1ct7p$6@i2pn2.org> 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> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 18 May 2024 14:43:06 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="1471737"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird X-Spam-Checker-Version: SpamAssassin 4.0.0 Content-Language: en-US In-Reply-To: <v2aec0$2qsgt$1@dont-email.me> Bytes: 11717 Lines: 257 On 5/18/24 10:35 AM, olcott wrote: > 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. >>>> >>> >>> *Not at all. Not in the least little bit* >>> For the H/D pairs comprising the halting problem counter-example all >>> that needs be shown is that one of YES or NO <is> the correct answer. >> ========== REMAINDER OF ARTICLE TRUNCATED ==========