Re: Turing Machine computable functions apply finite string transformations to inputs VERIFIED FACT

On 29/04/2025 20:56, olcott wrote:

On 4/29/2025 2:39 PM, Richard Heathfield wrote:

On 29/04/2025 20:06, olcott wrote:

On 4/29/2025 8:46 AM, Richard Heathfield wrote:

On 29/04/2025 14:11, olcott wrote:

On 4/29/2025 2:10 AM, Richard Heathfield wrote:

On 29/04/2025 03:50, olcott wrote:

>
<snip>
>

Yet it is H(P,D) and NOT P(D) that must be measured.

>
Nothing /has/ to be measured. P's behaviour (halts, doesn't halt) when given D as input must be /established/.

>
No H can possibly see the behavior of P(D)

>
It doesn't have to.

>
IF IT CAN'T SEE IT THEN  IT CAN'T REPORT ON  IT.

>
Yes, it can. There is no need to see the behaviour to establish whether it halts. All the decider has to be able to see is the code.
>

 THE CODE THAT IT CAN SEE
unequivocally specifies that the INPUT DOES NOT HALT

Fine. Either it's right or it's wrong.
If it's wrong, it's wrong. And if it's right we can use it to write a program that it can't figure out. Turing proved this.

 

I, as a decider, do not need to see the following program's behaviour to determine whether it halts...
>
int main(void)
{
   while(1);
   return 0;
}
>
...because I can tell just by reading the code that it enters an infinite loop and so will not halt. I can report on whether the program halts without having to execute it.
>

 IT DOES NOT WORK THAT WAY WITH PATHOLOGICAL SELF-REFERENCE.

There's nothing in the rules to stop it. Reading the code is a perfectly valid way of establishing whether a program halts, and Turing machines are more than capable of reading and analysing code. Compilers do it all the time.
What we /can't/ do by reading the code is devise a universally accurate termination analyser, for the same reason we can't devise a universally accurate termination analyser that executes the code to see what happens.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within