Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: What is the best way for termination analyzers to handle
 pathological inputs?
Date: Wed, 11 Jun 2025 14:12:48 -0500
Organization: A noiseless patient Spider
Lines: 67
Message-ID: <102ckfg$25dg0$1@dont-email.me>
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>
 <b7833de17b81773536f5837bf1ca856100abd776@i2pn2.org>
 <bPj2Q.137333$v0S.21911@fx14.ams4>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 11 Jun 2025 21:12:49 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="c5844607f8c5789cdff36a135feed3c9";
	logging-data="2274816"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/gHKUVMBwhZeMun57PaIvr"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:er7U1f9U9tGN1f+7bJDBodD6Hf4=
X-Antivirus-Status: Clean
Content-Language: en-US
X-Antivirus: Norton (VPS 250611-4, 6/11/2025), Outbound message
In-Reply-To: <bPj2Q.137333$v0S.21911@fx14.ams4>

On 6/11/2025 1:21 PM, Mr Flibble wrote:
> On Tue, 10 Jun 2025 23:15:51 -0400, Richard Damon wrote:
> 
>> 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)
> 
> You are wrong. An SHD does not have to simulate an algorithm to completion
> if it determines non-halting early BY ANALYSIS.
> 
> /Flibble

You can tell him this 1000 times and he will never get it.

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