Re: Turing computable functions

On 3/25/2025 3:24 PM, olcott wrote:

Cannot possibly derive any outputs not computed from
their inputs.

Correct, algorithms can only compute computable mathematical function.

 A Turing machine halt decider

Does not exist because the required mapping is not computable:
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

cannot possibly report
on the behavior of any directly executing process.
No Turing machine can every do this. This has always
been beyond what any Turing machine can ever do.

Strawman: reporting on an executing process is not a requirement.  But because a Turing machine will always behavior exactly the same for a given input, a complete description of that Turing machine fully specifies what would happen in the hypothetical case that such a machine was executed directly.

 The best that any Turing machine halt decider can
possibly do is determine the behavior that an input
finite string specifies.
 

In other words, a Turing machine can only compute a computable function.
And because the mathematical halting function is not computable, no Turing machine can compute it.

When we make these things 100% concrete in a language
that has been fully operational for many years...
 int DD()
{
   int Halt_Status = HHH(DD);
   if (Halt_Status)
     HERE: goto HERE;
   return Halt_Status;
}
 When an input finite string specifies a pathological
relationship with its simulating halt decider

Halt deciders don't exist.