Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!panix!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: What is the best way for termination analyzers to handle
 pathological inputs?
Date: Tue, 10 Jun 2025 23:15:51 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <b7833de17b81773536f5837bf1ca856100abd776@i2pn2.org>
References: <1027isi$on4i$1@dont-email.me> <1028n53$1440t$1@dont-email.me>
 <1029pla$1ah2f$15@dont-email.me>
 <f901f7cb6bb240e46f2f64f93f3571ccfe8b90d2@i2pn2.org>
 <xl%1Q.285105$VBab.37836@fx08.ams4>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 11 Jun 2025 03:38:21 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="4192395"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
X-Spam-Checker-Version: SpamAssassin 4.0.0
In-Reply-To: <xl%1Q.285105$VBab.37836@fx08.ams4>
Content-Language: en-US

On 6/10/25 3:05 PM, Mr Flibble wrote:
> On Tue, 10 Jun 2025 14:53:47 -0400, Richard Damon wrote:
> 
>> On 6/10/25 1:22 PM, olcott wrote:
>>> On 6/10/2025 2:33 AM, Mikko wrote:
>>>> On 2025-06-09 21:14:58 +0000, olcott said:
>>>>
>>>>> The official "received view" of this is that the best we can possibly
>>>>> do is to do nothing and give up.
>>>>
>>>> There is no official view about "the best". What is the best depends
>>>> on what one needs and wants. Some may think that the best they can do
>>>> is to waste their life in trying to do the impossible.
>>>>
>>>>
>>> It is not at all impossible to create a termination analyzer that
>>> reports on the behavior specified by the input to HHH(DDD). It was
>>> never correct to define a termination analyzer any other way.
>>>
>>>
>> Right, it is just a fact that it is impossible for HHH to be shuch a
>> analyzer.
>>
>> A CORRECT Temrination analyzer of the input to HHH(DDD), that is to the
>> termination analysis of DDD, is to say it halts, since the HHH(DDD) that
>> DDD will call  will return non-halting to that DDD, and it will then
>> halt.
> 
> But it will never "return" because it is infinitely recursive; the
> simulation is aborted and a halting result if non-halting is returned
> elsewhere.
> 
> /Flibble

So, you have a problem, either you don't have a correct simulation to 
show you got the right answer, or you don't answer.

That is the problem with trying to have the decider itself be two 
contradictory entities.

A correct simulator can not be a correct decider it the input is 
actually non-halting.

There seems to be some mental block about the fact that the DEFINITION 
of this sort of decider is that:


H(M) returns 1 if UTM(M) halts, and
H(M) returns 0 if UTM(M) will never halt

If you try to combine the the UTM and H into one program that it can 
NEVER correctly return 0, as it can only return 0 if it never halt (and 
thus can't return a value)