Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Jeff Barnett <jbb@notatt.com>
Newsgroups: comp.theory
Subject: Re: Termination analyzer defined ---RICHARD IS WRONG !!!
Date: Mon, 13 May 2024 12:07:37 -0600
Organization: A noiseless patient Spider
Lines: 19
Message-ID: <v1tktb$3jv6d$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 13 May 2024 20:07:39 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="254b4e125552f823a15adf565ca83ca2";
	logging-data="3800269"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX199Kkgn7KNCMwwK2ven9hf2R19/LJwXUFA="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:DPhKIumCWqN+3E+VanCa5TjfFQM=
In-Reply-To: <v1sl6o$3cg5n$1@dont-email.me>
Content-Language: en-US
Bytes: 2131

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.
-- 
Jeff Barnett