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: Thu, 16 May 2024 09:21:54 -0500
Organization: A noiseless patient Spider
Lines: 89
Message-ID: <v254q3$1k0tq$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>
 <v1tktb$3jv6d$1@dont-email.me> <v1vb6j$3ccc$1@dont-email.me>
 <v1vrs0$7577$3@dont-email.me> <v21pqq$okqv$1@dont-email.me>
 <v22icv$u8vi$1@dont-email.me> <v24ljr$1ggcd$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 16:21:56 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="4dc0119aaf775edb7bf006f6d2fcc2e1";
	logging-data="1704890"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18FNK+UT9kq1rl1QcpIHgzn"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:K2jrADFJVkXFQC5t2YhD6TRAVCE=
In-Reply-To: <v24ljr$1ggcd$1@dont-email.me>
Content-Language: en-US
Bytes: 4439

On 5/16/2024 5:02 AM, Mikko wrote:
> On 2024-05-15 14:55:26 +0000, olcott said:
> 
>> On 5/15/2024 2:56 AM, Mikko wrote:
>>> On 2024-05-14 14:18:40 +0000, olcott said:
>>>
>>>> On 5/14/2024 4:34 AM, Mikko wrote:
>>>>> On 2024-05-13 18:07:37 +0000, Jeff Barnett said:
>>>>>
>>>>>> On 5/13/2024 3:06 AM, Mikko wrote:
>>>>>>
>>>>>>> Anyway, if an analyzer can never tell whether a program terminates
>>>>>>> with every possible input then it is not a termination analyzer.
>>>>>>
>>>>>> I don't think the above is true in the way you meant it. Recall 
>>>>>> that the collection of all Turing machines with blank input tapes 
>>>>>> is the same set of computations as the collection with arbitrary 
>>>>>> input tapes. It's always possible to take any specific machine, T, 
>>>>>> and initial tape, I, and produce machine T' with blank initial 
>>>>>> input tape that is equivalent: T' initially writes I on its tape 
>>>>>> (say one character output per state in sequence) then continues 
>>>>>> with the set of states that comprises T.
>>>>>>
>>>>>> So it is obvious that a termination analyzer (AKA a halt decider) 
>>>>>> restricted to blank tape problems will do quite nicely and it is 
>>>>>> also quite obvious that no such entity exists.
>>>>>
>>>>> You only discuss halting decisions with specific inputs. THerefore 
>>>>> you say
>>>>> nothing about termination analyzers and don't show any mistake in 
>>>>> my comment.
>>>>>
>>>>
>>>> 00 int H(ptr x, ptr x)  // ptr is pointer to int function
>>>> 01 int D(ptr x)
>>>> 02 {
>>>> 03   int Halt_Status = H(x, x);
>>>> 04   if (Halt_Status)
>>>> 05     HERE: goto HERE;
>>>> 06   return Halt_Status;
>>>> 07 }
>>>> 08
>>>> 09 int main()
>>>> 10 {
>>>> 11   H(D,D);
>>>> 12 }
>>>>
>>>> In any case you diverged away form the whole point of this thread.
>>>> Richard is wrong when he says that there exists an H/D pair such
>>>> that D simulated by H ever reaches past its own line 03.
>>>
>>> The main topic (per OP) is the definition of "termination analyzer".
>>> Whether someone is wrong about aomeone else is a secondary topic if
>>> a topic at all, and pretty poitless anyway.
>>>
>>
>> One can analyze whether a specific program will halt with a specific
>> input.
> 
> True but irrelevant. A termination analyser analyses a program without
> any knowledge about specific inputs.
> 

*If the halting problem is refuted by this then IT IS NOT IRRELEVANT*

We are merely haggling over what to call it, not that the idea is
of no value. H is a termination analyzer that correctly analyzes whether
or not a certain set of C function/input pairs will halt. Here are two
examples:

void Infinite_Recursion(u32 N)
{
   Infinite_Recursion(N);
}

int factorial(int n)
{
   if (n >= 1)
     return n*factorial(n-1);
   else
     return 1;
}



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