Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott 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: References: 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: 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