Deutsch English Français Italiano |
<v23jqg$15707$24@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,sci.logic Subject: Re: Termination analyzer defined ---OLCOTT IS WRONG !!! Date: Wed, 15 May 2024 20:25:52 -0400 Organization: i2pn2 (i2pn.org) Message-ID: <v23jqg$15707$24@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> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Thu, 16 May 2024 00:25:52 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="1219591"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird Content-Language: en-US X-Spam-Checker-Version: SpamAssassin 4.0.0 In-Reply-To: <v22i6i$u8pk$1@dont-email.me> Bytes: 7471 Lines: 146 On 5/15/24 10:52 AM, olcott wrote: > 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. This is especially important when the received view is that a > specific program cannot possibly handle a specific input correctly. > > H(D,D) must actually analyze the behavior that D specifies and D > specifies that D correctly simulated by H cannot possibly reach > its own simulated final state and halt. But the behavior that H is supposed to be answering about is does D(D) halt when run. If you are admitting that you are just working on your POOP, you need to stop talking about is a "Halt Deciding", because that is juat a LIE. > > In the above case a simulator is an x86 emulator that correctly > emulates the x86 instructions of D in the order specified by the > x86 instructions of D until H correctly determines that D correctly > simulated by H cannot possibly reach its own simulated final state > at line 06. This may possibly include one or more recursive > simulations. > > Except that I have shown how to write an H that does that, and you are too stupid and bullheaded to understand that.