Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Termination analyzer defined ---RICHARD IS WRONG !!!
Date: Fri, 17 May 2024 12:03:53 +0300
Organization: -
Lines: 72
Message-ID: <v276hp$24419$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> <v254q3$1k0tq$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 17 May 2024 11:03:53 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="dbf1b225f2871bff3da7815f4eb7b472";
	logging-data="2232361"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19ZzpsMsv5a4skhfjeb4foI"
User-Agent: Unison/2.2
Cancel-Lock: sha1:8csZTIxNEbXd+bavNxvx3eSYbGw=
Bytes: 4132

On 2024-05-16 14:21:54 +0000, olcott said:

> 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*

It is irrelevant anyway. Facts are irrelevant to definitions and
definitions are irrelevant to facts (though they may be relevant
to the choice or validity of presentation of facts).

-- 
Mikko