Re: What is the best way for termination analyzers to handle pathological inputs?

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