Re: Proving the: Simulating termination analyzer Principle

On 4/5/2025 8:36 PM, olcott wrote:

On 4/5/2025 6:20 PM, dbush wrote:

On 4/5/2025 7:18 PM, olcott wrote:

On 4/5/2025 5:18 PM, Richard Heathfield wrote:

On 05/04/2025 22:31, dbush wrote:

On 4/5/2025 5:29 PM, olcott wrote:

On 4/5/2025 4:15 PM, dbush wrote:

On 4/5/2025 4:52 PM, olcott wrote:

*Simulating termination analyzer Principle*
It is always correct for any simulating termination
analyzer to stop simulating and reject any input that
would otherwise prevent its own termination.
>
void DDD()
{
    HHH(DDD);
    return;
}

>
Except when doing so would change the input, as is the case with HHH and DDD.
>
Changing the input is not allowed.

>
You may disagree that the above definition
of simulating termination analyzer is correct.
>
It is self-evident that HHH must stop simulating
DDD to prevent its own non-termination.
>

>
Changing the input is not allowed.

>
You're right, but it doesn't matter very much as long as terminates() *always* gets the answer right for any arbitrary program tape and any data tape. Mr Olcott's fails to do that.
>

>
Termination analyzers are not required to be infallible.
>

>
>
But they must still generate the required mapping for the input they claim to answer correctly:
>
>
Given any algorithm (i.e. a fixed immutable sequence of instructions) X described as <X> with input Y:
>
A solution to the halting problem is an algorithm H that computes the following mapping:
>
(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly
>

 Exactly the opposite, they are only allowed to report
on what they see.
 

No, they report what they are programed to report, which is some computable function.
And the halting function is not a computable function, as Linz and others have proved:
Given any algorithm (i.e. a fixed immutable sequence of instructions) X described as <X> with input Y:
A solution to the halting problem is an algorithm H that computes the following mapping:
(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly