Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory,sci.logic
Subject: Re: Termination analyzer defined ---RICHARD IS WRONG !!!
Date: Wed, 15 May 2024 09:52:01 -0500
Organization: A noiseless patient Spider
Lines: 139
Message-ID: <v22i6i$u8pk$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 15 May 2024 16:52:03 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="0b1a5f306bf9a6832a28841b3fc547c1";
	logging-data="992052"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18fBB5FW+lCf2u1+m2TLsWz"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:no8p9dKOQiXHIEPY4bmsClvRgSM=
In-Reply-To: <v21pla$ojrm$1@dont-email.me>
Content-Language: en-US
Bytes: 7106

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.

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.


-- 
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer